/* File:      farmer.P
** Author(s): Jiyang Xu
** Contact:   xsb-contact@cs.sunysb.edu
** 
** Copyright (C) ECRC 1990
** 
** XSB is free software; you can redistribute it and/or modify it under the
** terms of the GNU Library General Public License as published by the Free
** Software Foundation; either version 2 of the License, or (at your option)
** any later version.
** 
** XSB is distributed in the hope that it will be useful, but WITHOUT ANY
** WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
** FOR A PARTICULAR PURPOSE.  See the GNU Library General Public License for
** more details.
** 
** You should have received a copy of the GNU Library General Public License
** along with XSB; if not, write to the Free Software Foundation,
** Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**
** $Id: farmer.P,v 1.1.1.1 1998/11/05 17:00:57 sbprolog Exp $
** 
*/

/************************************************************************/
% Here's a solution to the Farmer, Wolf, Goat/Goose, 
% Cabbage/Grain problem.  Improvements could be made by:
%
% 1.  Using a better data structure for states already
% seen, e.g. a tree, a hash table, assert, or a bit set.
%
% 2.  Using best first search.
%
% Fortunately, we can separate these concerns from the
% problem.
%
% Domain independent depth first search rules:
/************************************************************************/

go :- cputime(X0), go_iter(100), cputime(X1), X is X1 - X0,
	write('cputime: '), write(X), nl.

demo :- solve(fwgc(e,e,e,e), fwgc(w,w,w,w), Sol), write_result(Sol), fail.
demo.

demo1 :- bagof(Sol, solve(fwgc(e,e,e,e), fwgc(w,w,w,w), Sol), Solution),
	write(Solution).

go_1 :- solve(fwgc(e,e,e,e), fwgc(w,w,w,w), _), fail.
go_1.

go_iter(0) :- !.
go_iter(_) :- go_1, fail.
go_iter(N):- M is N-1,
	go_iter(M).

solve( S, G, P ) :- path( S, G, [S], P ).

path( G, G, H, H ).
path( S, G, H, P ) :- 
	move( S, N ),             	% move to a New state
	safe( N ),        		% which is legal
	not_already( N, H ),      	% and not seen before
	path( N, G, [N|H], P ).     	% then complete the path

not_already(N, H) :- already(N, H), !, fail.
not_already(_, _).			% temp solution to BA index prob

already( X, [X|_] ).
already( X, [_|L] ):-
	already( X, L ).

move( fwgc( X, W, G, C ), fwgc( Y, W, G, C ) ) :-
	 opp( X, Y ). % farmer goes alone
move( fwgc( X, X, G, C ), fwgc( Y, Y, G, C ) ) :-
	 opp( X, Y ). % farmer takes wolf
move( fwgc( X, W, X, C ), fwgc( Y, W, Y, C ) ) :-
	 opp( X, Y ). % farmer takes goat
move( fwgc( X, W, G, X ), fwgc( Y, W, G, Y ) ) :-
	 opp( X, Y ). % farmer takes cabbage

opp( e, w ).  
opp( w, e ).

safe( fwgc( X, _, X, _ ) ).
safe( fwgc( X, X, _, X ) ).

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