A more efficient program than that of szukanie_wszerz for the breadth-first search The improvement is based on using the difference-pair representation for the list of candidate paths.

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Program source code: breadth-first_search_2.pl

% 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.
 
:- op( 900, fy, not).
 
% not Goal): negation as failure; 
%   Note: This is often available as a built-in predicate,
%   often written as prefix operator "\+", e.g. \+ likes(mary,snakes)
 
not Goal  :-
  Goal, !, fail
  ; 
  true.
 
% 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),
  conc( NewPaths, Z1, Z),              % Add NewPaths at end
  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( Path, [] ).