Learning to Solve a River Crossing Puzzle

Question

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 1

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!

Answer 2

In this case, you can look at the first few moves.

You can't take the fox or the beans, and if you go solo you will come back solo and be back at the start. For the second move, if you take the goose back you are back where you started, so you come back solo. You are a long way into the puzzle by then.

Answer 3

In most of these sorts of puzzles, there is a single moment when you crack it. For this one, it's the realization that

you can bring something back. I mean, that's kind of crazy, I am trying to get everything from this bank to that bank, why would I bring anything in the wrong direction?

If it never occurs to you to

bring anything back, the puzzle seems impossible. For the first step, you know it's ok to leave the fox with the beans, and it's not ok to leave the goose with anything, so you take it, fine. Then whatever you take over next you're going to have to leave with the goose while you go back for the third thing, and that won't work. If taking the goose back occurs to you here, you've cracked the puzzle and the rest is just mechanics.

Same thing with the limited-time lights and two-people-at-time-over-a-bridge thing. Most people want to pair slow with fast, or put two slows together but the key to solving it is actually pairing the two fastest. With the liars and truth tellers it's asking one what the other would say. And so on.