% Figure 11.10   An implementation of breadth-first search.


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

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

% breadthfirst( [ Path1, Path2, ...], Solution):
%   Solution is an extension to a goal of one of paths

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

breadthfirst( [Path | Paths], Solution)  :-
  extend( Path, NewPaths),
  append( Paths, NewPaths, Paths1), % append in place of conc
  breadthfirst( Paths1, 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).