The Missionary & Cannibals Problem

The Problem:

On 1 bank of a river are 3 missionaries and 3 cannibals. There is 1 boat available that can hold up to 2 people and that they would want to use it to cross the river. If cannibals do ever outnumber missionaries on either of the river’s edges, the missionaries will get eaten.

How can the boat be used by the missionaries and cannibals to safely carry all of them across the river?

The initial state is shown below here, where the black triangle represents the missionaries and the red circle represent cannibals.

The Solution:

This can be solved by searching for a solution i.e., which is a sequence of actions that leads from initial state to the final state.

First of all let us consider that both missionaries (M) and cannibals(C) are on the same side of the river.

Initially the positions are : 0M , 0C and 3M , 3C (B)
Now let’s send two Cannibals to left of bank : 0M , 2C (B) & 3M , 1C
Send 1 cannibal from left to right : 0M , 1C & 3M , 2C (B)
Now send remaining two Cannibals to left : 0M , 3C (B) & 3M , 0C
Send one cannibal to the right : 0M , 2C &3M , 1C (B)
Now send the two missionaries to the left : 2M , 2C (B) & 1M . 1C
Send one missionary and one cannibal to right : 1M , 1C & 2M , 2C (B)
Send two missionaries to left : 3M , 1C (B) & 0M , 2C
Send one cannibal to right : 3M , 0C & 0M , 3C (B)
Send two cannibals to left : 3M , 2C (B) & 0M , 1C
Send one cannibal to right : 3M , 1C & 0M , 2C (B)’
Send two cannibals to left : 3M , 3C (B) & 0M , 0C
Here (B) shows the position of the boat after the action is performed.
Therefore all missionaries and cannibals have now crossed river safely.
The complete search space is shown in the image below: