
/*
	Solve the Cannibals and Missionaries problem.
	3 Cannibals and 3 Missionaries must be brought across a river in
	a 2-man boat, never leaving more cannibals than missionaries on
	either side.
	
	Search for sequence of ok states, where:
		state(CL,ML,Boat,CR,MR)
	describes the number of cannibals and missionaries
	on the left/right side of the river, and Boat is 'left' or 'right'
*/

:- op(600, xfx, in).

in(X, [X|_]).
in(X, [_|S]) :- in(X, S).

not(X) :- X, !, fail.
not(_).

% append L1 and L2 to form L3
append([],L,L).
append([X|L1],L2,[X|L3]) :-		append(L1,L2,L3) .

% X is the last element of list L
last(X,L) :- append(_,[X],L).

% checks if state is ok:
ok(state(CL,ML,Boat,CR,MR)) :-
	CL >= 0, ML >= 0, safe(CL,ML),
	CR >= 0, MR >= 0, safe(CR,MR),
	Boat in [left, right].

% a state is safe if missionaries are not outnumbered:
safe(C,0).
safe(C,M) :- M>0, M>=C.

% there is a sequence of ok states from Start to Goal:
path(Start, Path, Goal) :-
	growPath(Start, [Start], Path, Goal).

% given some valid StartPath, we can find a longer Path
% to our Goal.
% base case, we have reached our Goal:
growPath(Start, StartPath, Path, Goal) :-
	StartPath = Path,
	last(Goal, Path).

% recursive case, StartPath can be extended to a LongerPath
% that will reach our Goal:
growPath(Start, StartPath, Path, Goal) :-
	extends(StartPath, LongerPath),
	growPath(Start, LongerPath, Path, Goal).

% an ok path can be extended by one transition to another ok path:
extends(OKPath, Path) :-
	last(Last, OKPath),
	canGo(Last, Next), % NB: canGo/2 checks if ok(New)
	not(Next in OKPath), % avoid cycles!
	append(OKPath, [Next], Path).

% we can go from state S0 to state S1:
canGo(S0, S1) :-
	S0 = state(CL0,ML0,Side0,CR0,MR0),
	S1 = state(CL1,ML1,Side1,CR1,MR1),
	C in [0,1,2],
	M in [0,1,2],
	C+M > 0,
	2 >= C+M,
	move(CL0, C, Side0, Side1, CL1),
	move(ML0, M, Side0, Side1, ML1),
	CR1 is 3 - CL1,
	MR1 is 3 - ML1,
	ok(S1).

% move N people from one side of the river to the other
% Old number on left side becomes New:
move(Old, N, left, right, New) :- New is Old - N.
move(Old, N, right, left, New) :- New is Old + N.

% write out all possible solutions:
soln(P) :- path(state(3,3,left,0,0), P, state(0,0,right,3,3)),
	write('SOLUTION'), nl,
	writelist(P), nl, fail.
soln(_).

solve :- soln(_).

writelist([X|L]) :- write(X), nl, writelist(L).
writelist([]).

/*
solve.
SOLUTION
state(3,3,left,0,0)
state(2,2,right,1,1)
state(2,3,left,1,0)
state(0,3,right,3,0)
state(1,3,left,2,0)
state(1,1,right,2,2)
state(2,2,left,1,1)
state(2,0,right,1,3)
state(3,0,left,0,3)
state(1,0,right,2,3)
state(1,1,left,2,2)
state(0,0,right,3,3)

SOLUTION
state(3,3,left,0,0)
state(2,2,right,1,1)
state(2,3,left,1,0)
state(0,3,right,3,0)
state(1,3,left,2,0)
state(1,1,right,2,2)
state(2,2,left,1,1)
state(2,0,right,1,3)
state(3,0,left,0,3)
state(1,0,right,2,3)
state(2,0,left,1,3)
state(0,0,right,3,3)

SOLUTION
state(3,3,left,0,0)
state(1,3,right,2,0)
state(2,3,left,1,0)
state(0,3,right,3,0)
state(1,3,left,2,0)
state(1,1,right,2,2)
state(2,2,left,1,1)
state(2,0,right,1,3)
state(3,0,left,0,3)
state(1,0,right,2,3)
state(1,1,left,2,2)
state(0,0,right,3,3)

SOLUTION
state(3,3,left,0,0)
state(1,3,right,2,0)
state(2,3,left,1,0)
state(0,3,right,3,0)
state(1,3,left,2,0)
state(1,1,right,2,2)
state(2,2,left,1,1)
state(2,0,right,1,3)
state(3,0,left,0,3)
state(1,0,right,2,3)
state(2,0,left,1,3)
state(0,0,right,3,3)

yes
*/
