Wolf, Goat and Cabbage: Puzzle and Step-by-Step Solution
Logic & Strategy
Easy
Reported at Optiver, IMC, Akuna
The puzzle
A farmer must ferry a wolf, a goat and a cabbage across a river in a boat that holds him and one passenger. Left alone together, the wolf eats the goat and the goat eats the cabbage. How does he get everything across intact?
Short answer: Seven crossings, and the key is move four: after delivering the wolf, the farmer brings the goat back.
Step 1: Find the piece that constrains everything
List the conflicts: wolf with goat, and goat with cabbage. The wolf and the cabbage are safe together. So the goat is the only passenger that conflicts with both others, and it can never be left unsupervised with either.
That gives an invariant: whenever the farmer is on the other bank, the goat must be alone, or the two others must be together without it. Any plan that breaks this fails.
Step 2: The seven crossings
1. Take the goat across; the wolf and cabbage are safe together. 2. Row back alone. 3. Take the wolf across. 4. Bring the goat back, because the wolf cannot be left with it. 5. Take the cabbage across; the goat waits alone on the near bank. 6. Row back alone. 7. Take the goat across. Everything is over, intact.
Taking the cabbage at step 3 instead of the wolf works symmetrically: then the goat comes back at step 4 and the wolf crosses at step 5.
Step 3: Why the backward move is forced
The goat must cross first, because the first trip cannot carry the wolf (leaving goat and cabbage) or the cabbage (leaving wolf and goat). Once the goat is over, the second passenger to arrive will be left with it while the farmer goes back. The only way to keep the invariant is to take the goat with him on that return trip.
Seven is the minimum. Each trip carries at most one passenger forward, three passengers need at least three forward trips, and the goat travels forward twice and back once. With the empty returns that is seven crossings.
Step 4: The general lesson
In a constrained search, progress is not monotone. Solvers who insist every move go forward have quietly added a constraint the puzzle never stated. Drawing the state space, with each bank's contents as a node and each trip as an edge, finds the answer mechanically, and that is the technique interviewers want named.
Why interviewers ask it
Interviewers listen for the invariant, the goat is never unsupervised with anything, not the memorised sequence. Mention that this is a breadth-first search over states.
Knowing the proof is half of it. Work Wolf, Goat and Cabbage interactively, then take it under a clock with the rest of the Outcry simulators.