/* missionaries and cannibals.  Represent a state by a tuple with
three integers (M,C,B) where M is the number of missionaries on the
left bank, C is the number of cannibals on the left bank and B is the
number of boats on the left bank. */

%:- module(mc, [start/1,goal/1,arc/2,writeState/1]).

start((3,3,1)).

goal((0,0,_)).

% there is an arc from S1 to S2 if there is a possible arc to legal state S2.

arc(S1,S2) :- possibleArc(S1,S2), legal(S2).

% possibleArc(S1,S2) iff we can go from S1 to (possibly illegal) state S2

possibleArc((M1,C1,B1),(M2,C2,B2)) :- delta(DM,DC,DB), M2 is M1+DM, C2 is C1+DC, B2 is B1+DB.

% delta(M,C,B) represents the *change* in the number of missionaries,
% cannibals and boats on the left bank of the river, respectively, for a
% given potential move.
	   
delta(2,0,1).    % MM go left
delta(1,1,1).    % MC go left
delta(0,2,1).    % CC go left
delta(1,0,1).    % M  go left
delta(0,1,1).    % C  go left
delta(-2,0,-1).  % MM go right
delta(-1,-1,-1). % MC go right
delta(0,-2,-1).  % CC go right
delta(-1,0,-1).  % M  go right
delta(0,-1,-1).  % C  go right

% legal(M,C) is true iff it is a legal state to have M missionaries
% and C cannibals on the left bank (checking of course who is then
% neccessarily on the right bank).

legal((M,C,B)) :-
	(B=0;B=1),
	legal1(M,C),
	MR is 3-M,
	CR is 3-C,
	legal1(MR,CR).

% legal1(M,C) checks one bank -- the number of missionaries and
% cannibals must be between 0 and 3 and no missiionary can be in danger.

legal1(M,C) :- M>=0, C>=0, M=<3, C=<3, (M=0;M>=C).

writeState((M,C,B)) :-
  S is 6-M-C,
  MR is 3-M,
  CR is 3-C,
  SR is 6-MR-CR,
  write('"'),
  doForN(S,write(' ')),
  doForN(M,write('M')),
  doForN(C,write('C')),
  (B=1 -> write(' |o   | ') | write(' |   o| ')),
  doForN(MR,write('M')),
  doForN(CR,write('C')),
  doForN(SR,write(' ')),
  write('"').

doForN(N,_) :- N<1,!.
doForN(N,Goal) :- call(Goal), N2 is N-1, doForN(N2,Goal).