Cannibals and Missionaries.



The rules for this problem are as follows.

Any time more cannibals are on the same side of the river as
missionaries, the game ends in a loss.

The boat carries 1 or 2 people - no more and no less.

To change sides, the boat must have at least 1 person in it. 

Those inside the boat count as if they are on whichever side the boat
is on at the time. For example, if the boat has two missionaries in it
and the boat is on the left side, then there are at least two
missionaries on the left side. If the boat takes the missionaries over
to the right side, then there are at least two missionaries on the
right side.

At the start of the game, all cannibals and missionaries are on the
left side of the river.

The game is won when all cannibals and missionaries are on the right
side of the river.

The boat begins on the left side of the river. 



Part 1-10% Due Thursday 9/23: Draw a sample state space including arrows
between states for this problem. Think about how to encode these
things programmatically into a program.

Part 2-30% Due Tuesday 9/28: Write the successor function. It should take as
input an action and a node and produce a new node. I suggest using
something like the following:

int successor(action move, node currentnode, node &newnode);

In this setup, node and action are structs (or classes) that encode
the information you need. The return value returns 1 if the action is
valid. It returns 0 if the action could not be performed or would lead
to a failure. The newnode should still be a valid newstate even if
return is 0. For example, if the action could not be performed,
newnode contains the same state as currentnode. If the action would
lead to failure then newnode would contain the "failed" state.


Remember, a successor function doesn't solve problems. It simply
produces the next node/state given the current node/state and an
action. There should be no tree search or strategy involved in this
process. Simply a moving of the missionaries and cannibals. You may
think of the input to the successor function as a node or a state at
this point.


Part 3-60% Due Tuesday 10/5: Write the solver for the missionaries and
cannibals problem.