/*
  The Cabbage, Goat, Wolf problem, take 2.  A state is now described
  by a list which allows us to take advantage of the predicate member
  already defined in SWI Prolog.
  
  Note the formulation of the operators, which return a new state
  (second argument of move/3) and also the description of what has
  been moved where (third argument).  Recall that a successful search
  should return the sequence of operators that generated the goal
  state starting from the initial state.
*/

% A state in the problem is represented by a list 
% [Boat,Cabbage,Goat,Wolf], in which the four variables can 
% take the values "north" or "south."

% the call would be: 
% :- moves([north,north,north,north], [south,south,south,south], R), write(R), fail.

% Moving around
% move(+AState,-AnotherState,-Move).

% first, attempt to move the cabbage: 
move([B,B,G,W],[B1,B1,G,W], moved(cabbage,B,B1)) :- opposite(B,B1).

% then, the goat: 
move([G,B,G,W],[G1,B,G1,W], moved(goat,G,G1)) :- opposite(G,G1).

% or the wolf: 
move([W,B,G,W],[W1,B,G,W1], moved(wolf,W,W1)) :- opposite(W,W1).

%... eventually, move the empty boat: 
move([X,C,G,W],[Y,C,G,W], moved(nothing,X,Y)) :- opposite(X,Y).

% by the way, the two shores are opposite...
opposite(south,north).
opposite(north,south).

% Legal states
% legal(+State).

legal(State) :- not(conflict(State)).

% we cannot allow the cabbage and the goat on the same shore unsupervised...
conflict([B,C,G,_]) :- C==G, opposite(C,B).

% ... nor the goat and the wolf...
conflict([B,_,G,W]) :- W==G, opposite(W,B).
% ... but anything else is fine. 

% Effectively solves the problem
% moves(+InitialState,+FinalState,-Moves).

% introduces a parameter that keeps track of visited states; also note that the 
% list of moves is given in the wrong order, hence we have to reverse it at the 
% end. 
moves(X,Y,V) :- moves(X,Y,[X],V1), reverse(V1,V).

% we reached the final state and we are done...
moves(F,F,_,[]).

% ... otherwise, generate a new move, and verify if it is legal, and there 
% are no loops. 
moves(X,F,V,[M|R]) :- move(X,Y,M), legal(Y), not(member(Y,V)), moves(Y,F,[Y|V],R).

/* 

The answer is: 

  ?- moves([north,north,north,north], [south,south,south,south], R).
  
  R = [moved(goat,north,south), moved(nothing,south,north), moved(wolf,north,south),
       moved(goat,south,north), moved(cabbage,north,south), moved(nothing,south,north),
       moved(goat,north,south)] ;
  
  R = [moved(goat,north,south), moved(nothing,south,north), moved(cabbage,north,south),
       moved(goat,south,north), moved(wolf,north,south), moved(nothing,south,north),
       moved(goat,north,south)] ;
  
  no

(The output has been edited for clarity)

*/