% Figure 11.7   A depth-first search program that avoids cycling.


% solve( Node, Solution):
%    Solution is an acyclic path (in reverse order) between Node and a goal

solve( Node, Solution)  :-
  depthfirst( [], Node, Solution).

% depthfirst( Path, Node, Solution):
%   extending the path [Node | Path] to a goal gives Solution

depthfirst( Path, Node, [Node | Path] )  :-
   goal( Node).

depthfirst( Path, Node, Sol)  :-
  s( Node, Node1),
  not( member( Node1, Path)),                % Prevent a cycle
  depthfirst( [Node | Path], Node1, Sol).

% Stack example
goal( [[a,b,c],[],[]]).
goal( [[],[a,b,c],[]]).
goal( [[],[],[a,b,c]]).

s( Stacks,[Stack1,[Top1|Stack2]|OtherStacks]) :- % Move Top1 to Stack2
 del([Top1|Stack1],Stacks,Stacks1),		 % Find first stack
 del(Stack2,Stacks1,OtherStacks).                % Find second stack

del( X,[X|L],L).
del( X,[Y|L],[Y|L1]) :- del( X,L,L1).

test(Start,Solution) :-
 Start = [[c,a,b],[],[]], solve(Start,Solution).