River Crossing Puzzles
Wolf, goat and cabbage plus missionaries and cannibals — with the search that shows four of each with a two-seat boat is impossible.
The farmer’s puzzle has exactly one real decision in it
There are exactly two shortest solutions, both seven crossings, and they are the same solution with one swap:
- goat → alone → wolf → goat → cabbage → alone → goat
- goat → alone → cabbage → goat → wolf → alone → goat
Counting, at every step, how many moves keep you on a shortest path gives 1, 1, 2, 1, 1, 1, 1 — one everywhere except the third crossing, where you pick the wolf or the cabbage. One binary choice in the whole thing, and having made it the rest is forced.
The move people actually miss is the fourth: bringing the goat back. Nobody expects to undo progress, which is exactly why a puzzle with one decision in it feels clever. Three of the four opening moves are unsafe, so even the first move is forced.
Four missionaries with a two-seat boat is impossible
Three of each takes eleven crossings and everyone knows it. Four of each cannot be done at all — not hard, impossible. Exhaustive search over the whole state space finds no path. The wall is the boat, not the puzzle:
| Of each | 2-seat boat | 3-seat boat | 4-seat boat |
|---|---|---|---|
| 1 | 1 crossings | 1 crossings | 1 crossings |
| 2 | 5 crossings | 3 crossings | 1 crossings |
| 3 | 11 crossings | 5 crossings | 3 crossings |
| 4 | impossible | 9 crossings | 5 crossings |
| 5 | impossible | 11 crossings | 7 crossings |
| 6 | impossible | impossible | 9 crossings |
A three-seat boat carries five pairs and then fails at six. A four-seat boat never fails. And the sharpest version of it: five missionaries and four cannibals crosses fine in fifteen, while four and four cannot cross at all. Adding a missionary to an impossible puzzle makes it solvable, because the rule is a comparison and not a headcount.
The rules
- Wolf, goat, cabbage. The boat holds the farmer and one passenger. Left alone, the wolf eats the goat and the goat eats the cabbage. The wolf has no interest in cabbage, which is the only reason the puzzle works at all.
- Missionaries and cannibals. On neither bank may the cannibals outnumber the missionaries — unless there are no missionaries there, in which case there is nobody to eat. The boat needs at least one person to row it, and cannot itself be unsafe.
- Every solution here is a shortest one, found by breadth-first search over the full state space, and every impossibility is the absence of any path at all rather than a failure to find one.
How to use
- Pick a puzzle and click what you want to take across.
- Moves that would leave something to be eaten are refused, with the reason.
- For missionaries and cannibals, set the party size and the boat seats.
- Read the verdict first — some settings cannot be solved at all.
Frequently asked questions
How do you solve the wolf, goat and cabbage puzzle?
Take the goat over, row back alone, take the wolf over, bring the goat BACK, take the cabbage over, row back alone, then take the goat over. Seven crossings. The wolf and the cabbage are interchangeable, so swapping those two steps gives the only other shortest answer.
Why do you bring the goat back?
Because the goat is the only thing that cannot be left with either of the others. Once the wolf is across, the goat cannot stay with it, so it has to return. That single backwards step is the whole puzzle — nobody expects to undo progress.
How many solutions does the farmer puzzle have?
Exactly two shortest ones, both seven crossings, and they differ only in whether the wolf or the cabbage crosses third. Counting the moves that stay on a shortest path gives one at every step except the third, so the entire puzzle contains a single binary decision.
How many trips for three missionaries and three cannibals?
Eleven crossings, and a breadth-first search over the whole state space confirms nothing shorter exists. The tool will walk you through one.
Can four missionaries and four cannibals cross?
Not with a two-seat boat. It is impossible, not merely difficult — an exhaustive search finds no path at all. A three-seat boat does it in nine, and carries five pairs before failing at six. A four-seat boat never fails.
Why is four and four impossible but five and four fine?
Because the rule is a comparison, not a headcount. Five missionaries and four cannibals crosses in fifteen while four and four cannot cross at all, so adding a missionary to an impossible puzzle makes it solvable.
What are the rules for missionaries and cannibals?
On neither bank may the cannibals outnumber the missionaries, unless there are no missionaries there at all, in which case nobody is at risk. The boat needs at least one person to row it and cannot itself carry an unsafe mix.
Does this send anything anywhere?
No. Every search runs in your browser and nothing is stored or uploaded.
🔒 This tool runs entirely in your browser. Nothing you enter is uploaded, logged, or stored.