Person, Goat, Wolf, and Cabbage Problem

Problem Statement:

A person with a goat, wolf, and cabbage is on one bank of the river. Given a boat as shown in the diagram. The boat is capable to carry the person and only one of the three (viz goat, cabbage, and wolf).

Conditions:

1. The person cannot leave the wolf and goat unattended on either side of the river.( if he does the wolf will eat the goat)
2. The person cannot leave the goat and cabbage unattended on either side of the river.( if he does the goat will eat the cabbage)

Is it possible to cross the river without the goat or cabbage being eaten?

 

Lets denote Person as P, Wolf as W, Goat as G, Cabbage as C in short form. If you perform combinations, we would get 16 subsets.

,, etc

The second state is when person takes the goat as shown in the below diagram.

Now identify the fatal states, for example GC-PW, WG-PC etc. In GC-PW state the goat would would eat the cabbage.

Transition Diagram:

 

The solution is left as an exercise.

Hints:

Draw a complete state transition diagram for the problem from the initial state to the final state. There are two short solutions to the problem.

Note that the final state is :

Reference:

Introduction to Automata Theory, Languages, and Computation- John E.Hopcroft, Jeffery D.Ullman.