A farmer needs to carry a wolf, goat, and a cabbage across a river.
He has only one small boat, which can carry the farmer and only one object.
He can cross the river repeatedly.
However if the farmer is on the other shore, the wolf will eat the goat,
and similarly, the goat will eat the cabbage.
We can describe each state by listing what is on each shore.
For example, we can use the pair (FG | WC) for the state where the farmer and goat
are on the first shore and the wolf and cabbage are on the other shore.
[The symbol 0 is used when nothing is on a shore, so that (FWGC | 0) is the initial state.]
(a) Find all allowable states of the puzzle, where neither the wolf and the goat
nor the goat and the cabbage are left on the same shore without the farmer.
(b) Construct a graph such that each vertex of this graph represents an allowable state
and the vertices representing two allowable states are connected by an edge
if it is possible to move from one state to the other using one trip of the boat.
(c) Find 2 different solutions of the puzzle, each using seven crossings.