The missionaries and cannibals problem is usually stated as follows. Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place. This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).

1. Formulate a search problem. And define the search state space appropriately to ensure a valid solution.
2. Draw a diagram of the complete state space.
3. Solve the Missionaries and Cannibals problem by the graph search algorithm BFS. Show fringe and the closed set in each iteration.
4. Solve the Missionaries and Cannibals problem by the graph search algorithm DFS. Show fringe and the closed set in each iteration.
5. Why do you think people have a hard time solving this puzzle, given that the state space is so simple?