/*
  The Cabbage, Goat, Wolf problem, take 1.  A state is described as a
  function with three arguments.  Such a representation may seem
  natural but actually generates a more complicated solution.

  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.
*/

% the query would be: 
% moves(state(north,has(cabbage,goat,wolf),has(nil,nil,nil)),
%       state(south,has(nil,nil,nil),has(cabbage,goat,wolf)),R).

% A state is represented by the function
% state(BoatLocation,NorthContent,SouthContent)
% where the content on each shore is represented by 
% has(Cabbage,Goat,Wolf).
% Each of the parameters Cabbage, Goat, and Wolf may be nil.

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

%from north to south first...
move(state(north,X,Y), state(south,R1,R2),moved(O,north,south)) :- 
  pick_object(O,X), add_object(O,Y,R2), del_object(O,X,R1).

%... then, the same thing, but from south to north
move(state(south,X,Y), state(north,R1,R2),moved(O,south,north)) :- 
  pick_object(O,Y), add_object(O,X,R1), del_object(O,Y,R2).

% and eventually move the empty boat if anything else fails
move(state(P,X,Y),state(Q,X,Y),moved(nothing,P,Q)) :- opposite(P,Q).

%%%%
% Pick something to move to the other shore
% pick_object(-Object,+Content)

pick_object(X,has(A,B,C)) :- member(X,[A,B,C]), not(X=nil).

% Erases an object from a shore. 
% del_object(+Object,+Shore,-NewShore)

del_object(cabbage,has(A,B,C),has(nil,B,C)).
del_object(goat,has(A,B,C),has(A,nil,C)).
del_object(wolf,has(A,B,C),has(A,B,nil)).

% Adds an object to a shore. 
% add_object(+Object,+Shore,-NewShore)

add_object(cabbage,has(A,B,C),has(cabbage,B,C)).
add_object(goat,has(A,B,C),has(A,goat,C)).
add_object(wolf,has(A,B,C),has(A,B,wolf)).

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

% Legal states
% legal(+State).

legal(state(south,has(C,G,W),_)) :- not(conflict(C,G,W)).
legal(state(north,_,has(C,G,W))) :- not(conflict(C,G,W)).

% we cannot allow the cabbage and the goat on the same shore unsupervised...
conflict(C,G,W) :- C=cabbage, G=goat.

% ... nor the goat and the wolf...
conflict(C,G,W) :- G=goat, W=wolf.
% ... 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,V,[]).

% ... 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).