# [Prolog] Missionaries and Cannibals – M Missionaries & C Cannibals & Boat carries N passengers version

In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries). The boat cannot cross the river by itself with no people on board.

(Source: Wikipedia)

Please read [Prolog] State space search method before continuing. Here I represent the state as a list in below structure:

[Boat, Missionaries, Cannibals]

- Boat: If Boat = 0 then the boat is on the left bank, if Boat = 1 then the boat is on the right bank.
- Missionaries: Number of missionaries are currently on the right bank.
- Cannibals: Number of cannibals are currently on the right bank.

Beside the game state, we also have the game settings represented by a list with below structure:

mcproblem = [M, C, N]

- M is the total number of missionaries on both banks. In the problem statement above, M = 3.
- C is the total number of cannibals on both banks. In the problem statement above, C = 3.
- N is the maximum number that the boat can carry. In the problem statement above, N = 2.
*mcproblem*is the global variable that carry the list represents game settings.

We also make some observations:

- If there are Missionaries missionaries on the left bank, then there are M – Missionaries missionaries on the right bank. Same goes for cannibals.
- We call A is the number of missionaries that is on the boat. If the boat is moved from left to right then: Missionaries (new) = Missionaries (old) + A. If the boat is moved from right to left then: Missionaries (new) = Missionaries (old) – A. Same goes for Cannibals with B is the number of cannibals on the boat. We also have contrains: 0 <= A <= N, 0 <= B <= N, 1 <= A + B <= N.
- If the boat is on the left bank, then only missionaries or cannibals currently being on the left bank can use the boat to move to the right bank, and vice versa.
- So if Boat = 1, then missionaries can only be on boat if Missionaries > 0 (there is at least one missionary on the right bank), cannibals can only be on boat if Cannibals > 0 (there is at least one cannibal on the right bank).
- If Boat = 0, then missionaries can only be on boat if Missionaries < M (there is at least one missionary on the left bank), cannibals can only be on boat if Cannibals < C (there is at least one cannibal on the left bank).

Here we also observe that

**after**do +- A and +- B [second observation], despite whether the boat is on the left or on the right bank: 0 <= Missionaries <= M, 0 <= Cannibals <= C.

If the right bank has at least one missionary then check if they are outnumbered by cannibals, if they are then the state is not valid:

1 |
failcondition([Missionaries,Cannibals]) :- Missionaries > 0, Cannibals > Missionaries |

But we also want to check the left bank with the same fail condition:

1 |
MissionariesP is M-Missionaries, CannibalsP is C-Cannibals, not(failcondition([MissionariesP, CannibalsP])). |

Together with constraints in the third observation, we have the full condition of a valid state:

1 |
condition([Missionaries,Cannibals]) :- nb_getval(mcproblem, [M,C,_]), Missionaries >= 0, Cannibals >= 0, Missionaries =< M, Cannibals =< C, not(failcondition([Missionaries, Cannibals])), MissionariesP is M-Missionaries, CannibalsP is C-Cannibals, not(failcondition([MissionariesP, CannibalsP])). |

Before continuing, let me make an observation: If you run:

1 |
member(X, [0,1,2]). |

It will return X = 0 ; X = 1 ; X = 2.

So number A of missionaries on boat and number B of cannibals on boat can be generated through this *generate* predicate:

1 |
generate(A, B) :- nb_getval(mcproblem, [_,_,N]), range(L, 0, N), member(A, L), member(B, L), AB is A+B, 2 >= AB, AB > 0. |

And here is our f – state transfer predicate:

1 2 |
f([1,Missionaries,Cannibals], [0,MissionariesP,CannibalsP]) :- generate(A, B), MissionariesP is Missionaries-A, CannibalsP is Cannibals-B, condition([MissionariesP,CannibalsP]). f([0,Missionaries,Cannibals], [1,MissionariesP,CannibalsP]) :- generate(A, B), MissionariesP is Missionaries+A, CannibalsP is Cannibals+B, condition([MissionariesP,CannibalsP]). |

Full program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
failcondition([Missionaries,Cannibals]) :- Missionaries > 0, Cannibals > Missionaries. condition([Missionaries,Cannibals]) :- nb_getval(mcproblem, [M,C,_]), Missionaries >= 0, Cannibals >= 0, Missionaries =< M, Cannibals =< C, not(failcondition([Missionaries, Cannibals])), MissionariesP is M-Missionaries, CannibalsP is C-Cannibals, not(failcondition([MissionariesP, CannibalsP])). generate(A, B) :- nb_getval(mcproblem, [_,_,N]), range(L, 0, N), member(A, L), member(B, L), AB is A+B, 2 >= AB, AB > 0. f([1,Missionaries,Cannibals], [0,MissionariesP,CannibalsP]) :- generate(A, B), MissionariesP is Missionaries-A, CannibalsP is Cannibals-B, condition([MissionariesP,CannibalsP]). f([0,Missionaries,Cannibals], [1,MissionariesP,CannibalsP]) :- generate(A, B), MissionariesP is Missionaries+A, CannibalsP is Cannibals+B, condition([MissionariesP,CannibalsP]). s(S,E,P) :- s1(S,E,[S],P1), reverse(P1,P). s1(E,E,R,R). s1(S,E,R,P) :- f(S,X), not(member(X,R)), s1(X,E,[X|R],P). %range(L,1,3) generates [3,2,1]. range(L, Low, High) :- range1([], L, Low, High). range1(L1, [High|L1], High, High). range1(L1, L, Low, High):- Low < High, Low1 is Low+1, range1([Low|L1], L, Low1, High). |

Run the program:

1 2 |
nb_setval(mcproblem, [3,3,2]). s([1,3,3], [0,0,0], X). |