state(1..8).     % estimate the number of necessary states.
side(l).  side(r).
is(farmer,l,1).     % farmer is on the left side in state 1 (with all items)
thing(cabbage).  thing(goat).  thing(dog).
is(X,l,1) :- thing(X).
otherside(X,Y) :- side(X), side(Y), X != Y.
0{ transport(cabbage,N), transport(goat,N), transport(dog,N) }1 :- state(N), not finished(N).
:- transport(X,N), is(farmer,S1,N), is(X,S2,N), S1 != S2,
   thing(X), state(N), side(S1), side(S2).
is(X,S2,M) :- is(X,S1,N), thing(X), otherside(S1,S2), transport(X,N), M = N+1, not finished(N),
   state(N), side(S1).
is(X,S1,M) :- is(X,S1,N), thing(X), not transport(X,N), M = N+1, not finished(N),
   state(N), side(S1).     %% the "frame axiom"
is(farmer,S2,M) :- is(farmer,S1,N), otherside(S1,S2), M = N+1, not finished(N),
   state(N), side(S1).
:- is(cabbage,S,N), is(goat,S,N), not is(farmer,S,N),   state(N), side(S).
:- is(goat,S,N), is(dog,S,N), not is(farmer,S,N),       state(N), side(S).
finished(N) :- is(cabbage,r,N), is(goat,r,N), is(dog,r,N),        state(N).
finished(M) :- finished(N), M = N+1,                              state(N).
:- not finished(8).