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.

Answer 4

A large language model like GPT can solve it systematically too. I know of two ways, one being based on using the LLM to help you with the programming details of the accepted solution using mathematical graphs discussed above. The discussion above left out some steps as an "exercise for the reader" like finding all the combinations of 4 choose 4, 4 choose 3, etc, and crossing out the disallowed states. This is where using GPT to write the python code to do all the work is helpful.

Drawing the graph is tricky too, and an additional helpful insight I can give you now is that the (M) appears and disappears in strictly alternating fashion in the solution, when you trace the graph execution from the starting node to the end node. This reflects the fact that the man must sail the boat to the opposite landmass to move any of the goods, resulting in all possible solutions showing that the man appears and disappears alternately from the left landmass. This insight helps eliminate lots of invalid possibilities, dramatically reducing the search space. I won't solve it with the LLM with graph math though right now, maybe later to demonstrate.

Instead I have solved this problem a whole different way by prompt engineering the LLM ChatGPT as follows in the link to openai.com

https://chat.openai.com/share/3534daf3-357e-4e09-9cac-ff2e86a84daf

Basically I told ChatGPT to create a voting group of 3 expert people and decide what to do stepwise. It works. I used ChatGPT4. I achieved success in ChatGPT4 first. It might also work in ChatGPT3.5 as well as API GPT3.5 (not chat) as because, like a Markov Chain, the state of the situation at the end of each step is all that matters. This way there is less burden on token memory size. I expect (unproven yet) that this design will let me call the API repeatedly until it reaches goal state. The way I solved it first, though, is one call to chatGPT4 which then keeps going, except for me telling it to continue a few times, all the way until it is solved.

I give you a copy of my prompt here. You can go look at the link above to see what happened next.

The problem: (Seashore has {fox,carrot,farmer,boat,goat}. Island has {}.) is the current state, which means that a farmer is standing on the seashore with his goat and carrot, and there is also a fox here, which wants to eat the goat. The farmer's presence prevents the goat from eating the carrot and the fox from eating the goat. If the farmer leaves the goat and the carrot together alone then the goat would eat the carrot. Similarly the fox would eat the goat if the farmer is not there with them. The farmer wants to sail the boat that is currently on the seashore, to take his goat and his carrot to the island, which is his final goal. The farmer's final goal is the state described by (Seashore has {fox}. Island has {goat,carrot}) and we do not care where the boat and farmer are at the final goal state, that is, the Island or Seashore are satisfactory locations for them at the final goal state. We need to find a way to achieve the final goal for the farmer. The farmer is the only one who can sail the boat. The boat is only big enough to hold up to 1 additional item, that is, fox, carrot, or goat, at the same time besides the farmer. The boat is the only way for an item to travel between seashore and island (no swimming, flying, etc).

The solution procedure: Let's think about this step by step, explaining our thinking as we go. We will always state exactly where the fox, carrot, goat, boat, and farmer are after every step is executed, either on the seashore or the island in the following format as an example: (Seashore has {fox,carrot}. Island has {farmer,boat,goat}.) Imagine we have three different experts who are collaboratively solving this problem. All experts will share with the other experts, their own preliminary plan for the next step only but they might have a sequence of steps to achieve the final goal secretly in mind however. Next, every expert will criticize or support the preliminary plan for the next step only of the other experts, but we will not yet actually execute the plan until after the vote. The three experts will vote to decide which expert's plan for next step to actually take: The plan with the majority vote will be agreed on by all as the actual step to be taken. After the vote is decided, the single chosen plan for the step will be executed, and after this one step's activities occur, we will state exactly where the fox, carrot, goat, boat and farmer are after the step is taken in the following format as an example: (Seashore has {fox}. Island has {carrot,farmer,boat,goat}.) If the state is not the goal state, then the stepwise cycle begins again, that is, each of the experts will formulate and announce their preliminary plan for one next step, criticize the other one-step plans, vote, collectively choose, execute a step, etc. Minimal commentary by the experts will be written during stepwise processing, limiting their words to the bare minimum needed to communicate each expert's preliminary plan, the criticism, the results of the collective vote, the step that is executed, and the outcome of the step in terms of the state of what items are now on the Island and the Seashore. The state must always indicate location of all five elements fox,carrot,goat,farmer,boat as being on Island or Seashore. Every expert must consider or review the state after a step, and look for problems to avoid and reconsider the plan, like goat and carrots being together without farmer present, or fox and goat without farmer. Keep in mind that for example when the farmer sails the boat to take the goat to the island, the farmer and the goat and the boat will resultingly appear in the Island state, such as State: (Seashore has {fox, carrot}. Island has {goat,farmer,boat}.) Note that the farmer and boat always move together, that is, appear together on either Island or Seashore, since the farmer cannot move without the boat, and the boat cannot move without the farmer. This means the following is an example of a disallowed state: (Seashore has {fox, carrot, farmer}. Island has {goat,boat}.)