/* The CRAZY FARMER problem solution by JAN STROJIL, ERASMUS student, level 2 */
/* just run 'go.' 							      */


/* defines who can eat what */
can_eat(goat, cabbage).
can_eat(volf, goat).

/* tests a situation for potential danger */
unsafe(L):- 
	member(X,L),	 /* there are two members of the group */
	member(Y,L),		     
	can_eat(X,Y).	 /* one of them can eat the other */

safe(L):-
	not unsafe(L).   /* just defines safe as the opposite of unsafe */

/* this is for deleting from lists */
del(X,[X|Tail], Tail).
del(X,[Y|Tail], [Y|Tail1]):-
	del(X, Tail, Tail1).

makemove(Left, Right, NLeft, [Who, farmer|Right]):-
				/* someone called Who goes RIGHT 	*/
	del(Who, Left, NL), 	/* remove Who from left 		*/
	del(farmer, NL, NLeft),	/* remove farmer from left 		*/
	safe(NLeft).		/* check safety of situation 		*/
/* the farmer with Who are added to the RIGHT list in the head of the clause, so there is no need to insert */
	
makemove(Left, Right, [Who, farmer|Left], NRight) :-
	del(Who, Right, NR), 
	del(farmer, NR, NRight),
	safe(NRight).
	
makemove(Left, Right, NLeft, [farmer|Right]) :- /* the farmer goes RIGHT alone 		*/
	del(farmer, Left, NLeft), 
	safe(NLeft).

makemove(Left, Right, [farmer|Left], NRight) :- /* the farmer goes LEFT alone 		*/
	del(farmer, Right, NRight), 
	safe(NRight).
	
solve([],_,Been1, Been2):-  revwrite_list(Been1, Been2).
solve(Left,Right,Been1, Been2) :-
	makemove(Left, Right, NewLeft, NewRight), 
	sort(NewLeft, SortedNewLeft), 		/* need to sort the list so it can be recognised later */
	not member(SortedNewLeft, Been1), 	/* check against stack */
	solve(SortedNewLeft, NewRight,[SortedNewLeft|Been1], [NewRight|Been2]).

/* reverse print for a list to print the solution */
revwrite_list([],[]).
revwrite_list([H1|T1],[H2|T2]):-
	revwrite_list(T1,T2),
	write(H1),write(' x '),write(H2),nl.

/* the testing clause */
go:-
	write([cabbage, farmer, goat, volf]), write(' x []'), nl,
	solve([cabbage, farmer, goat, volf],[],[],[]).



/* That's it. 2001 JAN STROJIL, ERASMUS student at Staffordshire University */