% the call would be: 
% search(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 structure
% 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.

% Pick something to move to the other shore
pick_object(X, has(A, B, C)) :- member(X, [A, B, C]), not(X = nil).

% Erases an object from a shore. 
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(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)).

% Moving around

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

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

% Legal states
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(cabbage, goat, W).
% ... nor the goat and the wolf...
conflict(C, goat, wolf).
% ... but anything else is fine. 

% Effectively solves the problem

search(X, Y, V) :- search(X, Y, [X], V1), reverse(V1, V).

search(F, F, V, []).
search(X, F, V, [M|R]) :- move(X, Y, M), legal(Y), not(member(Y, V)), search(Y, F, [Y|V], R).
