%
% 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(binary_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.