% Bratko Figure 11.10. An implementation of breadth-first search.

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

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

% breadthfirst([Path1, Path2, ...], Solution)
% Store all paths (in reverse order) in a queue ordered by path length
% Extend the path at the head of the queue by adding the successors of its last node
% Add newly created paths to the end of the queue

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

breadthfirst([Path | Paths], Solution)  :-
	extend(Path, NewPaths),
	append(Paths, NewPaths, Paths1),
	breadthfirst(Paths1, Solution).

extend([Node|Path], NewPaths)  :-
	findall([NewNode, Node|Path],
		(s(Node, NewNode, _), not(member(NewNode, [Node|Path]))),	% check for cycles
		NewPaths).