"Missionaries and cannibals problem” is well known problem in Computer Science.

The idea is the following: You have equal number of cannibals and missioners on one side of the river. You have to move them all to other side of river, by using boat. Boat can take 1 cannibal and 1 missioner or 1 cannibal and 0 missioners or 1 missioner and 0 cannibals. The problem is that at no point there should not be on some side of the river the number of missioners will be grater the number of cannibals , because missioners will convert cannibals religion (The original problem talks about a different case, when cannibals will eat missioners if there will be more cannibals then missioners, but I thing that my introduction of the problem is more ethic :) ).

This problem falls into AI (Artificial Intelligence) area which solved relatively easily with Prolog. The pattern is the following .

1. Define the “state”

2. Define now to move from state A to state B

3. Define the “Goal” state

4. Define the search , that checks all possible legal “moves” that bring from initial state to the goal

Ok. So lets define this points…

1. State I choose is to specify how many cannibals and missioners are currently on specific side of the river

I will assume that we need to move 3 cannibals and 3 missioners from the left side of the river to the right side

**s(NumOfMissioners,NumOfCannibals,RiverSide).**

2, Now we need to define **move** predicate

% move from left to right.**move(s(M1, C1, left), s(M2, C2, right),M,C) :-** % obviously we cannot move more people then we have

**M1 - M >= 0,**

C1 - C >= 0,

% calculate people on each side of the river after move

C1 - C >= 0,

**M2 is 3-M1+M,**

C2 is 3-C1+C,

M3 is M1-M,

C3 is C1-C,

% check exersize constraint

noConvertion(M2, C2),

noConvertion(M3, C3).

C2 is 3-C1+C,

M3 is M1-M,

C3 is C1-C,

% check exersize constraint

noConvertion(M2, C2),

noConvertion(M3, C3).

% move from right to left**move(s(M1, C1, right), s(M2, C2,left ),M,C) :-** % obviously we cannot move more people then we have

**M1 - M >= 0,**

C1 - C >= 0,

% calculate people on each side of the river after move

C1 - C >= 0,

**M2 is 3-M1+M,**

C2 is 3-C1+C,

M3 is M1-M,

C3 is C1-C,

% check exersize constraint

noConvertion(M2, C2),

noConvertion(M3, C3).

C2 is 3-C1+C,

M3 is M1-M,

C3 is C1-C,

% check exersize constraint

noConvertion(M2, C2),

noConvertion(M3, C3).

**move **is pretty simple . It says “I move from some state from the left side of the rivers to some state on the right side of the river.I move M missioners and C cannibals. After you move the people you have to adjust the numbers on both sides of the river and also check that there is no situation when missioners can convert cannibals”

**noConvertion** actually checks that after **move** no conversion occurred.

% to make sure that there is no conversion

% need to make sure that we have an equal number of missioners and cannibals

% or , the number of cannibals is grater then **noConvertion(X,X).noConvertion(X,Y):-Y>X ;Y=0.**

3. Goal is obvious.

**goal(s(3,3,right)).**

4. Now the search implementation.

I choose standard DFS/BSF implementation in prolog that you can find all over internet

This one for DFS

% the goal is that all peopel on the right side of the river**dephfirst(Node,[Node],_):-goal(Node).dephfirst(Node,[Node|Sol],Visit) :- sail(X,Y), move(Node, Node1,X,Y), not(member(Node1, Visit)), dephfirst(Node1, Sol, [Node|Visit]).**

and this one for BFS

% breadthfirst( [ Path1, Path2, ...], Solution):

% Solution is an extension to a goal of one of paths

**breadthfirst( [ [Node | Path] | _], [Node | Path]) :- goal( Node),!. **

**breadthfirst( [Path | Paths], Solution) :- extend( Path, NewPaths), append( Paths, NewPaths, Paths1), breadthfirst( Paths1, Solution).extend( [Node | Path], NewPaths) :- findall( [NewNode, Node | Path], ( sail(X,Y),move( Node, NewNode,X,Y), not member( NewNode, [Node | Path] ) ), NewPaths).**

You can see that implementation is straightforward. It creates a search tree for DFS or BFS for all possible options to call **move** predicate until it finds the goal.

One thing that still need to be mentioned is **sail **predicate. It actually stands for possible boat movement across the river sides.

% sail(X,Y) transfer by boat . X for missioners and Y for cannibals**sail(2, 0).sail(0, 2).sail(1, 0).sail(0, 1).sail(1, 1).**

To start the program just use

**For BFS**

*solve( s(3,3,left), Solution) :- breadthfirst( [ [Start] ], Solution0),reverse(Solution0,Solution).*

**For DFS**

*solve(3,3,Solution):-dephfirst( s(Misioners,Canibals,left), Solution,[]),!.*

Thank you!

ReplyDeleteIt helped me to understand how to make BFS with Prolog :).

Hi there. i have no idea what codes to type start. please enlighten me. Thanks!

ReplyDeleteCompile everything that is bold.

ReplyDeleteAfter this execute :

For BFS

solve( s(3,3,left), Solution) :-

breadthfirst( [ [Start] ], Solution0),reverse(Solution0,Solution).

For DFS

solve(3,3,Solution):-

dephfirst( s(Misioners,Canibals,left), Solution,[]),!.

it says:

ReplyDelete" Error 16: Instead of the atom member what is expected here is something like an infix operator or ). (line 54, after clause 10)

1 error, 0 warnings. "

..../Desktop/CanMis.pl:51:52: syntax error: ) or operator expected

ReplyDelete1 error(s)

Please help me :( I do not understand what this error is.