Missionaries and cannibals problem in AI

 

Missionaries and cannibals problem in AI

Three missionaries and their three cannibals are present on one side of a river and need to cross the river. There is only one boat available.

At any point, the number of cannibals should not outnumber the number of missionaries at that bank.

Only two persons can occupy the boat available at a time. Here, Missionary is denoted by 'M' and cannibal by  'C'.

Rules of the problem:

1.    (0, M): One missionary sailing the boat from bank-1 to bank-2.

2.    (M,0): One missionary sailing boat from bank-2 to bank-1.

3.    (M, M): Two missionaries sailing the boat from bank 1 to 2.

4.    (M, M): Two missionaries sailing the boat from bank 2 to 1.

5.    (M, C): One missionary & one cannibal sailing the boat from bank 1 to 2.

6.    (C, M): One missionary & one cannibal sailing the boat from bank 2 to bank 1.

7.    (C, C): Two cannibals sailing the boat from bank-1 to bank-2.

8.    (C, C): Two cannibals sailing the boat from bank-2 to bank-1.

9.    (0, C): One cannibal sailing the boat from bank-1 to bank-2.

10.    (C,0): One cannibal sailing the boat from bank-2 to bank-1.

After the application of rules	Person in the river bank -1	Person in the river bank -2	Boat Position
Start state	M, M, M, C, C, C	0	Bank-1
5	M, M, C, C	C, M	Bank-2
2	M, M, M, C, C	C	Bank-1
7	M, M, M	C, C, C	Bank-2
10	M, M, M, C	C, C	Bank-1
3	M, C	C, C, M, M	Bank-2
6	M, C, M, C	C, M	Bank-1
3	C, C	C, M, M, M	Bank-2
10	C, C, C	M, M, M	Bank-1
7	C	C, C, M, M, M	Bank-2
10	C, C	C, M, M, M	Bank-1
7	0	M, M, M, C, C, C	Bank-2