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