change(e,w).
change(w,e).
move([X,X,Goat,Cabbage],wolf,[Y,Y,Goat,Cabbage]) :- change(X,Y).
move([X,Wolf,X,Cabbage],goat,[Y,Wolf,Y,Cabbage]) :- change(X,Y).
move([X,Wolf,Goat,X],cabbage,[Y,Wolf,Goat,Y]) :- change(X,Y).
move([X,Wolf,Goat,Cabbage],nothing,[Y,Wolf,Goat,Cabbage]) :- change(X,Y).

oneEq(X,X,_).
oneEq(X,_,X).

safe([Man,Wolf,Goat,Cabbage]) :-
	oneEq(Man,Goat,Wolf),
	oneEq(Man,Goat,Cabbage).

solution([e,e,e,e],[]).

solution(Config,[FirstMove|OtherMoves]) :-
	move(Config,FirstMove,NextConfig),
	safe(NextConfig),
	solution(NextConfig,OtherMoves).