River Crossing Puzzle: Under Its Rules, Two Shortest Routes

Where it lands

The wolf, goat and cabbage puzzle asks how a farmer whose boat holds him and one passenger can get all three across a river, when the wolf eats the goat and the goat eats the cabbage whenever he leaves them alone together. Under those rules it can be done: we checked all 16 ways to spread the four over two banks, found 10 of them safe, and found exactly two shortest solutions, both worked out in the fold below the puzzle.

Sections on this sheet (4)

1. The puzzle
2. Ten safe arrangements out of sixteen
3. Where the puzzle comes from
4. Same rules, bigger boats

A Latin problem collection attributed to Alcuin sets a man beside a river with a wolf, a goat and cabbage. The Latin tells him to bring everything across “illaesa,” unharmed, but it never says who would harm whom, or when. Those rules have to be written down before anyone can count crossings. Here is the puzzle in standard form with our version of the missing rule, so you can try it before you open the answer.

In standard form: (our wording of problem XVIII of the Propositiones ad acuendos iuvenes)

1. P1Premise 1:The farmer, the wolf, the goat and the cabbage start on the left bank.
2. P2Premise 2:Only the farmer rows; he carries at most one of the three per crossing.
3. P3Premise 3:On a bank without the farmer, the wolf eats the goat and the goat eats the cabbage.
4. P4Premise 4:Nothing else counts as a loss; any number of crossings is allowed.
5. ? QQuestion:What is the fewest crossings that gets all four to the right bank, and in what order?

Wide figure: scroll it sideways, or open it full size.

The puzzle

The farmer stands on the left bank with a wolf, a goat and a cabbage. The only boat is small: it holds him and one passenger, and nobody else can row it. The table sets out the four rules and what each one allows.

“Shortest” in this page's title means fewest crossings, and one trip from one bank to the other counts as one crossing. Paper slips marked F, W, G and C on a sheet with a river drawn across it are enough to try it. Write down who stands on each bank after every crossing before you open the answer.

Show the checked solution

Checked solution

∴ Under these four rules, the fewest crossings is 7, and exactly two orders reach it. They are mirror images: swap the wolf and the cabbage in one and you get the other.

We checked all 16 bank arrangements. A breadth-first search, which tries every legal crossing from every arrangement it reaches, started on the left bank and found the goal after 7 crossings by exactly two routes. A second method, written separately, counted every sequence of legal crossings one length at a time, and the first length to reach the goal was again 7, with again two sequences.

Crossing	Direction	Route 1: the farmer carries	Route 2: the farmer carries
1	across	goat	goat
2	back	nothing	nothing
3	across	cabbage	wolf
4	back	goat	goat
5	across	wolf	cabbage
6	back	nothing	nothing
7	across	goat	goat

Crossing 4 is the move the decoy never considers: the farmer carries the goat back to the left bank. Without it, the third crossing leaves the goat with the wolf or with the cabbage as soon as he rows away. In knot terms, this one loosens only when you pull a strand back toward you first.

Wide figure: scroll it sideways, or open it full size.

The search also shows how little choice the puzzle leaves. The 10 safe arrangements are joined by only 10 legal crossings. On the way to the goal there is exactly one fork: after crossing 2, with the farmer back beside the wolf and the cabbage, he can carry either one.

The two branches meet again after crossing 5, closing a loop. From there he can also row back down the other branch, but that only takes him around the loop.

Wide figure: scroll it sideways, or open it full size.

The solution printed under problem XVIII in Migne's edition follows route 2, carrying the wolf on the third crossing, and it does not mention route 1.

Ten safe arrangements out of sixteen

Each of the four can stand on either bank, so there are 2 × 2 × 2 × 2 = 16 arrangements. Six of them lose something. In four, the wolf is left with the goat, and in two of those the cabbage is there as well; in the other two, the goat is left with the cabbage.

Wide figure: scroll it sideways, or open it full size.

All 10 safe arrangements can be reached from the start, and each one lies on at least one of the two shortest routes. A solver who keeps to safe arrangements has no dead end to wander into.

Searching a crossing puzzle by hand

The search behind these numbers needs no computer for a puzzle this small. It works the same way for any crossing puzzle whose rules fit on a card:

1. Write each arrangement as two lists, left bank | right bank, with the boat on the farmer's side.
2. Cross out every arrangement the rules forbid. Here that leaves 10 of the 16.
3. Start a list headed 0 that holds only the starting arrangement.
4. For each arrangement on the newest list, write down every legal crossing from it. Any arrangement that has not appeared on an earlier list goes on the next one.
5. Stop at the first list that contains the goal; its number is the fewest crossings.

To count the shortest solutions too, write a number beside each arrangement. The start gets 1, and every other arrangement gets the sum of the numbers of the arrangements on the list before that can reach it in one crossing. The number beside the goal is the count of shortest solutions.

Paper gets unwieldy fast once more travellers join: with six of them and a boat that can be on either side, the lists start from 2⁷ = 128 arrangements before any are crossed out, so the related puzzles below get the same search, run in full rather than on paper.

Where the puzzle comes from

The earliest text we read is problem XVIII of the Propositiones ad acuendos iuvenes, problems to sharpen the young. It is printed in volume 101 of J.-P. Migne's Patrologia Latina, columns 1149–1150, under the running head “Opp. dubia.” The edition files the whole collection among works of doubtful attribution, which is why this page says the collection is attributed to Alcuin and not that he wrote it.

The Latin title is “Propositio de homine et capra et lupo,” the problem of the man, the goat and the wolf. A man must take a wolf, a goat and “fasciculum cauli,” a bundle of cabbage, across a river in a boat that can carry “duos tantum ex ipsis,” only two of them. He has been ordered to bring everything over unharmed.

The Latin leaves out the rule that makes the puzzle work. It never says that the wolf eats the goat or that the goat eats the cabbage, or that either happens only when the man is away. Our P3 writes that rule down. The Latin also leaves open whether “two of them” includes the man, though the solution printed with it treats him as one of the two.

Albinus is the name Migne's edition pairs with Alcuin in its running heads: “Albini seu Alcuini,” of Albinus or Alcuin. The painting has no connection with the puzzle beyond that name. A 1992 article in The Mathematical Gazette by John Hadley and David Singmaster carries the collection's English title, “Problems to Sharpen the Young”; we have seen only its bibliographic record.

Illustration

Same rules, bigger boats

Problem XVIII sits between two other crossing puzzles. In problem XVII, three brothers each travel with a sister, the boat holds two, and the Latin says each brother desires his neighbor's sister. We read that as a rule: no sister may be with another brother unless her own brother is there too. In problem XIX, a man and a woman each weigh as much as a loaded cart, their two children together weigh the same, and the boat can carry one cartload.

The problem after that, XX, repeats problem XIX with a pair of hedgehogs and their two young, and its printed solution opens “Similiter, ut superius,” in the same way as above.

We wrote each one as rules and searched it the same way. We added a fourth puzzle, the one known as missionaries and cannibals; we have not traced it to a source we read, so its row states our rules only.

Wide figure: scroll it sideways, or open it full size.

The brothers, sisters and children are told apart, so swapping two people counts as a different order. The missionaries and cannibals row counts only how many of each kind cross each time. The solutions printed in the collection use 11 crossings for problem XVII and 9 for problem XIX, the same numbers our search gives as the minimum under our rules. In the printed solution to problem XVII, the speaker first crosses with his own sister, leaves her there and rows back alone; the other two sisters then cross together.

A river crossing can also be a fact to read rather than a puzzle to solve. Minard's map of the French army's losses in Russia, drawn by Charles Minard in 1869, labels the Bérézina river, and the black band, which his legend says stands for the men leaving Russia, crosses it. There the order of events is read from the map, not chosen.

Push back:

The strongest objection is that the two answers are really one. The rules treat the wolf and the cabbage alike, each safe with anything but the goat, so swapping their names turns route 1 into route 2, and the puzzle's real content is one insight that no count of crossings measures. We accept the mirror point, since we count different crossing orders and the fold calls the two mirror images. Whether that one insight is the whole puzzle is a disagreement the numbers cannot settle.

• Knights and Knaves: Two speakers instead of two banks; once the rules are written down, every case can be checked, including the ones with no answer.
• Tower of Hanoi: One disk moves at a time there too, and each added disk doubles the count of moves and adds one.

Sources

1. Propositiones Alcuini doctoris ad acuendos juvenes, problems XVII–XIX with their solutions, in J.-P. Migne (ed.), Patrologiae cursus completus, Series Latina, vol. 101 (Paris: J.-P. Migne), cols. 1149–1150, printed among the works of doubtful attribution (Opera dubia). https://archive.org/details/patrologiaecur101mign Read: columns 1149–1150 in Latin, with the column numbers and the running head checked on the scanned pages.
2. John Hadley and David Singmaster, “Problems to Sharpen the Young,” The Mathematical Gazette 76, no. 475 (March 1992): 102–126. doi:10.2307/3620384. https://doi.org/10.2307/3620384 Read: bibliographic record only.
3. Charles Joseph Minard, Carte figurative des pertes successives en hommes de l'Armée Française dans la campagne de Russie 1812–1813, dated on the map “Paris, le 20 Novembre 1869”; printers' lines “Autog. par Regnier, 8. Pas. Ste Marie St Gain à Paris” and “Imp. Lith. Regnier et Dourdet.” As reproduced on Wikimedia Commons, File:Minard.png (scan source not recorded). https://commons.wikimedia.org/wiki/File:Minard.png Read: the map image: the Bérézina label and the legend line on the black band; also the whole map: title, legend, every troop figure and place name, the temperature graph and the scale bar, from the full-size image.

Downloads: Both shortest solutions and the arrangement graph (JSON) (file notes: source, version and license (JSON)) · All 16 bank arrangements (CSV) (file notes: source, version and license (JSON)) · Related crossing puzzles under our rules (CSV) (file notes: source, version and license (JSON))

Cite this page