% 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).
% --------------------------------------------------------------------------