River Crossing

River Crossing is a family of classic logic puzzles where the player must transport a group of characters or objects across a river using a boat with limited capacity, subject to specific constraints. Certain combinations of passengers cannot be left alone together on either bank — for example, a wolf would eat a goat, or a goat would eat cabbage. The player must find a sequence of boat trips that safely moves everyone across without violating any constraint.

Rules (Classic Wolf, Goat, and Cabbage)

1. A farmer must transport a wolf, a goat, and a cabbage across a river.
2. The boat can carry only the farmer and one other item at a time.
3. The farmer must be in the boat for every crossing (the boat cannot cross on its own).
4. The wolf and the goat cannot be left alone together (the wolf would eat the goat).
5. The goat and the cabbage cannot be left alone together (the goat would eat the cabbage).
6. The wolf and the cabbage can be left alone together safely.
7. The goal is to get all four (farmer, wolf, goat, cabbage) to the other side.

Solution (Classic Puzzle)

1. Farmer takes the goat across.
2. Farmer returns alone.
3. Farmer takes the wolf across.
4. Farmer brings the goat back.
5. Farmer takes the cabbage across.
6. Farmer returns alone.
7. Farmer takes the goat across.

Total: 7 crossings.

Common Variants

• Missionaries and Cannibals: 3 missionaries and 3 cannibals must cross; cannibals can never outnumber missionaries on either bank.
• Jealous Husbands: 3 couples must cross; no woman can be on a bank with another man unless her husband is present.
• Bridge and Torch: 4 people cross a bridge at night with one flashlight; only two can cross at a time; each person walks at a different speed; the pair moves at the slower person's pace.
• Larger Groups: Extended versions with more characters and more complex constraint graphs.

Strategies

• Identify the Critical Constraint: Determine which character or item causes the most conflicts. In the classic puzzle, the goat conflicts with both the wolf and the cabbage, making it the key piece to manage.
• The Shuttle Technique: Sometimes you must bring an item back to the starting side to resolve a conflict. This counterintuitive "backward" move is often the key insight.
• Think in States: Represent each possible configuration of items on both banks as a "state." The puzzle becomes finding a path through valid states from the start to the goal.
• Minimize Crossings: The optimal solution uses the fewest possible crossings. For the classic puzzle, 7 crossings is optimal.
• Conflict Graph: Draw a graph of which items conflict. The item with the most conflicts usually needs the most careful handling — often it must travel first and may need to be shuttled back.
• Work Backward: Sometimes it helps to think about what the final few crossings must look like and work backward to determine earlier moves.

River crossing puzzles are among the oldest known logic puzzles, with the earliest recorded version appearing in the medieval manuscript "Propositiones ad Acuendos Juvenes" (Problems to Sharpen the Young), attributed to Alcuin of York around 800 CE. Alcuin was an English scholar and advisor to Emperor Charlemagne, and his collection included the wolf, goat, and cabbage problem along with several other mathematical puzzles. This makes river crossing puzzles over 1,200 years old.

The "Missionaries and Cannibals" variant emerged in the 19th century and became a standard problem in artificial intelligence research in the 20th century. It was one of the first problems used to demonstrate state-space search algorithms. In 1968, Amarel used it as a case study for problem representation in AI, showing how the choice of representation dramatically affects the difficulty of finding a solution. The problem has since appeared in countless AI textbooks.

The "Bridge and Torch" problem gained popular fame when it became a well-known interview question at technology companies in the late 1990s and 2000s, particularly at Microsoft. It challenges candidates to optimize the total crossing time when individuals have different speeds — a fundamentally different challenge from the constraint-satisfaction nature of the classic river crossing.

River crossing puzzles have endured for over a millennium because they teach fundamental problem-solving skills: breaking a complex situation into states, identifying constraints, considering counterintuitive moves (bringing something back), and systematically exploring possibilities. They appear in recreational mathematics books, computer science curricula, and puzzle collections worldwide. Their narrative framing — a farmer, a river, hungry animals — makes abstract logic feel concrete and memorable.