River Crossing Puzzles

How to play the river crossing puzzles

Choose a puzzle and read its rule. Tap someone on the bank where the boat is to put them in it, tap them again to take them out, and press Cross. The ones in bold can row. If a crossing would break the rule, on either bank or in the boat, the page says what would go wrong and lets you try again. Finish and it tells you whether you found the fewest crossings. Show the solution plays the shortest one step by step.

The wolf, goat and cabbage riddle: the solution

Take the goat over first: the wolf will not eat cabbage. Come back alone and take the wolf over, then bring the goat back with you. Leave the goat, take the cabbage over to the wolf, come back alone, and fetch the goat. Seven crossings, and the trick is the one everybody misses: something has to come back. The fox, chicken and grain is the same puzzle with different animals, and so is any version with a fox, a goose and a bag of beans. It is one of the oldest puzzles written down, in a collection attributed to Alcuin of York from around the year 800.

Missionaries and cannibals, and the jealous husbands

Three missionaries and three cannibals take 11 crossings with a boat for two. With four of each and a boat for two it cannot be done at all, and the solver proves it by checking every arrangement that can be reached; with a boat for three, five of each can make it in 11, but six cannot. The jealous husbands, three couples where no wife may be with another man unless her husband is there, also takes 11 crossings, and four couples with a boat for two is impossible.

These are the standard first examples of search in artificial intelligence. A state is how many of each are on the far bank and which side the boat is on; the moves are the crossings the rules allow; breadth-first search tries every state one crossing away, then two, and so on, so the first time it reaches everyone across, it has found the fewest crossings. That is exactly what Show the solution does.

The policeman and thief river crossing

Father, mother, two sons, two daughters, a policeman and a thief, and a raft for two that only the father, the mother and the policeman can work. The father must not be with a daughter without the mother, the mother must not be with a son without the father, and the thief must not be with any of the family unless the policeman is there. It takes 17 crossings. Start by sending the policeman over with the thief.

Bridge and torch

Four people must cross a bridge at night with one torch, at most two at a time, at the pace of the slower one. Taking 1, 2, 5 and 10 minutes, the best is 17: the two fastest cross, one brings the torch back, the two slowest cross together, and the other fast one brings it back for the last trip. The obvious plan, the fastest walking everyone across, takes 19. Change the times and the solver finds the fastest plan for those, which is not always the same pattern.

More logic puzzles

The water jug puzzle solver is the other classic of the AI textbooks, and the Tower of Hanoi the most famous shortest-path puzzle of all. For puzzles you hold in your hands, our brain teasers ask for the same kind of thinking ahead. There are more solvers on the puzzle tools page.