/* CANNIBALS AND MISSIONARIES problem solution by JAN STROJIL, ERASMUS student, Level 2 */
/* all code is mine own except for 'make_s' and 'reverse_print', where I needed some help, this is my first serious Prolog program  */
/* usage: just write 'go.' */

seznam([1,2,3,4,5,6]).

/* this makes a list of all the possible numbers of people in the boat */
make_list(0,[0]).
make_list(Count,[Count|List]):-
	Count2 is Count-1,
	make_list(Count2,List).
/* I had this first done by by listing integers up to 20 as atoms, but this is obviously more general and works for any size of the boat */


/* tests whether a situation is safe, pretty self-explanatory */
is_safe(Mw,Cw,Me,Ce):-
	(Mw >= Cw; Mw = 0),
	(Me >= Ce; Me = 0).

/* makes a move to the WEST */
move(state(Mw,Cw,Me,Ce,east), state(NMw,NCw,NMe,NCe,west), Boat_Can, Boat_Mis):-
	Me >= Boat_Mis,
	Ce >= Boat_Can,
	NMw is Mw + Boat_Mis,
	NMe is Me - Boat_Mis,
	NCw is Cw + Boat_Can,
	NCe is Ce - Boat_Can,
	is_safe(NMw,NCw,NMe,NCe). /* checks whether the new situation is safe (safe for the missionaries, anyway, it seems the cannibals can't avoid being converted to a new faith, their culture destroyed, their land taken, natural resources exploited and their children used as cheap labour force and later their story used for a hollywood movie...) */

/* makes a move to the EAST */
move(state(Mw,Cw,Me,Ce,west), state(NMw,NCw,NMe,NCe,east), Boat_Can, Boat_Mis):-
	Mw >= Boat_Mis,
	Cw >= Boat_Can,
	NMw is Mw - Boat_Mis,
	NMe is Me + Boat_Mis,
	NCw is Cw - Boat_Can,
	NCe is Ce + Boat_Can,
	is_safe(NMw,NCw,NMe,NCe).


/* this is the main procedure */

go:-	
	write('Number of missionaries? '),
	read(M),
	write('Number of cannibals? [no more than '),write(M),write(']'),
	read(C),
	M >= C,
	write('Size of the boat? [at least 2]'),
	read(SizeOfBoat),
	SizeOfBoat > 1,
	make_list(SizeOfBoat, ListOfNumbers), /* this makes a list of all the possible numbers of people in the boat */
      	solve(state(M,C,0,0,west),state(0,0,M,C,east), [state(M,C,0,0,west)], SizeOfBoat, ListOfNumbers).
/* the line above calls 'solve' with the starting position in the list of visited nodes */

/* this means a solution has been reached; the path is then printed */
solve(Goal, Goal, Been_stack, _, _) :- 
	reverse_print(Been_stack).

solve(State, Goal, Been_stack, SizeOfBoat, ListOfNumbers):- 
	member(Boat_Can, ListOfNumbers), /* gets people in the boat */
	member(Boat_Mis, ListOfNumbers),

	((Boat_Can=<Boat_Mis); (Boat_Mis=0)), /* either only cannibals in the boat or C=<M */
	Total is Boat_Can + Boat_Mis,         /* looks like I need this temporary variable */
	Total=<SizeOfBoat,                    /* checks the capacity of the boat 	*/
	Total\=0,                             /* and whether there is actually someone to row the boat*/

	move(State, New_State, Boat_Can,Boat_Mis),    /* this tries the move */
	not(member(New_State,Been_stack)),            /* this checks whether the new state has been visited before or not */
	solve(New_State, Goal, [New_State|Been_stack], SizeOfBoat, ListOfNumbers). 
/* and solve is called again with the new state added to the list of visited states */

/* this is a procedure for reverse printing of the solution path */
/* it goes all the way deep into the list and then prints the items as it "surfaces" again */
reverse_print([]).
reverse_print([Head|Tail]) :- 
	reverse_print(Tail),
	write(Head),nl.
/* if these two were swapped, it would be forward_print for a list */
mrp([]).
mrp([Head|[Head2|Tail]]) :- 
	mrp([Head2|Tail]),
	T is Head-Head2,
	write(T), nl.
mrp([Head2|Tail]) :- 
	mrp(Tail),
	write(Head2), nl.



/* That's it. 2001 Jan Strojil, ERASMUS student at Staffordshire University */
