Breadth First Search
Here is simple code for breadth first search. It is taken from the book
of Ivan Bratko.
% solve(+Start,Solution)
% Solution is an acyclic path (in reverse order)
% from Start to a goal
%
solve(Start, Solution) :
breadthfirst( [[Start]], Solution).
% breadthfirst(+[Paths], Solution).
% Paths is the list of paths being explored
%
% Node is it.
breadthfirst([ [NodePath] _OtherPaths], [NodePath]) :
goal(Node). % you have to write goal(+Node).
breadthfirst([Path Paths], Solution) :
extend(Path, NewPaths),
append(Paths, newpaths, Paths1),
breadthfirst(Pths1, Solution).
extend([NodePath], NewPaths) :
bagof( [NewNode, Node, Path],
(successor(Node, NewNode), not member(NewNode, [NodePath])),
NewPaths),
!.
extend(Path, []).
Notes:

For more details on (\+)/2. This is a form of " not ".
It must be used with care.

For details on the cut (!/0)

For details on bagof/3.
Note in particular that bagof fails when the goal has no solutions.
On the other hand findall/3 does not.
Jonathan Hodgson
Last Changed: 1999/10/07