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

Turbo Prolog Index     Home Page