A brain teaser goes as follows: a farmer is returning from market, where he has bought a wolf, a goat, and a cabbage. On his way home he must cross a river by boat, but the boat is only large enough to carry the farmer and one additional item. The farmer realizes he must shuttle the items across one by one. He must be careful however, as the wolf cannot be left alone on the same side of the river as the goat (since the goat will be eaten), and the goat cannot be left alone on the same side of the river as the cabbage (since the goat will eat the cabbage).
How can the farmer arrange his trips to move the wolf, the goat, and the cabbage across the river while ensuring that no one eats the other while he’s away? The problem usually yields to an analysis by trial and error, where one of the possible solutions is found by iterating and checking the possible decisions of the farmer.
But is there a more rigorous approach that will allow us to easily find all possible solutions without having to resort to guessing and checking?
A Discrete State Space
Let’s create a three-dimensional vector that represents the state of the system. The components of this vector will be 0 or 1 depending on which side of the river the wolf, the goat, and the cabbage are. Let’s list off all possible combinations without worrying about whether something is going to get eaten – we’ll get to that later.
|(0,0,0)||Our initial state, with all three on the starting side of the river.|
|(1,0,0)||The wolf has crossed the river, but not the goat or cabbage.|
|(0,1,0)||The goat has crossed the river, but not the wolf or cabbage.|
|(0,0,1)||The cabbage has crossed the river, but not the wolf or goat.|
|(1,1,0)||The wolf and the goat have crossed the river, but not the cabbage.|
|(0,1,1)||The goat and the cabbage have crossed the river, but not the wolf.|
|(1,0,1)||The wolf and cabbage have crossed the river, but not the goat.|
|(1,1,1)||Our desired state, where all three have crossed the river.|
Now a giant list like this isn’t much help. We’ve listed off all possible states, but we can structure this in a more sensible manner which will make solving the problem much easier. Let’s allow the vectors to represent the corners of a cube, with the edges of the cube representing trips across the river. Movement along the x axis represents the wolf moving, movement along the y axis represents the goat moving, and movement along the z axis represents the cabbage moving.
Alright, that seems a bit better. What we need to do now is find an allowable path along the edges of the cube from (0,0,0) to (1,1,1), and this will represent the solution to our puzzle. First we need to remove the edges where something gets eaten.
|(0,0,0) to (1,0,0)||This moves the wolf across, leaving the goat with the cabbage.|
|(0,0,0) to (0,0,1)||This moves the cabbage across, leaving the wolf with the goat.|
|(0,1,1) to (1,1,1)||This moves the wolf across, leaving the goat with the cabbage.|
|(1,1,0) to (1,1,1)||This moves the cabbage across, leaving the wolf with the goat.|
Our allowable state space now looks like this.
The problem has simplified itself drastically. We want to go from (0,0,0) to (1,1,1) by travelling along the black (allowable) edges of this cube. We can see that if we ignore solutions where the farmer loops pointlessly, there are two allowable solutions to this puzzle.
This is a beautiful example of the simple structures that underly many of these classic riddles.