% Depth-first search:

search(Initial, Final, Result) :- 
    search(Initial, Final, [Initial], Result).
    
search(Final, Final, _, []).
search(Current, Final, Visited, [M | Result]) :- 
    move(Current, SomeState, M),
    not(member(SomeState, Visited)),
    search(SomeState, Final, [SomeState | Visited], Result).

% Breadth-first search.

bsearch(Initial, Final, Result) :-
    bsearch([pair(Initial, [])], Final, [Initial], Result).

bsearch([pair(Final, Moves) | _], Final, _, Result) :- reverse(Moves, Result).
bsearch([pair(Final, _) | Rest], Final, Visited, Result) :-  % other solutions...
    bsearch(Rest, Final, Visited, Result),!. % no backtracking needed,
                                             % since we perform the search 
                                             % by hand!
bsearch([pair(Current, Moves) | Rest], Final, Visited, Result) :-
    findall(pair(State ,[Move | Moves]),
            (move(Current, State, Move), not(member(State, Visited))),
            Bag), % Fails on redo! This effectively eliminates
                  % Prolog's own search strategy on Current
                  % (however, Prolog's backtracking is used as a while
                  % loop in order to expand the states from Rest).
    append(Rest, Bag, Open),
    bsearch(Open, Final, [Current | Visited], Result).

/* Notes.

   1. The list of visited but not yet expanded states is kept in the
   first argument of bsearch/4 (where we collect these states together
   with the sequence of moves that generated them).

   2. Each visited state keeps its own list of moves from the initial
   state to itself. However, these lists share their common values
   (provided that the unifier is a good one), and thus the space
   complexity does meet the theoretical lower bound.

   3. The use of findall/3 is actually very flexible.  The list Open
   of open states (the ones encountered but not yet expanded) is
   created by combining Bag with the previous list of such states.  If
   we append Bag to the existing open states (as above) we get the
   desired breath-first search: the previous, shallower states will be
   expanded first.  If on the other hand we put Bag in front, we get
   a...  depth-first search: the most recent (deeper!) states will be
   expanded first.

   We can even compute an estimate of how close a state is to the
   goal, and keep the Open list sorted with respect to this
   estimation.  Such a sorting yields a form of greedy search called
   best-first.  If we use for sorting the sum of the estimate
   mentioned above and the effort spend so far in reaching the state
   we end up with a search algorithm called A*, which most of the time
   (but not always) is the most efficient search strategy.

   The best-first and breath-first search algorithms are both
   uninformed search algorithms, while best-first and A* are two
   variants of heuristic search algorithms.
*/

%% The Knights tour, for testing purposes. Possible goals:
%% :- search(1-1,3-3,R).
%% :- bsearch(1-1,3-3,R).
%% (they do not necessarily return the same set of solutions - why?)

% The board size is given by the predicate size/1

size(3). 

% The position of the Knight is represented by the 
% structure -(X,Y) (or X-Y), where X and Y are the 
% coordinates of the square where the Knight is located. 
% We represent a move by the the position it generates.

move(A,B,B) :- move_attempt(A,B), inside(B).

% There are 8 possible moves in the middle of the board: 

move_attempt(I-J, K-L) :- K is I+1, L is J-2. 
move_attempt(I-J, K-L) :- K is I+1, L is J+2. 
move_attempt(I-J, K-L) :- K is I+2, L is J+1. 
move_attempt(I-J, K-L) :- K is I+2, L is J-1. 
move_attempt(I-J, K-L) :- K is I-1, L is J+2.
move_attempt(I-J, K-L) :- K is I-1, L is J-2.  
move_attempt(I-J, K-L) :- K is I-2, L is J+1. 
move_attempt(I-J, K-L) :- K is I-2, L is J-1. 

% However, if the Knight is somwhere close to board's 
% margins, some moves might fall out of the board... 

inside(A-B) :- size(Max), A > 0, A =< Max, 
                          B > 0, B =< Max.
