%%%	Missionaries and Cannibals Problem for all solutions.  12/2003
%%%	Use of internal database to use predicates "assert" and "retract"
%%%	Constraints:
%%%	1. Cannibals cannot outnumber missionaries on either side 
%%%	   of the river.
%%%	2. Only one or two people in boat.                  
%%%	States are of the form:   state(M,C,Side) giving the
%%%	the number of missionaries and the number of cannibals
%%%	on the left side of the river along with the side of
%%%	river the boat is on.
%%%	Hence, initial state is: state(3,3,left) and
%%%	       final state is:   state(0,0,right).
%%%	nextState(State1,State2) is true if State2 can result
%%%	from State1 in just one move.
domains
	miss,cann	= integer
	state		= state (miss, cann, symbol)
	stateList	= state*
	file		= destinat
database
   	determ count(integer)	% Just in case although it did not matter.
predicates
 	solve		(stateList)
	determ pathFind	(stateList)	%Just in case
	pathWrite	(stateList)
	lastState	(stateList, state)
	nextState	(state, state)
	member		(state, stateList)
	includes	(state, stateList, stateList)
	move		(miss, cann)
	safe		(miss, cann)
	openFil
	closeFil
	run()
clauses
	count(0).
	solve(X) :- lastState(X, state(0,0,right)), 
		    pathFind(X),!.	%This Cut is useful to avoid
		      			%useless exploring next states
		      			%after the final state. 
	solve(X) :- lastState (X, LastState),
	            nextState (LastState, NextState),
	            not       (member(NextState, X)),
	            includes  (NextState, X, NewX),
	            solve     (NewX).			
	lastState ([], _)            :- !, fail.
	lastState ([Last|[]], Last).    	%% The stateList has one
						%% state right now.
	lastState ([_|Tail], State) :- lastState(Tail, State).					            
	% "includes" needs to include a NewState to the end of
	%  the current StateList.
	includes (NewState, [], [NewState])       :- !.             
	includes (NewState, [H|T],  [H|Result])   :- 
	    		includes (NewState, T, Result).	            
	nextState (state(M1,C1,left), state(M2,C2,right)) :-    			   
	  	move(M,C), M <= M1, C <= C1,
	  	M2 = M1-M,
	  	C2 = C1-C,
	  	safe (M2, C2).
	nextState (state(M1,C1,right), state(M2,C2,left)) :-
		move(M,C), 
		M2 = M1+M,
		C2 = C1+C,
		M2 <= 3,
		C2 <= 3,
		safe (M2,C2).
	safe (M,C)  :- M=C, !.
	safe (3,_)  :- !.
	safe (0,_).
	
	move (2,0).		  	
	move (1,1).
	move (1,0).
	move (0,1).
	move (0,2).
	
	member (X, [X|_])      :- !.
	member (X, [_|Tail])   :- member(X, Tail).
	pathFind(States)  :-
		retract(count(Previous)),
		Next = Previous + 1, 
		asserta(count(Next)),
		write ("\n       SOLUTION NUMBER::: ", Next, '\n'),
		pathWrite(States), !.
	pathWrite ([])    :- !.
	pathWrite ([H|T]) :-
		write (H), nl, pathWrite(T).
		
	openFil	  :-
		openwrite (destinat, "misall.out"),
		writedevice (destinat),
		write ("ALL SOLUTIONS OF MISSIONARIES PROBLEM\n").
		
	closeFil  :- closefile (destinat).
	
	run     :-  openFil,
		    InitialState = state(3,3,left),
		    solve ([InitialState]), fail.
	run	:-  closeFil.
goal    run