The story of river-crossing puzzles

A farmer must take a wolf, a goat and a cabbage across a river. The boat holds the farmer plus just one passenger. Left alone together, the wolf would eat the goat, and the goat would eat the cabbage. How can everyone get across? The key is not only carrying things over, but also bringing something back.

Seven crossings, and the trick of bringing something back

First take the goat over. The bank left behind holds only the wolf and the cabbage, which is safe. The farmer comes back alone and takes the wolf (or the cabbage) over. Now comes the key move: bring the goat back. If it stayed, it would be left with the wolf (or the cabbage) on the far bank. Leave the goat behind, carry the cabbage (or the wolf) across, return alone, and finally take the goat over. That is 7 crossings in all. Swapping the order of the wolf and the cabbage gives another solution of the same length.

Nothing in the story forbids going back. Even so, carrying something you have just delivered all the way back again is hard to think of.

This site's program explored every arrangement reachable from the start. Only 10 are safe, with nobody eaten, and the same search confirms that 7 is the minimum.

It is in a book more than 1,000 years old

This kind of puzzle appears in a Latin collection called Propositiones ad Acuendos Juvenes (“Problems to Sharpen the Young”). Its oldest surviving manuscript dates from the later 9th century. It contains the wolf, goat and cabbage problem along with other river crossings. The book is traditionally credited to the scholar Alcuin of York, but no one knows for certain that he wrote it.

That makes it one of the oldest surviving records, which does not rule out that people played with it even earlier.

The same puzzle in different costumes

The same structure has been told with different characters at different times and places. Alcuin's book has pairs of brothers and sisters. Later it took the form of the “jealous husbands”, with couples, according to the standard account. In the late 19th century a version with two other kinds of characters appeared, and it later became a favorite of introductory AI courses. That cast can bring unwelcome stereotypes of real groups of people into a game, so this site does not use it. We keep to neutral themes.

Tales with similar shapes are said to exist in several parts of Africa, and in Japan in the saying and paintings known as “Tora no ko watashi”. The animals and foods differ, but the heart of it is the same: some things must not be left together.

The “Pilots and drones” puzzle on this site is a neutral version. The boat carries one or two pilots or drones at a time. On either bank, drones may never outnumber the pilots, whenever any pilot is present. With 2 of each the minimum is 5 crossings, and with 3 of each it is 11. The program checks both.

Turning it into a map of states

In AI, this puzzle is a classic example of solving by a “map of states”. Who is on which bank is one state, and a boat trip joins one state to another. Remove the states where something gets eaten, and what remains is finding a path from the start to the goal. It is what you do in your head, drawn as dots and lines. The puzzle page shows this map so you can see where you are on it.

How to think about it

• Look at what you leave, not only what you carry. What matters is whether the unattended bank is safe.
• Find the one in both forbidden pairs. In the wolf, goat and cabbage puzzle, the goat is in both. That is why it goes first and later comes back.
• Use backward moves. A step back can untie a deadlock.
• Check both banks. When rules apply on both sides, as with pilots and drones, check the bank you leave as well as the one you reach.

Stuck? The Hint button on the puzzle page starts with the idea and works up. The last hint shows the next move on a shortest route.