River crossing puzzle

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.

[1] The setting may vary cosmetically, for example, by replacing the river by a bridge.

[1] The earliest known river-crossing problems occur in the manuscript Propositiones ad Acuendos Juvenes (English: Problems to sharpen the young), 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 fox, goose, and bag of beans puzzle and the jealous husbands problem.

[2] Well-known river-crossing puzzles include: These problems may be analyzed using graph-theoretic methods,[4][5] by dynamic programming,[6] or by integer programming.

be an undirected graph whose vertex set

represents items that the farmer must carry, and whose edge set

consists of pairs of items that conflict.

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 of

Consider a successful river crossing in which the farmer first carries a subset

of items across the river, leaving the remaining

Because the trip is successful, there must be no conflicts in the items left onshore; ie.

This implies that all edges

of the minimum vertex cover of

; this forms a lower bound on the Alcuin number of

On the other hand, it is possible to complete a successful trip with boat size equal to

This can be achieved by requiring the members

of a minimum vertex cover to remain on the boat at all times; these items number

, and thus leave one more space on the boat.

items, they can be taken across the river one at a time in any order, occupying the one remaining space on the boat.

, forming an upper bound for

[7] Csorba, Hurkens, and Woeginger proved in 2008 that determining which of

[5] Because the minimum vertex cover problem is NP-complete, it follows that computing the Alcuin number of a graph

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 (though determining either

remains NP-hard); for bipartite graphs,

can both be computed exactly in polynomial time.