River-Crossing and Bridge-Torch Problems
Model every crossing as a move in a state graph and the puzzle becomes a search for a path, whether the constraint is safety (nothing gets eaten) or speed (minimise total time).
Prerequisites: How to Attack a Brainteaser
Puzzles about ferrying items across a river, or people across a bridge with one torch, look like logistics trivia, but they're really state-space search problems: a "state" is who's on which bank (and where the boat or torch currently is), a "move" is a legal crossing, and the puzzle asks either whether a safe path from start to goal exists, or which path is fastest.
Worked example: the bridge and the torch
Four people need to cross a bridge at night. They have one torch, and the bridge can only hold at most two people at a time crossing together, always carrying the torch. The four cross at speeds of 1, 2, 5, and 10 minutes respectively; a pair crossing together moves at the slower person's pace. What is the minimum total time for all four to cross?
The tempting but wrong plan. Send the fastest person (1) back and forth as an escort: crosses out (2 min, escorted by 1), 1 returns (1 min), crosses (5 min), 1 returns (1 min), crosses (10 min). Total: minutes.
The better plan: send the two slowest together. Cross (2 min). Send 1 back (1 min). Cross together — since they're both already on the starting side, pair them so the expensive 10-minute trip only happens once (10 min, the pace of the slower). Send 2 back (2 min). Cross again (2 min). Total: minutes.
Why pairing the two slow people together wins. Each of the two slowest people has to cross exactly once, and every crossing they're part of costs at least their own time. The 19-minute plan makes the 10-minute person cross paired with the escort, but also separately burns time shuttling the escort around the 5-minute person. The 17-minute plan crosses the two slow people together in a single 10-minute trip, "hiding" the 5-minute cost inside the 10-minute cost instead of paying for it twice.
Model the puzzle as states (who and what is on which side) and legal transitions (who's allowed to move together). For minimisation puzzles specifically, look for moves that let an expensive item "absorb" another expensive item's cost by travelling together, rather than paying for each separately.
For safety-constrained crossings (a fox, a chicken, and grain, none of which can be left alone with another), draw the state graph explicitly — states are which combination of items sits on the starting bank — and just search it. There are usually fewer than a dozen reachable states.
Minimum-time river crossings are a small, hand-solvable instance of scheduling and bin-packing: whenever fixed-capacity resources (a bridge, a compute cluster, a settlement batch) move a mix of fast and slow jobs, the same instinct — batch the slow ones together rather than paying escort overhead per job — shows up in production job scheduling.
Related concepts
Practice in interviews
Further reading
- Winkler, Mathematical Puzzles: A Connoisseur's Collection