1. The missionaries and cannibals problem. Three missionaries and three cannibals are on the left river bank, with a boat that can hold one or two people. If on either side of the river or in the boat the number of cannibals exceeds the number of missionaries, the cannibals will eat the missionaries. There are no other people involved, and any use of the boat must include at least one person. Finally, after each river crossing, all persons in the boat are required to disembark the boat and step onto the river bank; thus, the requirement on the numbers of missionaries and cannibals must be satis ed after each river crossing. The problem is to nd a way for everyone to get safely from the left to the right river bank.
a. Formulate the problem precisely, and estimate the size of the state space.
b. Solve the problem optimally using an appropriate search algorithm. Is it a good idea to search for repeated states?
c. Why do you think people have a hard time solving this problem, given that the state space is so simple?