% P91 (**) Knight's tour
% Another famous problem is this one: How can a knight jump on an
% NxN chessboard in such a way that it visits every square exactly once?

% knights(N,Knights) :- Knights is a knight's tour on a NxN chessboard 

knights(N,Knights) :- M is N*N-1,  knights(N,M,[1/1],Knights).

% closed_knights(N,Knights) :- Knights is a knight's tour on a NxN 
% chessboard which ends at the same square where it begun.

closed_knights(N,Knights) :- 
   knights(N,Knights), Knights = [X/Y|_], jump(N,X/Y,1/1). 

% knights(N,M,Visited,Knights) :- the list of squares Visited must be
% extended by M further squares to give the solution Knights of the
% NxN chessboard knight's tour problem. 

knights(_,0,Knights,Knights).
knights(N,M,Visited,Knights) :-
   Visited = [X/Y|_],
   jump(N,X/Y,U/V),
   \+ memberchk(U/V,Visited),
   M1 is M-1,
   knights(N,M1,[U/V|Visited],Knights).

% jumps on an NxN chessboard from square A/B to C/D
jump(N,A/B,C/D) :- 
   jump_dist(X,Y), 
   C is A+X, C > 0, C =< N,
   D is B+Y, D > 0, D =< N.

% jump distances
jump_dist(1,2).
jump_dist(2,1).
jump_dist(2,-1).
jump_dist(1,-2).
jump_dist(-1,-2).
jump_dist(-2,-1).
jump_dist(-2,1).
jump_dist(-1,2).


% A more user-friendly presentation of the results ------------------------

show_knights(N) :- 
   get_time(Time), convert_time(Time,Tstr),
   write('Start: '), write(Tstr), nl, nl,
   knights(N,Knights), nl, show(N,Knights).

show(N,Knights) :-
   get_time(Time), convert_time(Time,Tstr),
   write(Tstr), nl, nl,
   length(Chessboard,N),
   Pred =.. [invlength,N],
   checklist(Pred,Chessboard),
   fill_chessboard(Knights,Chessboard,1),
   checklist(show_row,Chessboard),
   nl, fail.

invlength(N,L) :- length(L,N).

show_row([]) :- nl.
show_row([S|Ss]) :- writef('%3r',[S]), show_row(Ss). 

fill_chessboard([],_,_).
fill_chessboard([X/Y|Ks],Chessboard,K) :-
   nth1(Y,Chessboard,Row),
   nth1(X,Row,K),
   K1 is K+1,
   fill_chessboard(Ks,Chessboard,K1).

% --------------------------------------------------------------------------