Question

N missionaries and ? > 3 cannibals are on one side of a river, along with a boat that can hold at most ? = 2? people, where 1 ≤ ? < ⌈ ? 2 ⌉. 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. Define the problem in terms of state space, transitions between them, initial state and goal. Consider only those constraints and effects that are necessary to ensure a valid solution.

Answer 1

The Missionaries and Cannibals problem is a well-known problem that is
often used to illustrate AI techniques. The problem is as follows:

Three missionaries and three cannibals are on one side of a river, with a canoe.
They all want to get to the other side of the river. The canoe can only hold one
or two people at a time. At no time should there be more cannibals than missionaries
on either side of the river, as this would probably result in the missionaries
being eaten.

To solve this problem, we need to use a suitable representation.

First of all, we can consider a state in the solving of the problem to consist
of a certain number of cannibals and a certain number of missionaries on
each side of the river, with the boat on one side or the other.We could represent
this, for example, as

3, 3, 1          0, 0, 0

Above set of numbers represents numbers of cannibals, missionaries,
and canoes on one side of the river.

Initial state is (0, 0, 0)

Goal state is   (3, 3, 1)

An example of a state that must be avoided is

2, 1, 1

Here, there are two cannibals, one canoe, and just one missionary on the
other side of the river. This missionary will probably not last very long.

To get from one state to another, we need to apply an operator. The operators
that we have available are the following:

1. Move one cannibal to the other side.
2. Move two cannibals to the other side.
3. Move one missionary to the other side.
4. Move two missionaries to the other side.
5. Move one cannibal and one missionary to the other side.

We consider rules such as this to be constraints, which limit the possible
operators that can be applied in each state. If we design our representation
correctly, the constraints are built in, meaning we do not ever need to
examine illegal states.

We need to have a test that can identify if we have reached the goal
state—3, 3, 1.

After apply above operators we get the tree which is given below. In the tree, edge represent which operator we applied.