Cannibals And Missionaries Game

| Posted on by

  1. Cannibals And Missionaries Game Download Pc
  2. Cannibals And Missionaries Game
  3. Cannibals And Missionaries Game For Android
  4. Cannibals And Missionaries Game
  5. Cannibals And Missionaries Game Download

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 and the boat, if there are missionaries present on the bank (or the boat), they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries). Cannibals and missionaries game c# implementation. abatar1/CannibalsAndMissionaries. Dismiss Join GitHub today. GitHub is home to over 50 million developers working together to host and review code, manage projects, and build software together.

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.

Cannibals and missionaries game solution

(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:

  1. If there are Missionaries missionaries on the left bank, then there are M – Missionaries missionaries on the right bank. Same goes for cannibals.
  2. 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.
  3. 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:

MissionariesP isM-Missionaries,CannibalsP isC-Cannibals,not(failcondition([MissionariesP,CannibalsP])).

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

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

And here is our f – state transfer predicate:

2
4
6
8
10
12
14
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 isM-Missionaries,CannibalsP isC-Cannibals,not(failcondition([MissionariesP,CannibalsP])).generate(A,B):-nb_getval(mcproblem,[_,_,N]),range(L,0,N),member(A,L),member(B,L),AB isA+B,2>=AB,AB>0.
f([1,Missionaries,Cannibals],[0,MissionariesP,CannibalsP]):-generate(A,B),MissionariesP isMissionaries-A,CannibalsP isCannibals-B,condition([MissionariesP,CannibalsP]).
f([0,Missionaries,Cannibals],[1,MissionariesP,CannibalsP]):-generate(A,B),MissionariesP isMissionaries+A,CannibalsP isCannibals+B,condition([MissionariesP,CannibalsP]).
s(S,E,P):-s1(S,E,[S],P1),reverse(P1,P).
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,L,Low,High):-Low<High,Low1 isLow+1,range1([Low|L1],L,Low1,High).

Run the program:

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

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

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

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

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:

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

Full program:

Cannibals And Missionaries Game

Cannibals And Missionaries Game

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

Cannibals And Missionaries Game Download