Wolf, Goat and Cabbage Solution - The 7-Crossing Answer

The setup

A farmer must ferry a wolf, a goat and a cabbage across a river, one passenger per trip. Left unsupervised, the wolf eats the goat and the goat eats the cabbage. How does everything cross intact?

Short answer: Seven crossings, and the trick is move four: after delivering the wolf, the farmer brings the GOAT back.

The seven crossings

1. Take the goat over (wolf and cabbage are safe together). 2. Row back empty. 3. Take the wolf over. 4. Bring the goat BACK - this is the move every stuck solver is missing. 5. Take the cabbage over (goat waits alone on the near bank). 6. Row back empty. 7. Take the goat over. Done.

Taking the cabbage at step 3 instead of the wolf works symmetrically. What never works is refusing to let something ride back.

Why the backward move is forced

The goat is the only piece that conflicts with both others, so the goat can never be left with anyone - which means the goat must cross first and must be alone on a bank whenever the farmer is away. The only way to keep that true mid-puzzle is to bring it back.

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 - undoing apparent progress is often the only path through.

Why interviews ask it

As an interview question this is a state-space search in disguise: enumerate legal states, notice the invariant (the goat is never unsupervised with anything), and be willing to move backward. Interviewers listen for the invariant, not the memorised sequence.