% Figure 11.11  A more efficient program than that of Figure 11.10 for 
% the breadth-first search. The improvement is based on using 
% the difference-pair representation for the list of candidate paths. 
% Procedure extend is as in Figure 11.10.


% solve( Start, Solution):
%   Solution is a path (in reverse order) from Start to a goal

solve( Start, Solution)  :-
  breadthfirst( [ [Start] | Z] - Z, Solution).

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

breadthfirst( [Path | Paths] - Z, Solution)  :-
  extend( Path, NewPaths),
  append( NewPaths, Z1, Z), % Add NewPaths at end (append used in place of conc)
  Paths \== Z1,                        % Set of candidates not empty
  breadthfirst( Paths - Z1, Solution).

extend( [Node | Path], NewPaths)  :-
  bagof( [NewNode, Node | Path],
         ( s( Node, NewNode), not( member( NewNode, [Node | Path] ) ) ),
         NewPaths),
  !.

extend( _, [] ).              % bagof failed: Node has no successor

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