strategy - Learning to Solve a River Crossing Puzzle

I have seen many variations of the following puzzle:

Once upon a time, a farmer went to the market and purchased a fox, a goose, and a bag of beans. On his way home, the farmer came to the bank of a river and rented a small boat. The boat was so small that the farmer could carry only himself and a single one of his purchases - the fox, the goose, or the bag of the beans.

The farmer knew that if he left the fox and the goose together, the fox would eat the goose. Likewise, if left alone with the beans, the goose would eat them.

The farmer was able to get all of his purchases safely across the river. How did he do it?

I know that the solution is:

1. Take the goose across, come back empty.


2. Take the beans across, bring the goose back.


3. Leave the goose on the bank, take the fox across, come back empty.



4. Take the goose across.

(The fox and beans are interchangeable).

My question is this:
When given a problem in this format, what is the best way to begin solving it?

Answer

The quickest way may be by some form of intelligent trial and error, but there is one systematic method which will always work, and that is to translate the problem into the language of graph theory.

Start by making a complete list of all possible configurations of people and items. In this case, the boat will always be together with the farmer, so there are four objects, and \$2^4=16\$ possible configurations.

Cross out all configurations where something will be eaten, and number the remaining configurations. Here, six configurations are forbidden, leaving us with ten, which I describe by what is found on the left (original) river bank: $$1 : (M,F,G,B) \qquad 2: (M,F;G)\qquad 3:(M,F,B)$$ $$4 : (M,G;B)\qquad 5:(M,G) \qquad 6:(F,B)$$ $$7:(F)\qquad 8:(G)\qquad 9:(B)\qquad 10:(none)$$ I'm using the letter M for the farmer, who is described as "he", in order to avoid confusion with the fox (F).

Now we will make a graph with 10 nodes, where each node is one of the configurations above. Two nodes will be connected by an edge if and only if it is possible to get from one configuration to the other with a single boat trip.

Here, node 1 will be connected to node 6, and node 2 will be connected to node 7 and to node 8. We find that node 3 will be connected to three nodes; node 6, node 7, and node 9. Node 4 will be connected to node 8 and node 9, and node 5 will be connected to node 8 and node 10. Going through the remaining nodes 6 - 10, we find no new connections (the farmer has to return from the other river bank, resulting in one of the configurations 1 - 5).

The next step is to make a drawing of this graph. My computer abilities are very limited, but you should get something like this:

        7--2
       /    \
1--6--3      8--5--10
       \    /
        9--4

where you are allowed to go from node 3 to either 7 or 9, and from 2 or 4 to node 8.

Finally, we return to the original question, which can now be interpreted as: Find a path in our graph starting at node 1 and ending at node 10. The two solutions are immediately apparent!