The missionaries () and cannibals () problem is usually stated as follows: there are three missionaries and three cannibals on the left bank of a river. They want to cross the river to the right bank. There is a boat on the left bank. The boat can hold one or two people, and it can never cross the river with zero people. If cannibals ever outnumber missionaries, the cannibals will eat the missionaries. Find a way to get everyone from the left bank to the right bank while guaranteeing no missionaries are eaten.

We define a state as a 3-tuple (m, c, b) that consists of 2 integers and 1 character where m is the number of missionaries on the left bank, c is the number of cannibals on the left bank, b can be L or R, denoting which bank the boat is. For example, the initial state is (3, 3, L); the goal state is (0, 0, R); if the boat is on the right bank of the river and there are 2 missionaries and 2 cannibals on the left bank, we use (2, 2, R) to represent this state. We assume that a search path is stopped once it meets the goal state.

There are five operations as follows:

MM: 2 missionaries cross the river

CC: 2 cannibals cross the river

MC: 1 missionary and 1 cannibal cross the river

M: 1 missionary crosses the river

C: 1 cannibal crosses the river

Draw a diagram to show all the valid and reachable states and transitions from states corresponding to all legal operations. You can see Slide03 Page 16 for an example of what your diagram should look like. [23 marks]

How many valid and reachable states are there? [2 marks]

What is the minimum time for the boat to cross the river to reach the goal? [3 marks]