How to solve river crossing puzzles

What is a river crossing puzzle?

You stand on one bank with a boat and a few passengers. The boat holds only so many. Some passengers can't be left together without you: the wolf with the goat, the goat with the cabbage. Your job is to get everyone across in as few trips as you can.

Yukti's crossings add a few twists: some passengers can row, some things won't come back once they're across, and on weight days the boat has a weight limit instead of seats.

Where does it come from?

The oldest known river crossings are in Propositiones ad acuendos juvenes, "Problems to Sharpen the Young", a collection of about fifty puzzles attributed to Alcuin of York, a scholar at the court of Charlemagne, put together around the year 800. Its oldest surviving copy is from the late 9th century.

Three of its puzzles are crossings. Problem 18 is the one everyone knows: a man must take a wolf, a goat and a bundle of cabbages across a river in a boat that holds him and one more. Problem 17 has three pairs of travellers, and nobody may be left with someone else's partner unless their own is there too. Problem 19 is about weight: a man and a woman, each as heavy as a cart-load, and two children who together weigh as much as one adult, with a boat that carries one cart-load. Yukti's weight days come from it.

How do you solve one?

Five habits do most of the work:

1. Find the troublemaker. List the unsafe pairs and see who is in most of them. In the classic, the goat is in both. That passenger usually has to travel first, and may have to travel more than once.
2. Bringing someone back is allowed. This is the step people miss. Taking a passenger back to the start is often the only way to separate a pair.
3. Check both banks after every trip. The danger is often on the bank you are leaving, not the one you arrive at.
4. Count the trips. Every crossing except the last needs a return trip, so the shortest route is usually odd: 7, 9, 11.
5. Never repeat a position. If the banks look exactly as they did two trips ago, you have gone in a circle. Yukti's solver works this way: it tries every position once and keeps the shortest path.

A worked example: the wolf, the goat and the cabbages

The boat holds you and one more. Left alone, the wolf eats the goat and the goat eats the cabbages. The shortest route is 7 crossings:

1. Take the goat across. (The wolf and the cabbages are safe together.)
2. Row back alone.
3. Take the wolf across.
4. Bring the goat back. (Otherwise the wolf and the goat are left together.)
5. Take the cabbages across. (The goat waits on the first bank, alone.)
6. Row back alone.
7. Take the goat across. Everyone is on the far bank.

Taking the cabbages at step 3 and the wolf at step 5 also works: two routes of 7. The key is step 4.

Weight days: Alcuin's problem 19

You and a friend each weigh 80 kg; two children weigh 40 kg each; everyone can row; the boat carries 80 kg. The shortest route is 9 crossings:

1. The two children cross.
2. One child comes back.
3. You cross.
4. The other child comes back.
5. The two children cross.
6. One child comes back.
7. Your friend crosses.
8. The other child comes back.
9. The two children cross.

The trick is that the light passengers bring the boat back, so each heavy crossing costs four trips.

How does Yukti help when you are stuck?

A move that would leave an unsafe pair alone is stopped, and the board says which rule it breaks. A nudge asks you a question, such as "If you take the lion, who stays behind together?". The day after, yesterday's route shows the shortest route with a reason for every step.

Sources

Read on 26 October 2026: Propositiones ad Acuendos Juvenes (Wikipedia); Wolf, goat and cabbage problem (Wikipedia); Crossing the river (E. Barbeau, University of Toronto).