:- use_module(library(lists)).

% solve(+InitialState,-Solution)
% Given InitialState, solve/2 generates a solution
% (sequence of states from the initial state to
% a final state) by means of breadth-first search.

solve(Start, Solution) :-
  breadth_first([[Start]], Path),
  reverse(Path,Solution).

% breadth_first(+Queue,-Solution)
% Given a list of paths Queue = [Path1,...,PathN],
% breadth_first/2 generates a solution Solution
% (a sequence of states from the initial state to
% a final state) by expanding the first element
% of Queue and adding expanded paths to the end.

breadth_first([[Node|Path]|_],[Node|Path]) :-
  final_state(Node).
breadth_first([Path|Paths],Solution) :-
  extend(Path, NewPaths),
  append(Paths,NewPaths,Paths1),
  breadth_first(Paths1,Solution).

% extend(+Path,-NewPaths)
% Given a path (a list of states) Path = [State1,...,StateN],
% extend/2 generates a set of new paths NewPaths by
% by adding each successor of the first state
% in front of Path (already visited states are
% excluded).

extend([Node|Path], NewPaths) :-
  findall([NewNode,Node|Path],
        (successor(Node,NewNode),
	 \+ member(NewNode,[Node|Path])),
        NewPaths).
