2.2

# The wolf, the goat and the cabbage

Puzzles go back centuries. One of the most well-known puzzles is the ‘wolf, the goat and the cabbage’ puzzle that dates back to at least the 9th century. Known also as the ‘fox, chicken and grain puzzle’, ‘the fox, goose and bag of beans puzzle’, ‘the panther, pig and porridge puzzle’ and many other versions, it can be found in many folklores from Africa, to Asia, to Europe, America and Australia.

The puzzle is as follows. A farmer goes to market and buys a wolf, a sheep and a cabbage. On his way home, he has to cross a river by boat from one side to the other. The boat can carry only the farmer and one other thing - the wolf, the goat or the cabbage, so the farmer will need to make a few trips to boat all three over to the other side. During the boating, he will always have to leave two things on their own on the banks of the river. For obvious reasons, the wolf cannot be left alone with the goat - he will devour it. The goat cannot be left with the cabbage, because she will eat it. How then, can the farmer transfer all three to the other side of the river, leaving them all intact?

## The wolf, the sheep and the cabbage - solution

Obviously, the farmer should first take the goat over, leaving the wolf with the cabbage. He then returns alone to boat over either the cabbage or the wolf. It really doesn’t matter which. Let’s assume that he takes the wolf. He cannot leave the wolf with the goat while he returns for the cabbage, so he leaves the wolf and carries the goat back to the original bank with him. He leaves the goat and picks up the cabbage, boating it over and leaving it on the far-side bank with the fox. Finally, he returns alone to transport the goat over to the other bank.

## Discussion

This so-called ‘river crossing’ puzzle is an algorithmic puzzle. It asks us to find an algorithm that solves a given problem.

There are many variations on the wolf, goat and cabbage puzzle. Here is one variation. Can you solve it? Post your solutions in the comments! You are also encouraged to post your own variations on this puzzle for all of us to try and solve.

A farmer has to take across a river a fox, a chicken, a caterpillar and a cabbage. The boat can hold the farmer and two extra things. The fox cannot be left with the chicken, the chicken cannot be left with the caterpillar and the caterpillar cannot be left with the cabbage. How can he transport everything to the other bank, leaving all intact?