Minesweeper
Brain Teasers Play now
River crossing puzzles are transport logic problems where you move a group across a river in a small boat without ever leaving a forbidden pair alone. They go back to at least the 9th century, when Alcuin of York recorded the wolf-goat-cabbage riddle.
A set of characters or items must cross a river in a boat that holds a limited number, often just the ferryman plus one passenger. Everyone starts on the same bank, and the boat can't cross empty when something needs to come back.
Some combinations can't be left alone on a bank without a guardian. In the classic version the wolf eats the goat and the goat eats the cabbage if left together, so those pairs must never be unsupervised.
You make trips back and forth, sometimes carrying an item backward to keep the banks safe. The puzzle is solved when everyone has reached the far bank with no forbidden combination ever left alone.
In the wolf-goat-cabbage puzzle the goat conflicts with both of the others, so it has to cross first and shuttle back later. Find the item that appears in every conflict and build your plan around it.
The key idea is that you sometimes ferry an item back to the starting bank. Refusing to ever undo a crossing is exactly what makes the puzzle feel impossible.
A move is only legal if neither the bank you leave nor the bank you reach holds a forbidden pair. Check both sides before you commit to a crossing.
Picture the last safe trip that lands everyone across, then work out what state must come before it. Meeting in the middle from start and finish cuts the search down a lot.
Take the goat over first and return empty. Take the wolf over and bring the goat back. Leave the goat, take the cabbage over, then return for the goat. That's seven crossings in all.
The wolf-goat-cabbage version appears in a manuscript attributed to Alcuin of York from around 800 AD, so it's well over 1,200 years old.
It's a harder variant. Three missionaries and three cannibals cross in a two-seat boat, and the cannibals must never outnumber the missionaries on either bank. It takes eleven crossings.
They're textbook examples of state-space search. Each arrangement of the banks is a state, and solving the puzzle means finding a valid path between states. That's the core of many AI search algorithms.