Missionaries and Cannibals problem in AI

Missionaries and   Cannibals problem     is very famous      in  Artificial  Intelligence because    it was the   subject of   the first paper     that approached       problem formulation   from an analytical viewpoint.     The problem   can be stated   as follow.   Three missionaries   and three cannibals are on one side of a river, along with a boat that can hold one or two people. Now we have   to 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 another side. The above problem can be solved   by a   graph search   method.   Here   I   represent the   problem as   a   set of   states and operators. States are snapshots of the world and operators are those which transform one state into another state. States can be mapped to nodes of a graph and operators are the edges of the graph.

Missionaries and   Cannibals can be solved by using different search algorithms like Breadth first and   Depth first   search algorithm to   find the solution. The   node   of   the   graph   to   be   searched   is   represented   by  a   state   space.   Each   state space can be represent by

  State(no_of_missionaries, no_of_cannibals, side_of_the_boat)

Where       no_of_missonaries        are   the    number      of   missionaries     at   left   side   of   river, no_of_cannibals are the number of cannibals at the left side of river and side_of_the_boat is the side of the boat at particular state. For our case

                                  Initial State => State(3, 3, 0) and
                     Final State => State(0, 0, 1).

Where 0 represents left side and 1 represents right side of river. We should make a graph search which traverse the graph from initial state and find out the final state in fewest moves. There are many AI searches that search the graphs like Breadth first search, Depth first search, or iterative deepening search. Each of these different search   methods   has   different   properties   such   as   whether   a   result   is   guaranteed,   and  how much time and space is needed to carry out the search. This project uses Breadth first and Depth first search.

A move is characterized by the number of missionaries and the number of cannibals taken in the boat at one time. Since the boat can carry no more than two people at once, the only feasible combinations are:
         Carry (2, 0).
         Carry (1, 0).
         Carry (1, 1).
         Carry (0, 1).
         Carry(0, 2).
Where Carry (M, C) means the boat will carry M missionaries and C cannibals on one trip.

Once we have found a possible move, we have to confirm that it is feasible. It is not a
feasible to move more missionaries or more cannibals than that are present on one bank.
When the state is state(M1, C1, left) and we try carry (M,C) then
                 M <= M1 and C <= C1
must be true.
When the state is state(M1, C1, right) and we try carry(M, C) then
                 M + M1 <= 3 and C + C1 <= 3
must be true.