A river crossing puzzle is a type of puzzle in which the object is to carry items from one river bank to another, usually in the fewest trips. The difficulty of the puzzle may arise from restrictions on which or how many items can be transported at the same time, or which or how many items may be safely left together. The setting may vary cosmetically, for example, by replacing the river by a bridge. The earliest known river-crossing problems occur in the manuscript Propositiones ad Acuendos Juvenes (), traditionally said to be written by Alcuin. The earliest copies of this manuscript date from the 9th century; it contains three river-crossing problems, including the wolf, goat and cabbage problem and the missionaries and cannibals problem.

Well-known river-crossing puzzles include:

• The wolf, goat and cabbage problem, in which a wolf, goat and cabbage must cross the river in a boat but the neither the goat and cabbage, or wolf and goat can be alone together. The puzzle can also be formulated as a fox, goose, and bag of beans puzzle.

• The missionaries and cannibals problem, in which three missionaries and three cannibals must cross the river, with the constraint that at any time when both missionaries and cannibals are standing on either bank, the cannibals on that bank may not outnumber the missionaries. Also formulated as the jealous husbands problem.

• The bridge and torch problem in which four people come to a river in the night. There is a narrow bridge, and it can only hold two people at a time. They have one torch and, because it's night, the torch has to be used when crossing the bridge.

• Propositio de viro et muliere ponderantibus plaustrum. In this problem, also occurring in Propositiones ad Acuendos Juvenes, a man and a woman of equal weight, together with two children, each of half their weight, wish to cross a river using a boat which can only carry the weight of one adult.

These problems may be analyzed using graph-theoretic methods, by dynamic programming, or by integer programming.

Graph theoretic formulation

be an undirected graph the bag of beans, then the two vertices would be connected since the goose cannot be left on the same side of the river with a bag of beans. Note that the edges are undirected, as the nature of the conflict between the two items does not affect the fact that they cannot be left on the same side of the river. The object of the problem is to determine the minimum size of the boat such that a trip is feasible; this is known as the Alcuin number.

is a vertex cover.

.

holds is NP-hard. Because the minimum vertex cover problem is NP-complete is NP-hard. However, for certain classes of graphs, stronger results hold. For example, for planar graphs, determining which of the two relations holds can be done in polynomial time remains NP-hard); for bipartite graphs can both be computed exactly in polynomial time.

References