#### 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.

```/* 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, X), !.                                           */
closed_tour(N, Start, Tour):-
N mod 2 =:= 0, /* A closed tour is possible only if N is even */
nexts(Start, N, Nexts),
Length is 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, X), !.                                                  */
tour(N, Start, Tour):-
nexts(Start, N, Nexts),
Length is 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 is Length - 1,
ordered_choices(NextPosns, N, [Posn|Path], [], Choices),
member(p(_, NextPosn, NextButOnePosns), Choices),
/* Putting a cut here shows that backtracking never occurs */
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 is X mod N,
J is X // N,
next_1(I, J, K, L),
K >= 0, K < N,
L >= 0, L < N,
Y is L * N + K.

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

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

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

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

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