Farmer, Goat, Wolf, Cabbage

Music for this Song

One version of a standard puzzle called the Farmer, Goat, Wolf, Cabbage goes as follows:

• The farmer has a goat, a wolf and a cabbage .
• They come to a river (they're on left bank) and need to get to the other side (the right bank).
• There's a boat there that fits at most two of them (it's a big head of cabbage); the farmer must always be one of the two in the boat.
• If the farmer leaves the goat and cabbage on the same side of the river, when he is not present the goat will eat the cabbage (so that's not a legal state).
• Similarly, if the farmer leaves the goat and the wolf on the same side of the river, when he is not present... well, that's not legal either.

So, the problem is to find a sequence of actions that go from the initial state where they are all on the left bank to the final state when they are all on the right bank.

The state must keep track of which bank of the river everyone is on. So, a state will be:

(farmer_loc, goat_loc, wolf_loc, cabbage_loc) 

where each of these locations is 'L' or 'R' (for left or right). The boat is always with the farmer, so there is no need to keep track of that.

On any given step, the farmer can travel alone across the river, or can take one of the goat, wolf, or cabbage with him.

Define a successor function FGWC_successors and a method goal_test to allow us to use lib01's search method (which you recreated in last week's exercises) to solve this problem.

Or...

via XKCD