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

LPA Index     Home Page