Missionaries and Cannibals in Prolog

[Dave Colwell]

We're trying to solve the Missionaries and Cannibals problem using Prolog.  In the book, Bruce Tate shows how Prolog rocks at solving problems with well-defined rules.  The Sudoku solution was only a couple of dozen lines of code.  The standard M/C problem tells us that 3 missionaries and 3 cannibals are on one side of a river with a boat and they all need to cross to the other side.  The boat can only carry 1 or 2 people.  The cannibals cannot outnumber the missionaries on either bank or the cannibals will eat the missionaries.

I'm still working out the solution, but wanted to send out a couple of useful Prolog functions not mentioned in the book:
nl/0 sends a carriage return / new line to the standard output
write/1 will write a string to the standard output

I'll post again when I've got a solution.  Note that our next meeting is on Friday, August 5.

[Dave Colwell]

Arrrgh!

I finally proved to myself that my recursive declaration would solve a simplified Missionaries & Cannibals problem then spent the last 15 minutes cheerfully typing in the full solution.  Now I'm getting something I have no idea how to correct:

| ?- move(3,3,0,0,left,0,0,3,3).
Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ)

I'll bring my code to Book Club tomorrow morning.

Dave

[johnh]

Our best guess at the meeting was that you weren't keeping track of state and checking to see whether the current state had already been visited. As a simple example, we looked at code to determine a path through a directed graph:

 

% the graph definition:

edge(1, 5).
edge(1, 7).
edge(2, 1). edge(2, 7).
edge(3, 1). edge(3, 6).
edge(4, 3). edge(4, 5).
edge(5, 8).
edge(6, 4). edge(6, 5).
edge(7, 5).
edge(8, 6). edge(8, 7).

path(Node, Node, _, [Node]).

path(Start, Finish, Visited, [Start | Path]) :-
edge(Start, X),
\+(member(X,Visited)),
path(X, Finish, [X | Visited], Path).

 

...where Visited is the accumulating list of states, state being simply a node in the graph. The logic: there is a path from Start to Finish if it can be shown that there is an edge from Start to (unvisited node) X and a path from X to Finish.

 

This is kind of a fun program to play around with. path(1,8,[], P) will trace paths between node 1 and 8. But you can also throw in variables for the start and finish nodes and get some insight into how Prolog works.

 

 

[johnh]

Credit for the path program goes to Bill Wilson, University of New South Wales:

 

http://www.cse.unsw.edu.au/~billw/cs9414/notes/mandc/mandc.html

 

His notes not only explain the path program, but also include a missionaries and cannibals soluiton.

[johnh]

...and finally--I promise--there is a slight bug in the path program, in that it can revisit the start node.

 

Can you fix it?

[Dave Colwell]

Thanks for the information on the graph solution.  This has really helped me to understand better how to think in Prolog.  The most helpful part of the article you linked to is possibly the author's use of trace in his example.  To turn trace on, simple type trace. at the prompt.  notrace. turns it back off.  I added a fix to the subtle bug you pointed out and stepped through the execution to verify the Visited list now includes the start node.  I added this code to the existing solution:

% include the Start node when Visited is empty

path(Start, Finish, Visited, [Start | Path]) :-
edge(Start, X),
\+(member(X,Visited)),

Visited = [],
path(X, Finish, [Start, [X | Visited]], Path).