The wolf, goat, and cabbage river-crossing problem. Illustration from the cover of Introduction to the Design and Analysis of Algorithms by Anany Levitin
Puzzles in which a variety of objects and living things, some of them mutually incompatible, must be conveyed in small groups from one side of a river to another without any loss along the way. The earliest known examples are in Propositiones ad Acuendos, which is generally attributed to Abbott Alcuin. They are: the problem of three jealous husbands (each of whom won't let another man be alone with his wife), the problem of the wolf, the goat, and the cabbage, and the problem of the two adults and two children where the children weigh half as much as the adults. In the wolf-goat-cabbage case, the difficulty is that only one item can be ferried across at once but, if left unattended, the sheep will eat the cabbage and the wolf will eat the sheep. The solution, which involves a stratagem common to all these types of problems, is to bring back to the starting bank of the river an item that has already been taken across. In this case, the sheep must be taken across first, followed by either the cabbage or the wolf, but then the sheep must be brought back before the next item is taken across to avoid the sheep become either a diner or a dinner.
These medieval puzzles were considered and elaborated by Niccoló Tartaglia, Luca Pacioli, and Claude-Gaspar Bachet, and even more so by later mathematicians such as Edouard Lucas and Gaston Tarry, and others. Ways of complicating river-crossing problems include adding more people and objects, using a bigger boat, and inserting an island in the river.
