Solution: The Knight's Tour

The code...

declare
fun {Knights N}
   NN = N*N
   % The fields of the board are numbered from 1..NN
   % according to their lexicographic order, that is,
   % (1,1), (1,2), ..., (2,1), (2,2), ..., (N,N)
   %
   % Field: X x Y --> Field
   fun {Field X Y}
      (X-1)*N + Y
   end
   % Neighbours: Field --> List of fields
   fun {Neighbours F}
      X  = (F-1) mod N + 1
      Y  = (F-1) div N + 1
   in
      {FoldR [~2#~1 ~2#1 ~1#~2 ~1#2  1#~2 1#2 2#~1 2#1]
       fun {$ U#V In}
          A = X+U
          B = Y+V
       in
          case A>=1 andthen A=<N andthen B>=1 andthen B=<N
          then A + (B-1)*N | In else In end
       end
       nil}
   end
in
   proc {$ Solution}
      Pred  = {FD.tuple pred NN 1#NN}   % field --> field
      Succ  = {FD.tuple succ NN 1#NN}   % field --> field
      Jump  = {FD.tuple jump NN 1#NN}   % field --> jump
            = {FD.distinct}
   in
      Solution = Jump#Succ#Pred
      % there are no solutions for odd N
      N mod 2 = 0
      % tour starts as follows: (1,1), (2,3), ... 
      Jump.{Field 1 1} = 1            
      Jump.{Field 2 3} = 2
      % for every field F
      {For 1 NN 1
       proc {$ F}
          Nbs   = {Neighbours F}
       in
          Pred.F :: Nbs
          Succ.F :: Nbs
          % redundant constraint: avoid trivial cycles
          Succ.F \=: Pred.F
          % for every neighbour G of F
          {ForAll Nbs
           proc {$ G}
              (Succ.F=:G)
              = (F=:Pred.G)
              = (Jump.G =: {FD.modI Jump.F NN}+1)
           end}
       end}
      {FD.distribute naive Succ} % better than ff
   end
end

{ExploreOne {Knights 8}}
The search tree has no decision nodes. To find one solution, 2.26 seconds of computation are needed.

This first solution is

 1  8 15 24  3 10 13 22 
16 25  2  9 14 23  4 11
 7 64 17 26  5 12 21 38
18 27  6 63 20 39 54 59
47 62 19 28 55 60 37 40
32 29 48 61 44 41 55 53
49 46 31 34 51 56 43 36
30 33 50 45 42 35 52 57

Markus Löckelt