# 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.

13.2k views
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).

a. Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution. Draw a diagram of the complete state space.

b. Implement and solve the problem optimally using an appropriate search algorithm. Is it a good idea to check for repeated states?

c. Why do you think people have a hard time solving this puzzle, given that the state space is so simple?

+1 vote
by
selected by (user.guest)

The given data are

1. There are three missionaries and three cannibals on the left bank of a river.

2. They wish to cross over to the right bank using a boat that can only carry two at a time.

3. The number of cannibals on either bank must never exceed the number of missionaries on the same bank, otherwise the missionaries will become the cannibals' dinner.

4. Plan a sequence of crossings that will take everyone safely across.

For solving this, we use a 3-tuple (m, c, b) to represent the state of one side of the river, since the other side can be easily inferred. Here, m stands for the number of missionaries, c, the number of cannibals, and b, whether the boat is at this side of the river. Initially, we have the state (3, 3, 1) and the goal state should be (0, 0, 0).

State space diagram

Here, Actions are taken as

1m --- one missionary crosses the river

1c --- one cannibal crosses the river

2m ---- two missionaries cross the river

2c --- two cannibals cross the river

1m, 1c --- one missionary and one cannibal cross the river

b)

Yes, it is the good idea for the repeated states to solve the problem optimally using an appropriate search algorithm. Here, all the links in the state space are bidirectional, indicating the graph is full of cycles. However, all the cycles correspond to the case where we undo an action immediately after it is performed.

c)

Even though the state space is simple, people have a hard time solving this puzzle because most of the moves are either illegal or revert to the previous state. Also there is a feeling of a large branching factor and no clear way to proceed.

by
the image does not show
by (user.guest)
I've updated the post with the state space diagram. Thank you for the feedback and all the best in your studies :)

–1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
–1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
+1 vote
–1 vote
+1 vote
+1 vote