Thank you for visiting this site. This article covers the oldest veteran of the logic puzzle world: “the river crossing puzzle.”
A farmer stands on a riverbank with a wolf, a goat, and a cabbage. The boat carries the farmer plus one item, no more. And whenever the farmer isn’t watching, the wolf eats the goat, and the goat eats the cabbage. How does everyone reach the far bank intact? A homely puzzle a child can play with — and yet it is among the oldest logic puzzles on record, printed in a textbook 1,200 years ago, and one of the starting points of modern AI research.
What Is the River Crossing Puzzle?
The river crossing puzzle (this version being the wolf, goat and cabbage problem) asks you to design a transport schedule under two constraints: limited carrying capacity, and forbidden pairings. The rules:
- The farmer wants to move the wolf, the goat, and the cabbage across the river
- Only the farmer can row. The boat holds the farmer plus one passenger
- On a bank without the farmer, wolf and goat must not be left alone together (the goat gets eaten)
- On a bank without the farmer, goat and cabbage must not be left alone together (the cabbage gets eaten)
The very first move reveals the puzzle’s character. Ferry the wolf first, and the goat eats the cabbage behind you. Ferry the cabbage first, and the wolf eats the goat. So the opening move is forced: take the goat. The trouble is what comes next. Whatever you carry on trip two forms a dangerous pair with the goat the moment you set it down on the far bank. This is where most people stall.
The Original, from Charlemagne’s Court Scholar
The puzzle’s provenance is astonishingly old, reaching back to 8th-century Europe. The wolf, goat and cabbage problem appears verbatim in “Propositiones ad Acuendos Juvenes” (“Problems to Sharpen the Young”), a problem collection attributed to Alcuin (c. 735–804), the English-born scholar who served Charlemagne of the Frankish kingdom.
The collection — some fifty puzzles in Latin — is regarded as the oldest surviving mathematical puzzle collection of the West. Alcuin, the leading intellect of his day and head of Charlemagne’s palace school, wrote in a letter to the emperor that he was sending “problems of arithmetic, for pleasure” — believed to be the origin of the collection. A puzzle book compiled for an emperor’s education.
Delightfully, the collection contains three river crossing problems in a row. Number 17 is the “three jealous husbands” problem: no husband tolerates his wife being with another man in his absence, and three couples must cross in a two-seat boat — a genuinely hard 11-move problem. Number 18 is our wolf, goat and cabbage. And number 19 is the “heavy husband and wife with two children”: a family must cross in a boat that carries only one adult’s weight. Same skeleton, varied constraints, presented as a set — exactly the design philosophy of a modern problem book.
Twelve hundred years ago, a teacher was using river crossings to train young minds and an emperor’s. A fact that symbolizes just how long-lived the puzzle genre is.
The Answer Is 7 Moves — the Key Is Move 4
The shortest solution takes 7 moves:
- Ferry the goat across
- Return alone
- Ferry the wolf across
- Bring the goat back
- Ferry the cabbage across
- Return alone
- Ferry the goat across
The masterstroke, of course, is move 4. The goat you worked to deliver gets deliberately hauled back to the starting bank. That apparently wasteful retreat is exactly what lets the wolf and cabbage assemble safely on the far side. There is a mirror solution carrying the cabbage at move 3 instead of the wolf — and those two are the only shortest solutions.
The important point: no solution without a retreat exists. Forbid bringing anything back, and the puzzle becomes unsolvable. Move 4 is not a desperate improvisation but the single logically forced road.
Seeing Why the Detour Is the Shortest Route
Why the retreat is mandatory becomes vivid once you draw the puzzle as a map of states.
Each moment’s situation is determined by which bank holds the wolf, goat, cabbage, and farmer: 2^4 = 16 combinations. Remove the states where the goat or the cabbage gets eaten, and only 10 safe states remain. Draw those 10 as dots and connect states reachable by one boat trip, and you find the road from start to goal is nearly a single path — with move 4’s retreat built into the middle of it.
Seen this way, the river crossing transforms from “a flash-of-insight problem” into “a shortest-path problem on a map.” And that is precisely the basic strategy for making computers solve puzzles: enumerate the states, connect them by legal moves, and search for a route from start to goal. This framework, called state-space search, became one of the foundations of artificial intelligence research.
Indeed, the AI researcher Saul Amarel’s classic 1968 paper took the river crossing’s cousin, the “missionaries and cannibals problem,” and argued that merely changing how a problem is represented changes the difficulty of the search dramatically. Ever since, river crossing puzzles have served as the first worked example of state-space search in AI and algorithms textbooks. A game AI solving chess problems, a car navigator finding a route — at the root, both are the farmer and his goat in a boat.
Whether You Can Tolerate a Temporary Retreat Decides a Plan’s Quality
The lesson this puzzle throws at daily life, I think, is that stacking up forward moves alone does not guarantee arrival.
Refactoring in software development is a move-4: temporarily breaking something that works. On a mountain, descending to round a ridge often beats climbing the slope in front of you. In careers, a temporary pay cut or step down from a title for the sake of re-education not infrequently turns out to be the long-run shortest path. An evaluation regime that demands visible gains at every step erases retreat-containing shortest routes from the option set.
The other lesson is the constraint-sorting craft of “first write out the pairings that must never share a room.” The business version of the river crossing is everywhere: tasks that cannot run concurrently on a schedule, stakeholders who derail a meeting if seated together, drug interactions, workloads that must not share a server. Just separating capacity constraints from compatibility constraints on paper makes such sequencing problems dramatically more tractable.
Variants, and How Computers Solve It
What If the Boat Carries Two?
It ends in 3 moves: (1) ferry the wolf and cabbage together, (2) return alone, (3) ferry the goat. Wolf and cabbage are a safe pair, and the goat left behind can do no harm alone. The troublemaker goat stays quarantined until the very end, so the retreat move disappears entirely. A neat example of how one extra unit of capacity dissolves the choke point even with identical constraints.
Jealous Husbands and Famous Variations
Beyond Alcuin’s three-couples version (11 moves, two-seat boat), the famous relative is missionaries and cannibals (cannibals must never outnumber missionaries on any bank). Another kin often posed is the “bridge and torch problem”: four people who take 1, 2, 5, and 10 minutes to cross must all get over with one torch, two at a time, in 17 minutes — and the key there is likewise a counterintuitive move: send the two fastest first, and send one back.
How a Computer Solves It
The standard recipe: build a graph with safe states as nodes and boat trips as edges, then run breadth-first search for the shortest path. With only 10 states, the river crossing solves instantly — but the same framework scales to state-explosion problems like Rubik’s Cube and the 15-puzzle, where pruning and heuristic search take the lead. Once you have translated a problem into states and transitions, most of the battle is over — the lesson running straight from Amarel’s paper.
Related Logic Puzzles and Paradoxes
See the traffic version of “the longest way round is the shortest way home” — Braess’s paradox, where adding a road worsens congestion; procedure design under measurement in “the 12 coins and the balance scale”; and one bit of signal saving 99 people in “the hat puzzle.”
Summary
This article covered the logic puzzle world’s oldest veteran, “the river crossing puzzle.”
The problem Alcuin set his students 1,200 years ago has a forced opening, a logically compelled retreat in the middle, and a shortest solution of exactly 7 moves — a tiny yet perfect structure. And redrawn as a map of states, a riddle that seemed to demand inspiration becomes a problem an algorithm solves mechanically. That experience — “change the representation and the difficulty changes” — is, I believe, why the river crossing has survived to the present day.
When a plan of mine bogs down, I half-jokingly ask: “is there a move where I bring the goat back?” The move that looks like retreat may be the only way forward.
To return to the full list of logic and probability puzzles, follow the link below.
Thank you for reading. We hope to see you in the next article.
📚 Series: Logic & Probability Puzzles (6/11)
