#### Knight's Tour

You have to find a knight's tour on an N-by-N chessboard so that the knight visits each square exactly once. This was inspired by an heuristic given in "Advanced Prolog" by Peter Ross.

```check_determ
domains
side   = integer
length = integer
count  = integer
posn   = integer
posns  = posn*
p      = p(count,posn,posns)
ps     = p*
predicates
nondeterm closed_tour(side,posn,posns)
nondeterm tour(side,posn,posns)
nondeterm tour_1(length,side,posn,posns,posns,posns)
nexts(posn,side,posns)
nondeterm next(posn,side,posn)
nondeterm next_1(posn,posn,posn,posn)
less_than(p,p)
insert(ps,p,ps)
nondeterm member(p,ps)
nondeterm member(posn,posns)
reverse(posns,posns,posns)
difference(posns,posns,posns)
length(posns,count,count)
ordered_choices(posns,side,posns,ps,ps)
clauses

/* closed_tour(N, Start, Tour) is true if Tour is a closed Knight's tour   */
/*   on an N-by-N board starting and ending at the Start square, the       */
/*   squares being numbered from 0 to N * N - 1.                           */
/* e.g.closed_tour(8, 1, Tour), !.                                         */
closed_tour(N, Start, Tour):-
N mod 2 = 0, /* A closed tour is possible only if N is even */
nexts(Start, N, Nexts),
Length = N * N - 2,
tour_1(Length, N, Start, Nexts, [], [Last|Rest]),
nexts(Last, N, Nexts1),
member(Start, Nexts1),
reverse([Last|Rest], [], Tour).

/* tour(N, Start, Tour) is true if Tour is a Knight's tour on an N-by-N    */
/*   board starting at the Start square, the squares being numbered from 0 */
/*   to N * N - 1.                                                         */
/* e.g.tour(8, 0, Tour), !.                                                */
tour(N, Start, Tour):-
nexts(Start, N, Nexts),
Length = N * N - 2,
tour_1(Length, N, Start, Nexts, [], ReversedTour),
reverse(ReversedTour, [], Tour).

tour_1(0, _, Posn, [Last], Path, [Last,Posn|Path]).
tour_1(Length, N, Posn, NextPosns, Path, Tour):-
Length > 0,
Length1 = Length - 1,
ordered_choices(NextPosns, N, [Posn|Path], [], Choices),
member(p(_, NextPosn, NextButOnePosns), Choices),
tour_1(Length1, N, NextPosn, NextButOnePosns, [Posn|Path], Tour).

nexts(X, N, Ys):-findall(Y, next(X, N, Y), Ys).

next(X, N, Y):-
I = X mod N,
J = X div N,
next_1(I, J, K, L),
K >= 0, K < N,
L >= 0, L < N,
Y = L * N + K.

next_1(I, J, K, L):-K = I - 1, L = J - 2.
next_1(I, J, K, L):-K = I + 1, L = J - 2.
next_1(I, J, K, L):-K = I - 2, L = J - 1.
next_1(I, J, K, L):-K = I + 2, L = J - 1.
next_1(I, J, K, L):-K = I - 2, L = J + 1.
next_1(I, J, K, L):-K = I + 2, L = J + 1.
next_1(I, J, K, L):-K = I - 1, L = J + 2.
next_1(I, J, K, L):-K = I + 1, L = J + 2.

less_than(p(Count1, _, _), p(Count2, _, _)):-Count1 < Count2, !.

insert([X|Xs], Y, Ws):-less_than(X, Y), !, insert(Xs, Y, Zs), Ws = [X|Zs].
insert(Xs, Y, [Y|Xs]).

member(X, [X|_]).
member(X, [_|Ys]):-member(X, Ys).

difference([], _, []).
difference([X|Xs], Ys, Zs):-member(X, Ys), !, difference(Xs, Ys, Zs).
difference([X|Xs], Ys, [X|Zs]):-difference(Xs, Ys, Zs).

length([], L, L).
length([_|Xs], L0, L):-L1 = L0 + 1, length(Xs, L1, L).

reverse([], As, As).
reverse([X|Xs], As, Ys):-reverse(Xs, [X|As], Ys).

ordered_choices([], _, _, Choices, Choices).
ordered_choices([Posn|Posns], N, Path, Choices0, Choices):-
nexts(Posn, N, NextPosns),
difference(NextPosns, Path, UnvisitedPosns),
length(UnvisitedPosns, 0, Count),
insert(Choices0, p(Count, Posn, UnvisitedPosns), Choices1),
ordered_choices(Posns, N, Path, Choices1, Choices).
```