Brainteasers & Logic
River Crossings & Constraint Puzzles
Overview
Crossing puzzles test systematic state-space search. The key mental move: draw states (left-bank, right-bank, boat-position) as nodes in a graph, valid moves as edges, then find the shortest path. For timed crossings, the non-obvious insight is that pairing the two slowest people TOGETHER is cheaper than sending them separately with a fast escort.
How to Recognize
- →Moving items/people across with capacity or compatibility constraints
- →'Wolf, goat, cabbage' style — some pairs cannot be left alone
- →Torch/bridge: multiple people, different speeds, minimize time
- →Any puzzle with 'get from state A to state B with rules'
Step-by-Step Approach
- 1.Draw the full state: who/what is on each side — enumerate all valid states
- 2.Torch problem key insight: pair the two SLOWEST together; this saves time vs. sending them separately
- 3.Wolf-goat-cabbage: the goat is the problem — it must never be left alone with either
- 4.When stuck: remember you can bring things BACK across
Key Formulas
Worked Examples
Problem
4 people cross a dark bridge (one torch, max 2 at once, walk at slower person's speed). Times: 1, 2, 5, 10 min. Minimize total time.
Solution
Naive: always pair with person-1 (fastest). 1+10=10, 1 back=1, 1+5=5, 1 back=1, 1+2=2. Total = 19 min.
Key insight: person 10 and person 5 will dominate total time no matter what. Force them to cross TOGETHER (cost 10) instead of separately (cost 10+5=15 with escort returns).
Optimal: (1+2 cross=2), (1 return=1), (5+10 cross=10), (2 return=2), (1+2 cross=2). Total = 17 min.
Decision rule: 'two slow together' wins if t[2nd slowest] > 2×t[fastest]. Here: 5 > 2×1 = 2. ✓
Answer
17 minutes. Pair the two slowest (5,10) together on their one joint crossing. Strategy: (1,2)→ 1← (5,10)→ 2← (1,2)→.
Common Mistakes
- !
Torch problem: thinking person 1 should always escort. This is suboptimal when the gap between slow people is larger than the gap between them and the fastest.
- !
Forgetting reverse trips are allowed. In wolf-goat-cabbage, bringing the goat back is the non-obvious but essential move.
- !
Not checking all constraint violations. List all forbidden pairs before attempting a solution.
Practice Problems
Click "Show Answer" to revealBridge crossing: speeds 1, 2, 7, 10. Torch, max 2 people, walk at slower speed. Minimum time?
3 missionaries and 3 cannibals must cross a river. Boat holds 2. On neither bank can cannibals outnumber missionaries. What is the minimum number of crossings?