One man,one goat,one cabbage and one wolf

[spx2]

Hi,

I have tried to solve the problem mentioned in the subject.
What I wrote doesn't go through all possibilities up to depth 8(which
is what I wanted).
We are trasnfering the objects from Left -> Right
If at any time the Left bank remains empty then we immediately exit.
The sideGood predicate assures that the side is in conformity with our
rules
(there should be no [wolf,goat] pair or [goat,cabbage] pair on that
side).
So,it can be tested with traverse([wolf,cabbage,goat],[],0).
However,it does not hit a solution(altough it was expected to do so
because
depth has been limited to 8,and it doesn't explore all the
possibilities).
My question is why does it not backtrack properly ?
I have some cuts in the program,are they of the wrong type(I
understand that there are red/green types)?
I am aware of this nicer solution that works
http://www-cse.ucsd.edu/classes/sp05/cse130/misc/Prolog/goat_etc.html
.
That solution is different because it stores the configuration of the
problem in a much simpler way,
but still it has to backtrack and it does so properly , unlike what I
wrote.

%
% author : Petrea Stefan
% website : http://perlhobby.googlecode.com
%

%cabbage wolf goat and man problem

% we can only allow these situations
% and also viceversa for each one
% but nothing else

sideGood(Side):-
( member(goat,Side),member(wolf,Side) ,!,fail ); %we dont want these
two cases
( member(goat,Side),member(cabbage,Side),!,fail );
true.%we assure that neither the goat is eaten by wolf nor the goat
eats the cabbage

takeOnOtherSide(S1,S2,S1new,S2new):-
(
member(Whototake,S1),%we get a member of S1 and put in S2,ofcourse
we make 2 new lists for this
subtract(S1,[Whototake],S1new),
S2new = [Whototake|S2]
).%the man takes with him one of the objects on S1 and goes with it
in S2
takeOnOtherSide(S1,S2,S1new,S2new):-
(
S1new = S1,
S2new = S2
).%the man goes alone on the other side

%here L and R are symbolising the right and left sides of the river
the boat must cross
%if we go on the second branch(big one) , there are two
takeOnOtherSide one is L->R
%and the other is R->L, if at any point when doing those we get L1 or
L2 empty that means
%we have finished and we must cut and interrupt the execution

traverse(L,R,D):-
(L=@=[],!,true);
(
takeOnOtherSide(L ,R ,L1,R1),
(
(L1=@=[],!,true);
(sideGood(L1),sideGood(R1))
),
writeln(L1),writeln(R1),
takeOnOtherSide(R1,L1,R2,L2),
(
(L2=@=[],!,true);
(sideGood(L2),sideGood(R2))
),
writeln(L2),writeln(R2),
D<8,traverse(L2,R2,D+1)
).

% how to test
% traverse([wolf,cabbage,goat],[],0).