Example 1 : Missionaries and Cannibals Problem

N (where N>=1) missionaries and N cannibals arrive on the left bank of a river. They have a rowing boat with them. The boat will be used for transporting them across the river to the right bank. Each of them know how to row but there are two constraints:
The boat, which requires one person to row, cannot carry more than two persons at a time; and
If the number of missionaries on a bank is one or more, the number of cannibals on that bank cannot be more than the number of missionaries on that bank.
How are the missionaries and the cannibals to be transported across the river?


To set up the state space of this problem we must find a suitable formal representation of:

State – triple <α1,α2,α3>, where
α1 – persons on the left bank;
α2 – persons on the right bank;
α3 – boat position (L – boat is on the left bank; R – boat is on the right bank);
If m denote missionaries, c – cannibals, the initial state is and the final state is <0,NmNc,R>.


To set up the state space of this problem we must find a suitable formal representation of:
Moves


There are five alternative moves:
1m – send one missionary in the boat to sail
2m – … two missionaries…
1m1c – … one missionary and one cannibal…
1c – … one cannibal…
2c – … two cannibals…