% Section 11.2: iterative deepening depth-first search

depth_first_iterative_deepening( Node,Solution) :-
 path( Node,GoalNode,Solution),
 goal( GoalNode).

% path(Node1,Node2,Path) if Path is an acyclic (i.e., simple) path,
% in reverse order, between Node1 and Node2 in the state-space defined
% by the successor relation s

path( Node,Node,[Node]).

path( FirstNode,LastNode,[LastNode | Path]) :-
 path( FirstNode,OneButLast,Path),
 s( OneButLast,LastNode),
 not( member( LastNode,Path)).

% 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],[],[]], depth_first_iterative_deepening(Start,Solution).