Three missionaries and three cannibals are all on one bank of a river they wish to cross. They have a boat, which will hold two persons, but which can be rowed by one if necessary. If the cannibals ever outnumber the missionaries on a given bank, all the missionaries on that bank will be eaten. Otherwise, both parties will cooperate peacefully toward crossing the river. How can all the missionaries and cannibals be transported safely to the other bank? (b) Consider the general case in which there are m missionaries and n cannibals (m ≥ n), and in which the boat can hold p persons, but requires at least r persons to be rowed (p ≥ r).

first solve the problems that are given. Next, make a list of the subproblems you considered while solving them. Discuss how a computer might be programmed to solve each of the given problems, and how each of the problems might be represented to the computer. If you find a state-space representation for a problem, estimate the size of the state space and try to identify heuristics and algorithms the machine could use to search it. If computer time is available to you, choose a problem and try to implement a computer program that can solve it.