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