1 % Knight Tour
   2 
   3 % Input:
   4 % - size(N), if the chessboard is NxN
   5 % - forbidden(X,Y), if X,Y cannot be reached by the knight.
   6 
   7 % Output:
   8 % - move(X1,Y1,X2,Y2), if the knight moves from X1,Y1 to X2,Y2.
   9 
  10 
  11 
  12 
  13 % Define the chessboard.
  14 number(X) :- size(X).
  15 number(X) :- number(Y), X=Y-1, X>0.
  16 cell(X,Y) :- number(X), number(Y).
  17 
  18 % Guess the moves.
  19 move(X1,Y1,X2,Y2) | non_move(X1,Y1,X2,Y2) :- valid(X1,Y1,X2,Y2), not forbidden(X1,Y1), not forbidden(X2,Y2).
  20 
  21 % Compute all valid moves from each cell.
  22 valid(X1,Y1,X2,Y2) :- cell(X1,Y1), cell(X2,Y2), X1 = X2+2, Y1 = Y2+1.
  23 valid(X1,Y1,X2,Y2) :- cell(X1,Y1), cell(X2,Y2), X1 = X2+2, Y2 = Y1+1.
  24 valid(X1,Y1,X2,Y2) :- cell(X1,Y1), cell(X2,Y2), X2 = X1+2, Y1 = Y2+1.
  25 valid(X1,Y1,X2,Y2) :- cell(X1,Y1), cell(X2,Y2), X2 = X1+2, Y2 = Y1+1.
  26 valid(X1,Y1,X2,Y2) :- cell(X1,Y1), cell(X2,Y2), X1 = X2+1, Y1 = Y2+2.
  27 valid(X1,Y1,X2,Y2) :- cell(X1,Y1), cell(X2,Y2), X1 = X2+1, Y2 = Y1+2.
  28 valid(X1,Y1,X2,Y2) :- cell(X1,Y1), cell(X2,Y2), X2 = X1+1, Y1 = Y2+2.
  29 valid(X1,Y1,X2,Y2) :- cell(X1,Y1), cell(X2,Y2), X2 = X1+1, Y2 = Y1+2.
  30 
  31 % Exactly one move entering to each cell.
  32 :- cell(X,Y), not forbidden(X,Y), not exactlyOneMoveEntering(X,Y).
  33 exactlyOneMoveEntering(X,Y) :- move(X,Y,X1,Y1), not atLeastTwoMovesEntering(X,Y).
  34 atLeastTwoMovesEntering(X,Y) :- move(X,Y,X1,Y1), move(X,Y,X2,Y2), X1 != X2.
  35 atLeastTwoMovesEntering(X,Y) :- move(X,Y,X1,Y1), move(X,Y,X2,Y2), Y1 != Y2.
  36 
  37 % Exactly one move leaving each cell.
  38 :- cell(X,Y), not forbidden(X,Y), exactlyOneMoveLeaving(X,Y).
  39 exactlyOneMoveLeaving(X,Y) :- move(X1,Y1,X,Y), not atLeastTwoMovesLeaving(X,Y).
  40 atLeastTwoMovesLeaving(X,Y) :- move(X1,Y1,X,Y), move(X2,Y2,X,Y), X1 != X2.
  41 atLeastTwoMovesLeaving(X,Y) :- move(X1,Y1,X,Y), move(X2,Y2,X,Y), Y1 != Y2.
  42 
  43 % Each non-forbidden cell must be reached by the knight.
  44 reached(X,Y) :- move(_,_,X,Y).
  45 reached(X,Y) :- move(X,Y,_,_).
  46 % reached(X2,Y2) :- reached(X1,Y1), move(X1,Y1,X2,Y2).
  47 :- cell(X,Y), not forbidden(X,Y), not reached(X,Y).
  48 
  49 % Each forbidden cell must remain unreached.
  50 :- forbidden(X,Y), reached(X,Y).