Wednesday, 19 September 2012

Solving “Missionaries and cannibals problem” with Prolog by using DFS and BFS

 

"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
        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).

% 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
       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).

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,[]),!.

5 comments:

  1. Thank you!
    It helped me to understand how to make BFS with Prolog :).

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

    ReplyDelete
  3. Compile everything that is bold.
    After 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,[]),!.

    ReplyDelete
  4. it says:
    " 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. "

    ReplyDelete
  5. ..../Desktop/CanMis.pl:51:52: syntax error: ) or operator expected
    1 error(s)

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

    ReplyDelete