% Source: http://www.cs.kuleuven.ac.be/~dtai/prototypes/dppd/missionaries.html
go(Res) :- search(s(s(s(0))),s(s(s(0))),west,
	[state(s(s(s(0))),s(s(s(0))),west)],Res).

search(0,0,Boat,Result,Result).
search(WM,WC,east,History,Result) :-
	move_boat_west(WM,WC,NWM,NWC),
	safe(NWM,NWC),
	\+(loop(NWM,NWC,west,History)),
	search(NWM,NWC,west,[state(NWM,NWC,west)|History],Result).
search(WM,WC,west,History,Result) :-
	move_boat_east(WM,WC,NWM,NWC),
	safe(NWM,NWC),
	\+(loop(NWM,NWC,east,History)),
	search(NWM,NWC,east,[state(NWM,NWC,east)|History],Result).

safe(s(s(s(0))),WestCann) :- \+(gt(WestCann,s(s(s(0))) )).
safe(0,WestCann) :- \+(gt(WestCann,s(s(s(0))) )).
safe(W,W) :-  \+(ge(0,W)), \+(ge(W,s(s(s(0))) )).

loop(WestMiss,WestCann,Boat,History) :-
	member(state(WestMiss,WestCann,Boat),History).

move_boat_east(WestMiss,WestCann,NewWestMiss,NewWestCann) :-
	plus2(NewWestMiss,WestMiss), NewWestCann = WestCann.
move_boat_east(WestMiss,WestCann,NewWestMiss,NewWestCann) :-
	plus1(NewWestMiss,WestMiss), NewWestCann = WestCann.
move_boat_east(WestMiss,WestCann,NewWestMiss,NewWestCann) :-
	plus1(NewWestMiss,WestMiss),
	plus1(NewWestCann,WestCann).
move_boat_east(WestMiss,WestCann,NewWestMiss,NewWestCann) :-
	NewWestMiss = WestMiss, plus1(NewWestCann,WestCann).
move_boat_east(WestMiss,WestCann,NewWestMiss,NewWestCann) :-
	NewWestMiss = WestMiss, plus2(NewWestCann,WestCann).

move_boat_west(WestMiss,WestCann,NewWestMiss,NewWestCann) :-
	plus2(WestMiss,NewWestMiss), NewWestCann = WestCann.
move_boat_west(WestMiss,WestCann,NewWestMiss,NewWestCann) :-
	plus1(WestMiss,NewWestMiss), NewWestCann = WestCann.
move_boat_west(WestMiss,WestCann,NewWestMiss,NewWestCann) :-
	plus1(WestMiss,NewWestMiss), plus1(WestCann,NewWestCann).
move_boat_west(WestMiss,WestCann,NewWestMiss,NewWestCann) :-
	NewWestMiss = WestMiss, plus1(WestCann,NewWestCann).
move_boat_west(WestMiss,WestCann,NewWestMiss,NewWestCann) :-
	NewWestMiss = WestMiss, plus2(WestCann,NewWestCann).

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).


gt(s(X),0).
gt(s(X),s(Y)) :- gt(X,Y).

ge(0,0).
ge(s(X),0).
ge(s(X),s(Y)) :- ge(X,Y).

plus1(X,s(X)).
plus2(X,s(s(X))).