MISSIONARY CANNIBAL PROBLEM SOLUTION IN AI | BLOG |

DATE :- 09/02/2020

Both problems we have seen in the previous module were comparatively simple as there was the little
prerequisite for applying rules. To emphasize that important part, let us take two more problems which rely heavily on the prerequisites for applying a rule.

A missionary cannibal problem

Let us take our next example to reiterate our understanding of state space, the start state, the end
state, the rules and using those rules to solve the problem, especially the preconditions under which a
rule is to be applied.

 The problem is called a missionary and cannibal problem. Three missionaries and three cannibals found themselves on one side of a river. All of them have to move to the other side. The only boat available for communication can carry maximum two of them at a time. Minimum one of the travelers must come back to get the boat on the side where others are waiting. Another condition is, at no point in time, the missionaries should be less than the number of cannibals on any side of the river (otherwise they will eat those missionaries).

One of the many ways to represent the state space is as follows.

L (M1,C1) && R (M2, C2) && (BL || BR) where

(M1 >= C1 || M1 = 0),

(M2 >= C2 || M2 = 0),

M1 + M2 = 3, M1, M2  (0, 3)

C1 + C2 = 3, C1, C2  (0, 3)

L indicates left and R indicates right sides.
M1 is missionaries on the left side while C1 indicates the cannibals on the left side,
M2 and C2 indicate the same for the right side,
A total number of missionaries and cannibals must remain the same as 3 for any valid state so the
summation of M1 and M2 and C1 and C2 must be 3 for a valid state.
BL indicates boat on the left side while BR indicates a boat on the right side. We can have a boat on one side but not on both sides of the river.
The state space thus indicates that M1 missionaries and C1 cannibals are on left side of the river while M2 missionaries and C2 cannibals are on the right side of the river and boat is either on the left or the right side of the river.

One solution

L(3,3) && R (0,0) && BL -> L(3,1) && R (0,2) && BR

L(3,1) && R (0,2) && BR-> L(3,2) && R (0,1) && BL

L(3,2) && R (0,1) && BL -> L(3,0) && R (0,3) && BR

L(3,0) && R (0,3) && BR -> L(3,1) && R (0,2) && BL

L(3,1) && R (0,2) && BL -> L(1,1) && R (2,2) && BR

L(1,1) && R (2,2) && BR -> L(2,2) && R (1,1) && BL

L(2,2) && R (1,1) && BL -> L(0,2) && R (3,1) && BR

L(0,2) && R (3,1) && BR -> L(0,3) && R (3,0) && BL

L(0,3) && R (3,0) && BL -> L(0,1) && R (3,2) && BR

L(0,1) && R (3,2) && BR -> L(0,2) && R (3,1) && BL

L(0,2) && R (3,1) && BL -> L(0,0) && R (3,3) && BR