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
m --- one missionary crosses the river
c --- one cannibal crosses the river
mm ---- two missionaries cross the river
cc --- two cannibals cross the river
mc --- 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.