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
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.
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.
Please leave a comment below and share with other students in your network if you found this solution helpful. Happy learning!