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