%
% Missionaries and Cannibals Puzzle -- 
%
% There are 3 missionaries, 3 cannibals, and a boat on the west bank of
% a river.  All wish to cross, but the boat holds at most 2 people.
% If the missionaries ever outnumber the cannibals on either bank of the
% river or in the boat, the outnumbered cannibals will be converted.
% Can they all safely cross the river?  If so, how?
% (The boat cannot cross empty.)
%
% state(X,Y,Z) means that X missionaries, Y cannibals, and the boat
% are on the Z side of the river.
%

set(hyper_res).
set(prolog_style_variables).

op(900, xfx, ||).
op(900, xfx, &&).

make_evaluable(_-_, $DIFF(_,_)).
make_evaluable(_+_, $SUM(_,_)).
make_evaluable(_<_, $LT(_,_)).
make_evaluable(_<=_, $LE(_,_)).
make_evaluable(_>_, $GT(_,_)).
make_evaluable(_>=_, $GE(_,_)).
make_evaluable(_==_, $EQ(_,_)).
make_evaluable(_&&_, $AND(_,_)).
make_evaluable(_||_, $OR(_,_)).

list(usable).

%  MBS - missionaries on same side as the boat
%  CBS - cannibals on same side as the boat
%  BP  - position of boat (either west or east)
%  M   - missionaries to cross
%  C   - cannibals to cross

-state(MBS,CBS,BP)   % If we have an achievable state,

 | -pick(M)          % missionaries to cross
 | -pick(C)          % cannibals to cross
 | -(M<=MBS)
 | -(C<=CBS)
 | -(M+C>0)          % if number in boat > 0,
 | -(M+C<=2)         % if number in boat <= 2,
 | -(C>=M||C==0)     % if no conversions in the boat,

	% if no conversions after the boat leaves current side,

 | -(CBS-C>=MBS-M || CBS-C==0)

	% if no conversions when the boat arrives at the other side,

 | -((3-CBS)+C >= (3-MBS)+M || (3-CBS)+C==0)

	% then a crossing can occur

 | state((3-MBS)+M, (3-CBS)+C, otherside(BP)).

% The following give the number of each that can cross.

pick(0).
pick(1).
pick(2).

-state(3,3,east).   % goal state
end_of_list.

list(sos).
state(3,3,west).    % initial state
end_of_list.

list(demodulators).
otherside(west) = east.
otherside(east) = west.
end_of_list.

