% mandc(CurrentState, Visited, Path)
% to run the code in iProlog, do
% % prolog mandc.pro
% : mandc(state(3,3,left), [state(3,3,left)], Path)?
% if you are looking at this with a web browser like "netscape", you can
% save a copy by selecting "Save As" from the "File" menu.
mandc(state(0, 0, right), _, []).
mandc(CurrentState, Visited, [Move | RestOfMoves]) :-
newstate(CurrentState, NextState),
not(member(NextState, Visited)),
make_move(CurrentState, NextState, Move),
mandc(NextState, [NextState | Visited], RestOfMoves).
% make_move(State1, State2, Move) builds the move(-,-,-) that gets you
% from State1 to State2.
make_move(state(M1, C1, left), state(M2, C2, right), move(M, C, right)) :-
M is M1 - M2,
C is C1 - C2.
make_move(state(M1, C1, right), state(M2, C2, left), move(M, C, left)) :-
M is M2 - M1,
C is C2 - C1.
% carry(X,Y) is true if the boat can carry X missionaries and Y cannibals.
carry(2, 0).
carry(1, 0).
carry(1, 1).
carry(0, 1).
carry(0, 2).
% legal(X, Y) is true if it is safe for the missionaries to have X
% missionaries and Y cannibals together on a river bank (left or right).
legal(X, X).
legal(3, X).
legal(0, X).
% newstate(State1, State2) is true if it is possible to get from State1
% to State2.
newstate(state(M1, C1, left), state(M2, C2, right)) :-
carry(M, C),
M <= M1,
C <= C1,
M2 is M1 - M,
C2 is C1 - C,
legal(M2, C2).
newstate(state(M1, C1, right), state(M2, C2, left)) :-
carry(M, C),
M2 is M1 + M,
C2 is C1 + C,
M2 <= 3,
C2 <= 3,
legal(M2, C2).