Knight's tour: Difference between revisions

Content added Content deleted

Inline

Revision as of 01:59, 10 May 2012

Problem: you have a standard 8x8 chessboard, empty but for a single knight on some square. Your task is to emit a series of legal knight moves that result in the knight visiting every square on the chessboard exactly once. Note that it is not a requirement that the tour be "closed"; that is, the knight need not end within a single move of its start position.

Input and output may be textual or graphical, according to the conventions of the programming environment. If textual, squares should be indicated in algebraic notation. The output should indicate the order in which the knight visits the squares, starting with the initial position. The form of the output may be a diagram of the board with the squares numbered ordering to visitation sequence, or a textual list of algebraic coordinates in order, or even an actual animation of the knight moving around the chessboard.

Input: starting square

Output: move sequence

Cf.

N-queens problem

Ada

First, we specify a naive implementation with naive backtracking:

<lang Ada>generic

  Size: Integer;

package Knights_Tour is

  subtype Index is Integer range 1 .. Size;
  type Tour is array  (Index, Index) of Natural;

  function Get_Tour(Start_X, Start_Y: Index) return Tour;
  -- finds tour via backtracking
  -- either no tour has been found, (Get_Tour(X, Y)=0 for all X, Y in Index)
  -- or the Result(X,Y)=K if and only if I,J is visited at the K-th move

  procedure Tour_IO(The_Tour: Tour);
  -- writes The_Tour to the output using Ada.Text_IO;

end Knights_Tour;</lang>

Here is the implementation:

<lang Ada>with Ada.Text_IO, Ada.Integer_Text_IO;

package body Knights_Tour is

  Visited: Tour;
  -- Visited(I, J)=0: Not yet visited
  -- Visited(I, J)=K: Visited during the k-th move

  type Pair is array(1..2) of Integer;
  type Pair_Array is array (Positive range <>) of Pair;

  Pairs: constant Pair_Array (1..8)
    := ((-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1));
  -- possible places to visit if Done

  function Get_Tour(Start_X, Start_Y: Index) return Tour is

     procedure Visit(X, Y: Index; Move_Number: Positive; Found: out Boolean) is
        XX, YY: Integer;
     begin
        Found := False;
        Visited(X, Y) := Move_Number;
        if Move_Number = Integer(Index'Last * Index'Last) then
           Found := True;
        else
           for P in Pairs'Range loop
              XX := X + Pairs(P)(1);
              YY := Y + Pairs(P)(2);
              if (XX in Index) and then (YY in Index)
                               and then Visited(XX, YY) = 0 then
                 Visit(XX, YY, Move_Number+1, Found); -- recursion
                 if Found then
                    return; -- no need to search further
                 end if;
              end if;
           end loop;
           Visited(X, Y) := 0; -- undo previous mark
        end if;
     end Visit;

     Done: Boolean;
  begin
     Visited := (others => (others => 0));
     Visit(Start_X, Start_Y, 1, Done);
     if not Done then
        Visited := (others => (others => 0));
     end if;
     return Visited;
  end Get_Tour;

  procedure Tour_IO(The_Tour: Tour) is
  begin
     if The_Tour(1, 1) /= 0 then
     for I in Index loop
        for J in Index loop
           Ada.Integer_Text_IO.Put(The_Tour(I, J), 4);
        end loop;
        Ada.Text_IO.New_Line;
     end loop;
     else
        Ada.Text_IO.Put_Line("No Solution");
     end if;
  end Tour_IO;

end Knights_Tour;</lang>

Here is the main program:

<lang Ada>with Knights_Tour, Ada.Command_Line;

procedure Test_Knight is

  Size: Positive := Positive'Value(Ada.Command_Line.Argument(1));

  package KT is new Knights_Tour(Size => Size);

begin

  KT.Tour_IO(KT.Get_Tour(1, 1));

end Test_Knight;</lang>

For small sizes, this already works well (< 1 sec for size 8). Sample output:

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

For larger sizes we'll use Warnsdorff's heuristic (without any thoughtful tie breaking). We extend the specification by

<lang Ada> function Warnsdorff_Get_Tour(Start_X, Start_Y: Index) return Tour;

  -- uses Warnsdorff heurisitic to find a tour faster
  -- same interface as Get_Tour</lang>

and the implementation by <lang Ada> function Warnsdorff_Get_Tour(Start_X, Start_Y: Index) return Tour is

     Done: Boolean;

     function Neighbors(X, Y: Index) return Natural is
        Result: Natural := 0;
     begin
        for P in Pairs'Range loop
           if X+Pairs(P)(1) in Index and then Y+Pairs(P)(2) in Index and then
             Visited(X+Pairs(P)(1),  Y+Pairs(P)(2)) = 0 then
              Result := Result + 1;
           end if;
        end loop;
        return Result;
     end Neighbors;

     procedure Sort(Options: in out Pair_Array) is
        N_Bors: array(Options'Range) of Natural;
        K: Positive range Options'Range;
        N: Natural;
        P: Pair;
     begin
        for Opt in Options'Range loop
           N_Bors(Opt) := Neighbors(Options(Opt)(1), Options(Opt)(2));
        end loop;
        for Opt in Options'Range loop
           K := Opt;
           for Alternative in Opt+1 .. Options'Last loop
              if N_Bors(Alternative) < N_Bors(Opt) then
                 K := Alternative;
              end if;
           end loop;
           N           := N_Bors(Opt);
           N_Bors(Opt) := N_Bors(K);
           N_Bors(K)   := N;
           P            := Options(Opt);
           Options(Opt) := Options(K);
           Options(K)   := P;
        end loop;
     end Sort;

     procedure Visit(X, Y: Index; Move: Positive; Found: out Boolean) is
        Next_Count: Natural range 0 .. 8 := 0;
        Next_Steps: Pair_Array(1 .. 8);
        XX, YY: Integer;
     begin
        Found := False;
        Visited(X, Y) := Move;
        if Move = Integer(Index'Last * Index'Last) then
           Found := True;
        else
           -- consider all possible places to go
           for P in Pairs'Range loop
              XX := X + Pairs(P)(1);
              YY := Y + Pairs(P)(2);
              if (XX in Index) and then (YY in Index)
                and then Visited(XX, YY) = 0 then
                 Next_Count := Next_Count+1;
                 Next_Steps(Next_Count) := (XX, YY);
              end if;
           end loop;

           Sort(Next_Steps(1 .. Next_Count));

           for N in 1 .. Next_Count loop
              Visit(Next_Steps(N)(1), Next_Steps(N)(2), Move+1, Found);
              if Found then
                 return; -- no need to search further
           end if;
           end loop;

           -- if we didn't return above, we have to undo our move
           Visited(X, Y) := 0;
        end if;
     end Visit;

  begin
     Visited := (others => (others => 0));
     Visit(Start_X, Start_Y, 1, Done);
     if not Done then
        Visited := (others => (others => 0));
     end if;
     return Visited;
  end Warnsdorff_Get_Tour;</lang>

The modification for the main program is trivial: <lang Ada>with Knights_Tour, Ada.Command_Line;

procedure Test_Fast is

  Size: Positive := Positive'Value(Ada.Command_Line.Argument(1));

  package KT is new Knights_Tour(Size => Size);

begin

  KT.Tour_IO(KT.Warnsdorff_Get_Tour(1, 1));

end Test_Fast;</lang>

This works still well for somewhat larger sizes:

>./test_fast 24
   1 108  45  52   3 112  57  60   5  62 131 144   7  64 147 170   9  66 187 192  11  68  71 190
  46  51   2 111  56  53   4 113 130  59   6  63 146 169   8  65 186 215  10  67 188 191  12  69
 107  44 109  54 123 114 129  58  61 132 145 168 143 148 185 214 171 198 225 216 193  70 189  72
  50  47 122 115 110  55 140 133 128 167 142 149 184 213 172 199 226 255 246 197 224 217 194  13
  43 106  49 124 139 134 127 166 141 150 183 212 173 200 227 254 247 242 223 256 245 196  73 218
  48 121 116 135 126 165 138 151 182 211 174 201 228 253 248 241 290 263 304 243 222 257  14 195
 105  42 125 164 137 152 181 210 175 202 229 252 249 240 289 264 329 308 291 262 303 244 219  74
 120 117 136 153 180 163 176 203 230 267 250 239 288 265 328 309 334 345 330 305 292 221 258  15
  41 104 119 160 177 204 231 268 209 238 287 266 251 310 335 344 357 332 307 346 261 302  75 220
 118 159 154 205 162 179 208 237 286 269 324 311 336 327 438 333 418 347 356 331 306 293  16 259
 103  40 161 178 207 232 285 270 323 312 337 326 483 416 343 422 437 358 419 298 349 260 301  76
 158 155 206 233 284 271 236 313 338 325 482 415 342 439 484 417 420 423 348 355 360 299 294  17
  39 102 157 272 235 314 339 322 481 414 341 492 497 514 421 440 485 436 359 424 297 350  77 300
 156 273 234 315 276 283 478 413 340 493 480 513 530 491 498 515 452 441 454 435 354 361  18 295
 101  38 275 282 397 412 321 494 479 512 557 496 543 534 529 490 499 486 451 442 425 296 351  78
 274 279 316 277 320 477 410 511 570 495 554 535 556 531 542 533 516 453 444 455 434 353 362  19
  37 100 281 398 411 396 575 476 567 558 561 544 553 536 521 528 489 500 487 450 443 426  79 352
 280 317 278 319 402 409 510 569 560 571 566 555 550 541 532 537 522 517 460 445 456 433  20 363
  99  36 389 378 399 576 395 574 475 568 559 562 545 552 525 520 527 488 501 462 449 364 427  80
  94 379 318 401 388 403 408 509 572 565 474 551 540 549 538 523 518 461 446 459 432 457 366  21
  35  98  93 390 377 400 573 394 375 508 563 546 373 524 519 526 371 502 463 466 365 448  81 428
 380  95 382 385 404 387 376 407 564 473 374 507 548 539 372 503 464 467 370 447 458 431  22 367
 383  34  97  92 391  32 405  90 393  30 547  88 471  28 505  86 469  26 465  84 369  24 429  82
  96 381 384  33 386  91 392  31 406  89 472  29 506  87 470  27 504  85 468  25 430  83 368  23

Bracmat

<lang bracmat> ( knightsTour

 =     validmoves WarnsdorffSort algebraicNotation init solve
     , x y fieldsToVisit
   .   ~
     |   ( validmoves
         =   x y jumps moves
           .   !arg:(?x.?y)
             & :?moves
             & ( jumps
               =   dx dy Fs fxs fys fx fy
                 .   !arg:(?dx.?dy)
                   & 1 -1:?Fs
                   & !Fs:?fxs
                   &   whl
                     ' ( !fxs:%?fx ?fxs
                       & !Fs:?fys
                       &   whl
                         ' ( !fys:%?fy ?fys
                           &     (   (!x+!fx*!dx.!y+!fy*!dy)
                                   : (>0:<9.>0:<9)
                                 | 
                                 )
                                 !moves
                             : ?moves
                           )
                       )
               )
             & jumps$(1.2)
             & jumps$(2.1)
             & !moves
         )
       & ( init
         =   fields x y
           .   :?fields
             & 0:?x
             &   whl
               ' ( 1+!x:<9:?x
                 & 0:?y
                 &   whl
                   ' ( 1+!y:<9:?y
                     & (!x.!y) !fields:?fields
                     )
                 )
             & !fields
         )
       & init$:?fieldsToVisit
       & ( WarnsdorffSort
         =   sum moves elm weightedTerms
           .   ( weightedTerms
               =   pos alts fieldsToVisit moves move weight
                 .     !arg:(%?pos ?alts.?fieldsToVisit)
                     &   (   !fieldsToVisit:!pos
                           & (0.!pos)
                         |   !fieldsToVisit:? !pos ?
                           & validmoves$!pos:?moves
                           & 0:?weight
                           &   whl
                             ' ( !moves:%?move ?moves
                               & (   !fieldsToVisit:? !move ?
                                   & !weight+1:?weight
                                 | 
                                 )
                               )
                           & (!weight.!pos)
                         | 0
                         )
                       + weightedTerms$(!alts.!fieldsToVisit)
                   | 0
               )
             & weightedTerms$!arg:?sum
             & :?moves
             &   whl
               ' ( !sum:(#.?elm)+?sum
                 & !moves !elm:?moves
                 )
             & !moves
         )
       & ( solve
         =   pos alts fieldsToVisit A Z tailOfSolution
           .   !arg:(%?pos ?alts.?fieldsToVisit)
             &   (   !fieldsToVisit:?A !pos ?Z
                   & ( !A !Z:&
                     |   solve
                       $ ( WarnsdorffSort$(validmoves$!pos.!A !Z)
                         . !A !Z
                         )
                     )
                 | solve$(!alts.!fieldsToVisit)
                 )
               : ?tailOfSolution
             & !pos !tailOfSolution
         )
       & ( algebraicNotation
         =   x y
           .     !arg:(?x.?y) ?arg
               &   str$(chr$(asc$a+!x+-1) !y " ")
                   algebraicNotation$!arg
             | 
         )
       & @(!arg:?x #?y)
       & asc$!x+-1*asc$a+1:?x
       &   str
         $ (algebraicNotation$(solve$((!x.!y).!fieldsToVisit)))
 )

& out$(knightsTour$a1);</lang>

a1 b3 a5 b7 d8 f7 h8 g6 f8 h7 g5 h3 g1 e2 c1 a2 b4 a6 b8 c6 a7 c8 e7 g8 h6 g4 h2 f1 d2 b1 a3 c2 e1 f3 h4 g2 e3 d1 b2 a4 c3 b5 d4 f5 d6 c4 e5 d3 f2 h1 g3 e4 c5 d7 b6 a8 c7 d5 f4 e6 g7 e8 f6 h5

C

For an animated version using OpenGL, see Knight's tour/C.

The following draws on console the progress of the horsie. Specify board size on commandline, or use default 8. <lang c>#include <stdio.h>

include <stdlib.h>
include <string.h>
include <unistd.h>

typedef unsigned char cell; int dx[] = { -2, -2, -1, 1, 2, 2, 1, -1 }; int dy[] = { -1, 1, 2, 2, 1, -1, -2, -2 };

void init_board(int w, int h, cell **a, cell **b) { int i, j, k, x, y, p = w + 4, q = h + 4; /* b is board; a is board with 2 rows padded at each side */ a[0] = (cell*)(a + q); b[0] = a[0] + 2;

for (i = 1; i < q; i++) { a[i] = a[i-1] + p; b[i] = a[i] + 2; }

memset(a[0], 255, p * q); for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { for (k = 0; k < 8; k++) { x = j + dx[k], y = i + dy[k]; if (b[i+2][j] == 255) b[i+2][j] = 0; b[i+2][j] += x >= 0 && x < w && y >= 0 && y < h; } } } }

define E "\033["

int walk_board(int w, int h, int x, int y, cell **b) { int i, nx, ny, least; int steps = 0; printf(E"H"E"J"E"%d;%dH"E"32m[]"E"m", y + 1, 1 + 2 * x);

while (1) { /* occupy cell */ b[y][x] = 255;

/* reduce all neighbors' neighbor count */ for (i = 0; i < 8; i++) b[ y + dy[i] ][ x + dx[i] ]--;

/* find neighbor with lowest neighbor count */ least = 255; for (i = 0; i < 8; i++) { if (b[ y + dy[i] ][ x + dx[i] ] < least) { nx = x + dx[i]; ny = y + dy[i]; least = b[ny][nx]; } }

if (least > 7) { printf(E"%dH", h + 2); return steps == w * h - 1; }

if (steps++) printf(E"%d;%dH[]", y + 1, 1 + 2 * x); x = nx, y = ny; printf(E"%d;%dH"E"31m[]"E"m", y + 1, 1 + 2 * x); fflush(stdout); usleep(120000); } }

int solve(int w, int h) { int x = 0, y = 0; cell **a, **b; a = malloc((w + 4) * (h + 4) + sizeof(cell*) * (h + 4)); b = malloc((h + 4) * sizeof(cell*));

while (1) { init_board(w, h, a, b); if (walk_board(w, h, x, y, b + 2)) { printf("Success!\n"); return 1; } if (++x >= w) x = 0, y++; if (y >= h) { printf("Failed to find a solution\n"); return 0; } printf("Any key to try next start position"); getchar(); } }

int main(int c, char **v) { int w, h; if (c < 2 || (w = atoi(v[1])) <= 0) w = 8; if (c < 3 || (h = atoi(v[2])) <= 0) h = w; solve(w, h);

return 0; }</lang>

C++

Works with: C++11

Uses Warnsdorff's rule and (iterative) backtracking if that fails.

<lang cpp>#include <iostream>

include <iomanip>
include <array>
include <string>
include <tuple>
include <algorithm>

using namespace std;

template<int N = 8> class Board { public:

   array<pair<int, int>, 8> moves;
   array<array<int, N>, N> data;

   Board() 
   {
       moves[0] = make_pair(2, 1);
       moves[1] = make_pair(1, 2);
       moves[2] = make_pair(-1, 2);
       moves[3] = make_pair(-2, 1);
       moves[4] = make_pair(-2, -1);
       moves[5] = make_pair(-1, -2);
       moves[6] = make_pair(1, -2);
       moves[7] = make_pair(2, -1);
   }

   array<int, 8> sortMoves(int x, int y) const 
   {
       array<tuple<int, int>, 8> counts;
       for(int i = 0; i < 8; ++i) 
       {
           int dx = get<0>(moves[i]);
           int dy = get<1>(moves[i]);

           int c = 0;
           for(int j = 0; j < 8; ++j) 
           {
               int x2 = x + dx + get<0>(moves[j]);
               int y2 = y + dy + get<1>(moves[j]);

               if (x2 < 0 || x2 >= N || y2 < 0 || y2 >= N)
                   continue;
               if(data[y2][x2] != 0)
                   continue;

               c++;
           }

           counts[i] = make_tuple(c, i);
       }

       // Shuffle to randomly break ties
       random_shuffle(counts.begin(), counts.end());

       // Lexicographic sort
       sort(counts.begin(), counts.end());

       array<int, 8> out;
       for(int i = 0; i < 8; ++i)
           out[i] = get<1>(counts[i]);
       return out;
   }

   void solve(string start) 
   {
       for(int v = 0; v < N; ++v)
           for(int u = 0; u < N; ++u)
               data[v][u] = 0;

       int x0 = start[0] - 'a';
       int y0 = N - (start[1] - '0');
       data[y0][x0] = 1;

       array<tuple<int, int, int, array<int, 8>>, N*N> order;
       order[0] = make_tuple(x0, y0, 0, sortMoves(x0, y0));

       int n = 0;
       while(n < N*N-1) 
       {
           int x = get<0>(order[n]);
           int y = get<1>(order[n]);

           bool ok = false;
           for(int i = get<2>(order[n]); i < 8; ++i) 
           {
               int dx = moves[get<3>(order[n])[i]].first;
               int dy = moves[get<3>(order[n])[i]].second;

               if(x+dx < 0 || x+dx >= N || y+dy < 0 || y+dy >= N)
                   continue;
               if(data[y + dy][x + dx] != 0) 
                   continue;

               ++n;
               get<2>(order[n]) = i + 1;
               data[y+dy][x+dx] = n + 1;
               order[n] = make_tuple(x+dx, y+dy, 0, sortMoves(x+dx, y+dy));
               ok = true;
               break;
           }

           if(!ok) // Failed. Backtrack.
           {
               data[y][x] = 0;
               --n;
           }
       }
   }

   template<int N>
   friend ostream& operator<<(ostream &out, const Board<N> &b);

};

template<int N> ostream& operator<<(ostream &out, const Board<N> &b) {

   for (int v = 0; v < N; ++v) 
   {
       for (int u = 0; u < N; ++u) 
       {
           if (u != 0) out << ",";
           out << setw(3) << b.data[v][u];
       }
       out << endl;
   }
   return out;

}

int main() {

   Board<5> b1;
   b1.solve("c3");
   cout << b1 << endl;

   Board<8> b2;
   b2.solve("b5");
   cout << b2 << endl;

   Board<31> b3; // Max size for <1000 squares
   b3.solve("a1");
   cout << b3 << endl;
   return 0;

}</lang>

Output:

 23, 16, 11,  6, 21
 10,  5, 22, 17, 12
 15, 24,  1, 20,  7
  4,  9, 18, 13,  2
 25, 14,  3,  8, 19

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

275,112, 19,116,277,604, 21,118,823,770, 23,120,961,940, 25,122,943,926, 27,124,917,898, 29,126,911,872, 31,128,197,870, 33
 18,115,276,601, 20,117,772,767, 22,119,958,851, 24,121,954,941, 26,123,936,925, 28,125,912,899, 30,127,910,871, 32,129,198
111,274,113,278,605,760,603,822,771,824,769,948,957,960,939,944,953,942,927,916,929,918,897,908,913,900,873,196,875, 34,869
114, 17,600,273,602,775,766,773,768,949,850,959,852,947,952,955,932,937,930,935,924,915,920,905,894,909,882,901,868,199,130
271,110,279,606,759,610,761,776,821,764,825,816,951,956,853,938,945,934,923,928,919,896,893,914,907,904,867,874,195,876, 35
 16,581,272,599,280,607,774,765,762,779,950,849,826,815,946,933,854,931,844,857,890,921,906,895,886,883,902,881,200,131,194
109,270,281,580,609,758,611,744,777,820,763,780,817,848,827,808,811,846,855,922,843,858,889,892,903,866,885,192,877, 36,201
282, 15,582,269,598,579,608,757,688,745,778,819,754,783,814,847,828,807,810,845,856,891,842,859,884,887,880,863,202,193,132
267,108,283,578,583,612,689,614,743,756,691,746,781,818,753,784,809,812,829,806,801,840,835,888,865,862,203,878,191,530, 37
 14,569,268,585,284,597,576,619,690,687,742,755,692,747,782,813,752,785,802,793,830,805,860,841,836,879,864,529,204,133,190
107,266,285,570,577,584,613,686,615,620,695,684,741,732,711,748,739,794,751,786,803,800,839,834,861,528,837,188,531, 38,205
286, 13,568,265,586,575,596,591,618,685,616,655,696,693,740,733,712,749,738,795,792,831,804,799,838,833,722,527,206,189,134
263,106,287,508,571,590,587,574,621,592,639,694,683,656,731,710,715,734,787,750,737,796,791,832,721,798,207,532,187,474, 39
 12,417,264,567,288,509,572,595,588,617,654,657,640,697,680,713,730,709,716,735,788,727,720,797,790,723,526,473,208,135,186
105,262,289,416,507,566,589,512,573,622,593,638,653,682,659,698,679,714,729,708,717,736,789,726,719,472,533,184,475, 40,209
290, 11,418,261,502,415,510,565,594,513,562,641,658,637,652,681,660,699,678,669,728,707,718,675,724,525,704,471,210,185,136
259,104,291,414,419,506,503,514,511,564,623,548,561,642,551,636,651,670,661,700,677,674,725,706,703,534,211,476,183,396, 41
 10,331,260,493,292,501,420,495,504,515,498,563,624,549,560,643,662,635,650,671,668,701,676,673,524,705,470,395,212,137,182
103,258,293,330,413,494,505,500,455,496,547,516,485,552,625,550,559,644,663,634,649,672,667,702,535,394,477,180,397, 42,213
294,  9,332,257,492,329,456,421,490,499,458,497,546,517,484,553,626,543,558,645,664,633,648,523,666,469,536,393,220,181,138
255,102,295,328,333,412,491,438,457,454,489,440,459,486,545,518,483,554,627,542,557,646,665,632,537,478,221,398,179,214, 43
  8,319,256,335,296,345,326,409,422,439,436,453,488,441,460,451,544,519,482,555,628,541,522,647,468,631,392,219,222,139,178
101,254,297,320,327,334,411,346,437,408,423,368,435,452,487,442,461,450,445,520,481,556,629,538,479,466,399,176,215, 44,165
298,  7,318,253,336,325,344,349,410,347,360,407,424,383,434,427,446,443,462,449,540,521,480,467,630,391,218,223,164,177,140
251,100,303,300,321,316,337,324,343,350,369,382,367,406,425,384,433,428,447,444,463,430,539,390,465,400,175,216,169,166, 45
  6,299,252,317,304,301,322,315,348,361,342,359,370,381,366,405,426,385,432,429,448,389,464,401,174,217,224,163,150,141,168
 99,250,241,302,235,248,307,338,323,314,351,362,341,358,371,380,365,404,377,386,431,402,173,388,225,160,153,170,167, 46,143
240,  5, 98,249,242,305,234,247,308,339,232,313,352,363,230,357,372,379,228,403,376,387,226,159,154,171,162,149,142,151, 82
 63,  2,239, 66, 97,236,243,306,233,246,309,340,231,312,353,364,229,356,373,378,227,158,375,172,161,148,155,152, 83,144, 47
  4, 67, 64, 61,238, 69, 96, 59,244, 71, 94, 57,310, 73, 92, 55,354, 75, 90, 53,374, 77, 88, 51,156, 79, 86, 49,146, 81, 84
  1, 62,  3, 68, 65, 60,237, 70, 95, 58,245, 72, 93, 56,311, 74, 91, 54,355, 76, 89, 52,157, 78, 87, 50,147, 80, 85, 48,145

C#

<lang csharp>using System; using System.Collections.Generic;

namespace prog { class MainClass { const int N = 8;

readonly static int[,] moves = { {+1,-2},{+2,-1},{+2,+1},{+1,+2}, {-1,+2},{-2,+1},{-2,-1},{-1,-2} }; struct ListMoves { public int x, y; public ListMoves( int _x, int _y ) { x = _x; y = _y; } }

public static void Main (string[] args) { int[,] board = new int[N,N]; board.Initialize();

int x = 0, // starting position y = 0;

List<ListMoves> list = new List<ListMoves>(N*N); list.Add( new ListMoves(x,y) );

do { if ( Move_Possible( board, x, y ) ) { int move = board[x,y]; board[x,y]++; x += moves[move,0]; y += moves[move,1]; list.Add( new ListMoves(x,y) ); } else { if ( board[x,y] >= 8 ) { board[x,y] = 0; list.RemoveAt(list.Count-1); if ( list.Count == 0 ) { Console.WriteLine( "No solution found." ); return; } x = list[list.Count-1].x; y = list[list.Count-1].y; } board[x,y]++; } } while( list.Count < N*N );

int last_x = list[0].x, last_y = list[0].y; string letters = "ABCDEFGH"; for( int i=1; i<list.Count; i++ ) { Console.WriteLine( string.Format("{0,2}: ", i) + letters[last_x] + (last_y+1) + " - " + letters[list[i].x] + (list[i].y+1) );

last_x = list[i].x; last_y = list[i].y; } }

static bool Move_Possible( int[,] board, int cur_x, int cur_y ) { if ( board[cur_x,cur_y] >= 8 ) return false;

int new_x = cur_x + moves[board[cur_x,cur_y],0], new_y = cur_y + moves[board[cur_x,cur_y],1];

if ( new_x >= 0 && new_x < N && new_y >= 0 && new_y < N && board[new_x,new_y] == 0 ) return true;

return false; } } }</lang>

CoffeeScript

This algorithm finds 100,000 distinct solutions to the 8x8 problem in about 30 seconds. It precomputes knight moves up front, so it turns into a pure graph traversal problem. The program uses iteration and backtracking to find solutions. <lang coffeescript> graph_tours = (graph, max_num_solutions) ->

 # graph is an array of arrays
 # graph[3] = [4, 5] means nodes 4 and 5 are reachable from node 3
 #
 # Returns an array of tours (up to max_num_solutions in size), where
 # each tour is an array of nodes visited in order, and where each
 # tour visits every node in the graph exactly once.
 #
 complete_tours = []
 visited = (false for node in graph)
 dead_ends = ({} for node in graph)
 tour = [0]
 
 valid_neighbors = (i) ->
   arr = []
   for neighbor in graph[i]
     continue if visited[neighbor]
     continue if dead_ends[i][neighbor]
     arr.push neighbor
   arr
   
 next_square_to_visit = (i) ->
   arr = valid_neighbors i
   return null if arr.length == 0

   # We traverse to our neighbor who has the fewest neighbors itself.
   fewest_neighbors = valid_neighbors(arr[0]).length
   neighbor = arr[0]
   for i in [1...arr.length]
     n = valid_neighbors(arr[i]).length
     if n < fewest_neighbors
       fewest_neighbors = n
       neighbor = arr[i]
   neighbor
 
 while tour.length > 0
   current_square = tour[tour.length - 1]
   visited[current_square] = true
   next_square = next_square_to_visit current_square
   if next_square?
     tour.push next_square
     if tour.length == graph.length
       complete_tours.push (n for n in tour) # clone
       break if complete_tours.length == max_num_solutions
     # pessimistically call this a dead end
     dead_ends[current_square][next_square] = true
     current_square = next_square
   else
     # we backtrack
     doomed_square = tour.pop()
     dead_ends[doomed_square] = {}
     visited[doomed_square] = false
 complete_tours

knight_graph = (board_width) ->

 # Turn the Knight's Tour into a pure graph-traversal problem
 # by precomputing all the legal moves.  Returns an array of arrays,
 # where each element in any subarray is the index of a reachable node.
 index = (i, j) ->
   # index squares from 0 to n*n - 1
   board_width * i + j
 
 reachable_squares = (i, j) ->
   deltas = [
     [ 1,  2]
     [ 1, -2]
     [ 2,  1]
     [ 2, -1]
     [-1,  2]
     [-1, -2]
     [-2,  1]
     [-2, -1]
   ]
   neighbors = []
   for delta in deltas
     [di, dj] = delta
     ii = i + di
     jj = j + dj
     if 0 <= ii < board_width
       if 0 <= jj < board_width
         neighbors.push index(ii, jj)
   neighbors
 
 graph = []
 for i in [0...board_width]
   for j in [0...board_width] 
     graph[index(i, j)] = reachable_squares i, j
 graph

illustrate_knights_tour = (tour, board_width) ->

 pad = (n) ->
   return " _" if !n?
   return " " + n if n < 10
   "#{n}"
   
 console.log "\n------"
 moves = {}
 for square, i in tour  
   moves[square] = i + 1
 for i in [0...board_width]
   s = 
   for j in [0...board_width]
     s += "  " + pad moves[i*board_width + j]
   console.log s

BOARD_WIDTH = 8 MAX_NUM_SOLUTIONS = 100000

graph = knight_graph BOARD_WIDTH tours = graph_tours graph, MAX_NUM_SOLUTIONS console.log "#{tours.length} tours found (showing first and last)" illustrate_knights_tour tours[0], BOARD_WIDTH illustrate_knights_tour tours.pop(), BOARD_WIDTH </lang>

output <lang> > time coffee knight.coffee 100000 tours found (showing first and last)

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

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

real 0m29.741s user 0m25.656s sys 0m0.253s </lang>

D

Translation of: C++

<lang d>import std.stdio, std.algorithm, std.random, std.range,

      std.conv, std.typecons, std.typetuple;

int[N][N] knightTour(size_t N=8)(in string start) {

   assert(start.length >= 2);
   alias Tuple!(int,"x", int,"y") P;
   // is enum slower than immutable here?
   immutable P[8] moves = [P(2,1), P(1,2), P(-1,2), P(-2,1),
                           P(-2,-1), P(-1,-2), P(1,-2), P(2,-1)];
   int[N][N] data;

   int[8] sortMoves(in int x, in int y) {
       int[2][8] counts;
       foreach (i, ref d1; moves) {
           int c = 0;
           foreach (ref d2; moves) {
               immutable p = P(x + d1.x + d2.x, y + d1.y + d2.y);
               if (p.x >= 0 && p.x < N && p.y >= 0 && p.y < N &&
                   data[p.y][p.x] == 0)
                   c++;
           }
           //counts[i] = [c, i]; // slow
           counts[i][0] = c;
           counts[i][1] = i;
       }

       counts.randomShuffle(); // shuffle to randomly break ties
       counts[].sort(); // lexicographic sort

       int[8] result;
       transversal(counts[], 1).copy(result[]);
       return result;
   }

   immutable p0 = P(start[0] - 'a', N - to!int(start[1 .. $]));
   data[p0.y][p0.x] = 1;

   Tuple!(int, int, int, int[8])[N * N] order;
   order[0] = tuple(p0.x, p0.y, 0, sortMoves(p0.x, p0.y));

   int n = 0;
   while (n < (N * N - 1)) {
       immutable int x = order[n][0];
       immutable int y = order[n][1];
       bool ok = false;
       foreach (i; order[n][2] .. 8) {
           immutable P d = moves[order[n][3][i]];
           if (x+d.x < 0 || x+d.x >= N || y+d.y < 0 || y+d.y >= N)
               continue;

           if (data[y + d.y][x + d.x] == 0) {
               order[n][2] = i + 1;
               n++;
               data[y + d.y][x + d.x] = n + 1;
               order[n] = tuple(x+d.x,y+d.y,0,sortMoves(x+d.x,y+d.y));
               ok = true;
               break;
           }
       }

       if (!ok) { // Failed. Backtrack.
           data[y][x] = 0;
           n--;
       }
   }

   return data;

}

void main() {

   foreach (i, side; TypeTuple!(5, 8, 31)) {
       immutable form = "%(%" ~ text(text(side ^^ 2).length) ~ "d %)";
       foreach (ref row; knightTour!side(["c3", "b5", "a1"][i]))
           writefln(form, row);
       writeln();
   }

}</lang> Output:

23 16 11  6 21
10  5 22 17 12
15 24  1 20  7
 4  9 18 13  2
25 14  3  8 19

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

275 112  19 116 277 604  21 118 823 770  23 120 961 940  25 122 943 926  27 124 917 898  29 126 911 872  31 128 197 870  33
 18 115 276 601  20 117 772 767  22 119 958 851  24 121 954 941  26 123 936 925  28 125 912 899  30 127 910 871  32 129 198
111 274 113 278 605 760 603 822 771 824 769 948 957 960 939 944 953 942 927 916 929 918 897 908 913 900 873 196 875  34 869
114  17 600 273 602 775 766 773 768 949 850 959 852 947 952 955 932 937 930 935 924 915 920 905 894 909 882 901 868 199 130
271 110 279 606 759 610 761 776 821 764 825 816 951 956 853 938 945 934 923 928 919 896 893 914 907 904 867 874 195 876  35
 16 581 272 599 280 607 774 765 762 779 950 849 826 815 946 933 854 931 844 857 890 921 906 895 886 883 902 881 200 131 194
109 270 281 580 609 758 611 744 777 820 763 780 817 848 827 808 811 846 855 922 843 858 889 892 903 866 885 192 877  36 201
282  15 582 269 598 579 608 757 688 745 778 819 754 783 814 847 828 807 810 845 856 891 842 859 884 887 880 863 202 193 132
267 108 283 578 583 612 689 614 743 756 691 746 781 818 753 784 809 812 829 806 801 840 835 888 865 862 203 878 191 530  37
 14 569 268 585 284 597 576 619 690 687 742 755 692 747 782 813 752 785 802 793 830 805 860 841 836 879 864 529 204 133 190
107 266 285 570 577 584 613 686 615 620 695 684 741 732 711 748 739 794 751 786 803 800 839 834 861 528 837 188 531  38 205
286  13 568 265 586 575 596 591 618 685 616 655 696 693 740 733 712 749 738 795 792 831 804 799 838 833 722 527 206 189 134
263 106 287 508 571 590 587 574 621 592 639 694 683 656 731 710 715 734 787 750 737 796 791 832 721 798 207 532 187 474  39
 12 417 264 567 288 509 572 595 588 617 654 657 640 697 680 713 730 709 716 735 788 727 720 797 790 723 526 473 208 135 186
105 262 289 416 507 566 589 512 573 622 593 638 653 682 659 698 679 714 729 708 717 736 789 726 719 472 533 184 475  40 209
290  11 418 261 502 415 510 565 594 513 562 641 658 637 652 681 660 699 678 669 728 707 718 675 724 525 704 471 210 185 136
259 104 291 414 419 506 503 514 511 564 623 548 561 642 551 636 651 670 661 700 677 674 725 706 703 534 211 476 183 396  41
 10 331 260 493 292 501 420 495 504 515 498 563 624 549 560 643 662 635 650 671 668 701 676 673 524 705 470 395 212 137 182
103 258 293 330 413 494 505 500 455 496 547 516 485 552 625 550 559 644 663 634 649 672 667 702 535 394 477 180 397  42 213
294   9 332 257 492 329 456 421 490 499 458 497 546 517 484 553 626 543 558 645 664 633 648 523 666 469 536 393 220 181 138
255 102 295 328 333 412 491 438 457 454 489 440 459 486 545 518 483 554 627 542 557 646 665 632 537 478 221 398 179 214  43
  8 319 256 335 296 345 326 409 422 439 436 453 488 441 460 451 544 519 482 555 628 541 522 647 468 631 392 219 222 139 178
101 254 297 320 327 334 411 346 437 408 423 368 435 452 487 442 461 450 445 520 481 556 629 538 479 466 399 176 215  44 165
298   7 318 253 336 325 344 349 410 347 360 407 424 383 434 427 446 443 462 449 540 521 480 467 630 391 218 223 164 177 140
251 100 303 300 321 316 337 324 343 350 369 382 367 406 425 384 433 428 447 444 463 430 539 390 465 400 175 216 169 166  45
  6 299 252 317 304 301 322 315 348 361 342 359 370 381 366 405 426 385 432 429 448 389 464 401 174 217 224 163 150 141 168
 99 250 241 302 235 248 307 338 323 314 351 362 341 358 371 380 365 404 377 386 431 402 173 388 225 160 153 170 167  46 143
240   5  98 249 242 305 234 247 308 339 232 313 352 363 230 357 372 379 228 403 376 387 226 159 154 171 162 149 142 151  82
 63   2 239  66  97 236 243 306 233 246 309 340 231 312 353 364 229 356 373 378 227 158 375 172 161 148 155 152  83 144  47
  4  67  64  61 238  69  96  59 244  71  94  57 310  73  92  55 354  75  90  53 374  77  88  51 156  79  86  49 146  81  84
  1  62   3  68  65  60 237  70  95  58 245  72  93  56 311  74  91  54 355  76  89  52 157  78  87  50 147  80  85  48 145

Go

<lang go>/* Adapted from "Enumerating Knight's Tours using an Ant Colony Algorithm" by Philip Hingston and Graham Kendal, PDF at http://www.cs.nott.ac.uk/~gxk/papers/cec05knights.pdf. */

package main

import (

   "fmt"
   "math/rand"
   "sync" 
   "time"

)

const boardSize = 8 const nSquares = boardSize * boardSize const completeTour = nSquares - 1

// task input: starting square. These are 1 based, but otherwise 0 based // row and column numbers are used througout the program. const rStart = 2 const cStart = 3

// pheromone representation read by ants var tNet = make([]float64, nSquares*8)

// row, col deltas of legal moves var drc = [][]int{{1, 2}, {2, 1}, {2, -1}, {1, -2},

   {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}

// get square reached by following edge k from square (r, c) func dest(r, c, k int) (int, int, bool) {

   r += drc[k][0]
   c += drc[k][1]
   return r, c, r >= 0 && r < boardSize && c >= 0 && c < boardSize

}

// struct represents a pheromone amount associated with a move type rckt struct {

   r, c, k int
   t       float64

}

func main() {

   fmt.Println("Starting square:  row", rStart, "column", cStart)
   // initialize board
   for r := 0; r < boardSize; r++ {
       for c := 0; c < boardSize; c++ {
           for k := 0; k < 8; k++ { 
               if _, _, ok := dest(r, c, k); ok {
                   tNet[(r*boardSize+c)*8+k] = 1e-6
               }
           }
       }
   }

   // waitGroups for ant release clockwork
   var start, reset sync.WaitGroup
   start.Add(1)
   // channel for ants to return tours with pheremone updates
   tch := make(chan []rckt)

   // create an ant for each square
   for r := 0; r < boardSize; r++ {
       for c := 0; c < boardSize; c++ {
           go ant(r, c, &start, &reset, tch)
       }
   }

   // accumulator for new pheromone amounts
   tNew := make([]float64, nSquares*8)

   // each iteration is a "cycle" as described in the paper
   for {
       // evaporate pheromones
       for i := range tNet {
           tNet[i] *= .75
       }

       reset.Add(nSquares) // number of ants to release
       start.Done()        // release them
       reset.Wait()        // wait for them to begin searching
       start.Add(1)        // reset start signal for next cycle

       // gather tours from ants
       for i := 0; i < nSquares; i++ {
           tour := <-tch
           // watch for a complete tour from the specified starting square
           if len(tour) == completeTour &&
               tour[0].r == rStart-1 && tour[0].c == cStart-1 {

               // task output:  move sequence in a grid.
               seq := make([]int, nSquares)
               for i, sq := range tour {
                   seq[sq.r*boardSize+sq.c] = i + 1
               }
               last := tour[len(tour)-1]
               r, c, _ := dest(last.r, last.c, last.k)
               seq[r*boardSize+c] = nSquares
               fmt.Println("Move sequence:")
               for r := 0; r < boardSize; r++ {
                   for c := 0; c < boardSize; c++ {
                       fmt.Printf(" %3d", seq[r*boardSize+c])
                   }
                   fmt.Println()
               }
               return // task only requires finding a single tour
           }
           // accumulate pheromone amounts from all ants
           for _, move := range tour {
               tNew[(move.r*boardSize+move.c)*8+move.k] += move.t
           }
       }
   
       // update pheromone amounts on network, reset accumulator
       for i, tn := range tNew {
           tNet[i] += tn
           tNew[i] = 0
       }
   }

}

type square struct {

   r, c int

}

func ant(r, c int, start, reset *sync.WaitGroup, tourCh chan []rckt) {

   rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
   tabu := make([]square, nSquares)
   moves := make([]rckt, nSquares)
   unexp := make([]rckt, 8)
   tabu[0].r = r
   tabu[0].c = c

   for {
       // cycle initialization
       moves = moves[:0]
       tabu = tabu[:1]
       r := tabu[0].r
       c := tabu[0].c

       // wait for start signal
       start.Wait()
       reset.Done()

       for {
           // choose next move
           unexp = unexp[:0]
           var tSum float64
       findU:
           for k := 0; k < 8; k++ {
               dr, dc, ok := dest(r, c, k)
               if !ok {
                   continue
               }
               for _, t := range tabu {
                   if t.r == dr && t.c == dc {
                       continue findU
                   }
               }
               tk := tNet[(r*boardSize+c)*8+k]
               tSum += tk
               // note:  dest r, c stored here
               unexp = append(unexp, rckt{dr, dc, k, tk})
           }
           if len(unexp) == 0 {
               break // no moves
           }
           rn := rnd.Float64() * tSum
           var move rckt
           for _, move = range unexp {
               if rn <= move.t {
                   break
               }
               rn -= move.t
           }

           // move to new square
           move.r, r = r, move.r
           move.c, c = c, move.c
           tabu = append(tabu, square{r, c})
           moves = append(moves, move)
       }

       // compute pheromone amount to leave
       for i := range moves {
           moves[i].t = float64(len(moves)-i) / float64(completeTour-i)
       }

       // return tour found for this cycle
       tourCh <- moves
   }

}</lang> Output:

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

Haskell

<lang Haskell> import System (getArgs) import Data.Char (ord, chr) import Data.List (minimumBy, (\\), intercalate, sort) import Data.Ord (comparing)

type Square = (Int, Int)

board :: [Square] board = [ (x,y) | x <- [1..8], y <- [1..8] ]

knightMoves :: Square -> [Square] knightMoves (x,y) = filter (flip elem board) jumps

 where jumps = [ (x+i,y+j) | i <- jv, j <- jv, abs i /= abs j ]
       jv    = [1,-1,2,-2]

knightTour :: [Square] -> [Square] knightTour moves

   | candMoves == [] = reverse moves
   | otherwise = knightTour $ newSquare : moves
 where newSquare = minimumBy (comparing (length . findMoves)) candMoves
       candMoves = findMoves $ head moves
       findMoves sq = knightMoves sq \\ moves

main :: IO () main = do

   sq <- fmap (toSq . head) getArgs
   printTour $ map toAlg $ knightTour [sq]
 where toAlg (x,y) = [chr (x + 96), chr (y + 48)]
       toSq [x,y] = ((ord x) - 96, (ord y) - 48)
       printTour [] = return ()
       printTour tour = do
           putStrLn $ intercalate " -> " $ take 8 tour
           printTour $ drop 8 tour

</lang>

Output:

e5 -> f7 -> h8 -> g6 -> h4 -> g2 -> e1 -> f3
g1 -> h3 -> g5 -> h7 -> f8 -> d7 -> b8 -> a6
b4 -> a2 -> c1 -> d3 -> b2 -> a4 -> b6 -> a8
c7 -> e8 -> g7 -> h5 -> f4 -> e6 -> d8 -> b7
c5 -> b3 -> a1 -> c2 -> a3 -> b1 -> d2 -> c4
a5 -> c6 -> a7 -> c8 -> d6 -> b5 -> d4 -> e2
c3 -> d1 -> f2 -> h1 -> g3 -> e4 -> f6 -> g8
h6 -> g4 -> h2 -> f1 -> e3 -> f5 -> e7 -> d5

Icon and Unicon

This implements Warnsdorff's algorithm using unordered sets.

The board must be square (it has only been tested on 8x8 and 7x7). Currently the maximum size board (due to square notation) is 26x26.
Tie breaking is selectable with 3 variants supplied (first in list, random, and Roth's distance heuristic).
A debug log can be generated showing the moves and choices considered for tie breaking.

The algorithm doesn't always generate a complete tour. <lang Icon>link printf

procedure main(A) ShowTour(KnightsTour(Board(8))) end

procedure KnightsTour(B,sq,tbrk,debug) #: Warnsdorff’s algorithm

/B := Board(8) # create 8x8 board if none given /sq := ?B.files || ?B.ranks # random initial position (default) sq2fr(sq,B) # validate initial sq if type(tbrk) == "procedure" then

  B.tiebreak := tbrk                   # override tie-breaker

if \debug then write("Debug log : move#, move : (accessibility) choices")

choices := [] # setup to track moves and choices every (movesto := table())[k := key(B.movesto)] := copy(B.movesto[k])

B.tour := [] # new tour repeat {

  put(B.tour,sq)                       # record move
   
  ac := 9                              # accessibility counter > maximum
  while get(choices)                   # empty choices for tiebreak
  every delete(movesto[nextsq := !movesto[sq]],sq) do {  # make sq unavailable
     if ac >:= *movesto[nextsq] then   # reset to lower accessibility count
        while get(choices)             # . re-empty choices      
     if ac = *movesto[nextsq] then
        put(choices,nextsq)            # keep least accessible sq and any ties
     } 
  
  if \debug then {                     # move#, move, (accessibility), choices
     writes(sprintf("%d. %s : (%d) ",*B.tour,sq,ac)) 
     every writes(" ",!choices|"\n")                 
     }
  sq := B.tiebreak(choices,B) | break  # choose next sq until out of choices
  }

return B end

procedure RandomTieBreaker(S,B) # random choice return ?S end

procedure FirstTieBreaker(S,B) # first one in the list return !S end

procedure RothTieBreaker(S,B) # furthest from the center if *S = 0 then fail # must fail if [] every fr := sq2fr(s := !S,B) do {

  d := sqrt(abs(fr[1]-1 - (B.N-1)*0.5)^2 + abs(fr[2]-1 - (B.N-1)*0.5)^2)
  if (/md := d) | ( md >:= d) then msq := s     # save sq 
  }

return msq end

record board(N,ranks,files,movesto,tiebreak,tour) # structure for board

procedure Board(N) #: create board N := *&lcase >=( 0 < integer(N)) | stop("N=",image(N)," is out of range.") B := board(N,[],&lcase[1+:N],table(),RandomTieBreaker) # setup every put(B.ranks,N to 1 by -1) # add rank #s every sq := !B.files || !B.ranks do # for each sq add

  every insert(B.movesto[sq] := set(), KnightMoves(sq,B))   # moves to next sq

return B end

procedure sq2fr(sq,B) #: return numeric file & rank f := find(sq[1],B.files) | runerr(205,sq) r := integer(B.ranks[sq[2:0]]) | runerr(205,sq) return [f,r] end

procedure KnightMoves(sq,B) #: generate all Kn accessible moves from sq fr := sq2fr(sq,B) every ( i := -2|-1|1|2 ) & ( j := -2|-1|1|2 ) do

  if (abs(i)~=abs(j)) & (0<(ri:=fr[2]+i)<=B.N) & (0<(fj:=fr[1]+j)<=B.N) then
     suspend B.files[fj]||B.ranks[ri]

end

procedure ShowTour(B) #: show the tour write("Board size = ",B.N) write("Tour length = ",*B.tour) write("Tie Breaker = ",image(B.tiebreak))

every !(squares := list(B.N)) := list(B.N,"-") every fr := sq2fr(B.tour[m := 1 to *B.tour],B) do

  squares[fr[2],fr[1]] := m

every (hdr1 := " ") ||:= right(!B.files,3) every (hdr2 := " +") ||:= repl((1 to B.N,"-"),3) | "-+"

every write(hdr1|hdr2) every r := 1 to B.N do {

  writes(right(B.ranks[r],3)," |")
  every writes(right(squares[r,f := 1 to B.N],3))
  write(" |",right(B.ranks[r],3))
  }

every write(hdr2|hdr1|&null) end</lang>

The following can be used when debugging to validate the board structure and to image the available moves on the board. <lang Icon>procedure DumpBoard(B) #: Dump Board internals write("Board size=",B.N) write("Available Moves at start of tour:", ImageMovesTo(B.movesto)) end

procedure ImageMovesTo(movesto) #: image of available moves every put(K := [],key(movesto)) every (s := "\n") ||:= (k := !sort(K)) || " : " do

  every s ||:= " " || (!sort(movesto[k])|"\n")

return s end</lang>

Sample output:

Board size = 8
Tour length = 64
Tie Breaker = procedure RandomTieBreaker
       a  b  c  d  e  f  g  h
    +-------------------------+
  8 | 53 10 29 26 55 12 31 16 |  8
  7 | 28 25 54 11 30 15 48 13 |  7
  6 |  9 52 27 62 47 56 17 32 |  6
  5 | 24 61 38 51 36 45 14 49 |  5
  4 | 39  8 63 46 57 50 33 18 |  4
  3 | 64 23 60 37 42 35 44  3 |  3
  2 |  7 40 21 58  5  2 19 34 |  2
  1 | 22 59  6 41 20 43  4  1 |  1
    +-------------------------+
       a  b  c  d  e  f  g  h

Two 7x7 boards:

Board size = 7
Tour length = 33
Tie Breaker = procedure RandomTieBreaker
       a  b  c  d  e  f  g
    +----------------------+
  7 | 33  4 15  - 29  6 17 |  7
  6 | 14  - 30  5 16  - 28 |  6
  5 |  3 32  -  -  - 18  7 |  5
  4 |  - 13  - 31  - 27  - |  4
  3 | 23  2  -  -  -  8 19 |  3
  2 | 12  - 24 21 10  - 26 |  2
  1 |  1 22 11  - 25 20  9 |  1
    +----------------------+
       a  b  c  d  e  f  g

Board size = 7
Tour length = 49
Tie Breaker = procedure RothTieBreaker
       a  b  c  d  e  f  g
    +----------------------+
  7 | 35 14 21 46  7 12  9 |  7
  6 | 20 49 34 13 10 23  6 |  6
  5 | 15 36 45 22 47  8 11 |  5
  4 | 42 19 48 33 40  5 24 |  4
  3 | 37 16 41 44 27 32 29 |  3
  2 | 18 43  2 39 30 25  4 |  2
  1 |  1 38 17 26  3 28 31 |  1
    +----------------------+
       a  b  c  d  e  f  g

J

Solution:
The Knight's tour essay on the Jwiki shows a couple of solutions including one using Warnsdorffs algorithm. <lang j>NB. knight moves for each square of a (y,y) board kmoves=: monad define

t=. (>,{;~i.y) +"1/ _2]\2 1 2 _1 1 2 1 _2 _1 2 _1 _2 _2 1 _2 _1
(*./"1 t e. i.y) <@#"1 y#.t

)

ktourw=: monad define

M=. >kmoves y
p=. k=. 0
b=. 1 $~ *:y
for. i.<:*:y do.
 b=. 0 k}b
 p=. p,k=. ((i.<./) +/"1 b{~j{M){j=. ({&b # ]) k{M 
end.
assert. ~:p
(,~y)$/:p

)</lang>

Example Use: <lang j> ktourw 8 NB. solution for an 8 x 8 board

0 25 14 23 28 49 12 31

15 22 27 50 13 30 63 48 26 1 24 29 62 59 32 11 21 16 51 58 43 56 47 60

2 41 20 55 52 61 10 33

17 38 53 42 57 44 7 46 40 3 36 19 54 5 34 9 37 18 39 4 35 8 45 6

  9!:37]0 64 4 4  NB. truncate lines longer than 64 characters and only show first and last four lines

  ktourw 202 NB. 202x202 board -- this implementation failed for 200 and 201
   0   401   414   405   398   403   424   417   396   419   43...
 413   406   399   402   425   416   397   420   439   430   39...
 400     1   426   415   404   423   448   429   418   437 4075...
 409   412   407   446   449   428   421   440 40739 40716   43...

...

 550    99   560   569  9992   779   786   773 10002  9989   78...
 555   558   553   778   563   570   775   780   785   772 1000...
 100   551   556   561   102   777   572   771   104   781   57...
 557   554   101   552   571   562   103   776   573   770   10...</lang>

Java

<lang java>import java.util.*;

public class KnightsTour {

   private final static int base = 12;
   private final static int[][] moves = {{1,-2},{2,-1},{2,1},{1,2},{-1,2},
       {-2,1},{-2,-1},{-1,-2}};
   private static int[][] grid;
   private static int total;

   public static void main(String[] args) {
       grid = new int[base][base];
       total = (base - 4) * (base - 4);

       for (int r = 0; r < base; r++)
           for (int c = 0; c < base; c++)
               if (r < 2 || r > base - 3 || c < 2 || c > base - 3)
                   grid[r][c] = -1;

       int row = 2 + (int) (Math.random() * (base - 4));
       int col = 2 + (int) (Math.random() * (base - 4));

       grid[row][col] = 1;

       if (solve(row, col, 2))
           printResult();
       else System.out.println("no result");

   private static boolean solve(int r, int c, int count) {
       if (count > total)
           return true;

       List<int[]> nbrs = neighbors(r, c);

       if (nbrs.isEmpty() && count != total)
           return false;

       Collections.sort(nbrs, new Comparator<int[]>() {
           public int compare(int[] a, int[] b) {
               return a[2] - b[2];
           }
       });

       for (int[] nb : nbrs) {
           r = nb[0];
           c = nb[1];
           grid[r][c] = count;
           if (!orphanDetected(count) && solve(r, c, count + 1))
               return true;
           grid[r][c] = 0;
       }

       return false;
   }

   private static List neighbors(int r, int c) {
       List nbrs = new ArrayList<>();

       for (int[] m : moves) {
           int x = m[0];
           int y = m[1];
           if (grid[r + y][c + x] == 0) {
               int num = countNeighbors(r + y, c + x);
               nbrs.add(new int[]{r + y, c + x, num});
           }
       }
       return nbrs;
   }

   private static int countNeighbors(int r, int c) {
       int num = 0;
       for (int[] m : moves) {
           int x = m[0];
           int y = m[1];
           if (grid[r + y][c + x] == 0)
               num++;
       }
       return num;
   }

   private static boolean orphanDetected(int count) {
       if (count < total - 1) {
           for (int r = 2; r < base-2; r++)
               for (int c = 2; c < base-2; c++)
                   if (grid[r][c] == 0 && countNeighbors(r, c) == 0)
                       return true;
       }
       return false;
   }

   private static void printResult() {
       for (int[] row : grid) {
           for (int i : row) {
               if (i == -1) continue;
               System.out.printf("%2d ", i);
           }
           System.out.println();
       }
   }

}</lang>

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

Lua

<lang lua>N = 8

moves = { {1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2} }

function Move_Allowed( board, x, y )

   if board[x][y] >= 8 then return false end

   local new_x, new_y = x + moves[board[x][y]+1][1], y + moves[board[x][y]+1][2]    
   if new_x >= 1 and new_x <= N and new_y >= 1 and new_y <= N and board[new_x][new_y] == 0 then return true end
   
   return false

end

board = {} for i = 1, N do

   board[i] = {}
   for j = 1, N do
       board[i][j] = 0
   end

end

x, y = 1, 1

lst = {} lst[1] = { x, y }

repeat

   if Move_Allowed( board, x, y ) then
       board[x][y] = board[x][y] + 1
       x, y = x+moves[board[x][y]][1], y+moves[board[x][y]][2]
       lst[#lst+1] = { x, y }
   else
       if board[x][y] >= 8 then
           board[x][y] = 0
           lst[#lst] = nil
           if #lst == 0 then
               print "No solution found."
               os.exit(1)
           end
           x, y = lst[#lst][1], lst[#lst][2]
       end
       board[x][y] = board[x][y] + 1    
   end

until #lst == N^2

last = lst[1] for i = 2, #lst do

   print( string.format( "%s%d - %s%d", string.sub("ABCDEFGH",last[1],last[1]), last[2], string.sub("ABCDEFGH",lst[i][1],lst[i][1]), lst[i][2] ) )
   last = lst[i]

end</lang>

Mathprog

While a little slower than using Warnsdorff this solution is interesting:

1. It shows that Hidato (see: http://rosettacode.org/wiki/Hidato) and Knights Tour are essentially the same problem.

2. It is possible to specify which square is used for any Knights Move.

<lang> /*Knights.mathprog

 Find a Knights Tour

 Nigel_Galloway
 January 11th., 2012

/

param ZBLS; param ROWS; param COLS; param D := 2; set ROWSR := 1..ROWS; set COLSR := 1..COLS; set ROWSV := (1-D)..(ROWS+D); set COLSV := (1-D)..(COLS+D); param Iz{ROWSR,COLSR}, integer, default 0; set ZBLSV := 1..(ZBLS+1); set ZBLSR := 1..ZBLS;

var BR{ROWSV,COLSV,ZBLSV}, binary;

void0{r in ROWSV, z in ZBLSR,c in (1-D)..0}: BR[r,c,z] = 0; void1{r in ROWSV, z in ZBLSR,c in (COLS+1)..(COLS+D)}: BR[r,c,z] = 0; void2{c in COLSV, z in ZBLSR,r in (1-D)..0}: BR[r,c,z] = 0; void3{c in COLSV, z in ZBLSR,r in (ROWS+1)..(ROWS+D)}: BR[r,c,z] = 0; void4{r in ROWSV,c in (1-D)..0}: BR[r,c,ZBLS+1] = 1; void5{r in ROWSV,c in (COLS+1)..(COLS+D)}: BR[r,c,ZBLS+1] = 1; void6{c in COLSV,r in (1-D)..0}: BR[r,c,ZBLS+1] = 1; void7{c in COLSV,r in (ROWS+1)..(ROWS+D)}: BR[r,c,ZBLS+1] = 1;

Izfree{r in ROWSR, c in COLSR, z in ZBLSR : Iz[r,c] = -1}: BR[r,c,z] = 0; Iz1{Izr in ROWSR, Izc in COLSR, r in ROWSR, c in COLSR, z in ZBLSR : Izr=r and Izc=c and Iz[Izr,Izc]=z}: BR[r,c,z] = 1;

rule1{z in ZBLSR}: sum{r in ROWSR, c in COLSR} BR[r,c,z] = 1; rule2{r in ROWSR, c in COLSR}: sum{z in ZBLSV} BR[r,c,z] = 1; rule3{r in ROWSR, c in COLSR, z in ZBLSR}: BR[0,0,z+1] + BR[r-1,c-2,z+1] + BR[r-1,c+2,z+1] + BR[r-2,c-1,z+1] + BR[r-2,c+1,z+1] + BR[r+1,c+2,z+1] + BR[r+1,c-2,z+1] + BR[r+2,c-1,z+1] + BR[r+2,c+1,z+1] - BR[r,c,z] >= 0;

solve;

for {r in ROWSR} {

   for {c in COLSR} {
       printf " %2d", sum{z in ZBLSR} BR[r,c,z]*z;
   }                                                                     
   printf "\n";

} data;

param ROWS := 5; param COLS := 5; param ZBLS := 25; param Iz: 1 2 3 4 5 :=

1  .   .   .   .  .
2  .  19   2   .  .
3  .   .   .   .  . 
4  .   .   .   .  .
5  .   .   .   .  .
;

end;

</lang>

Produces:

<lang> GLPSOL: GLPK LP/MIP Solver, v4.47 Parameter(s) specified in the command line:

--minisat --math Knights.mathprog

Reading model section from Knights.mathprog... Reading data section from Knights.mathprog... 62 lines were read Generating void0... Generating void1... Generating void2... Generating void3... Generating void4... Generating void5... Generating void6... Generating void7... Generating Izfree... Generating Iz1... Generating rule1... Generating rule2... Generating rule3... Model has been successfully generated Will search for ANY feasible solution Translating to CNF-SAT... Original problem has 2549 rows, 2106 columns, and 9349 non-zeros 575 covering inequalities 1924 partitioning equalities Solving CNF-SAT problem... Instance has 3356 variables, 10874 clauses, and 34549 literals

============================[MINISAT]=============================

==================================================================

| 0 | 9000 32675 | 3000 0 0 0.0 | 0.000 % | | 101 | 6025 21551 | 3300 93 1620 17.4 | 57.688 % | | 251 | 6025 21551 | 3630 243 4961 20.4 | 57.688 % |

==================================================================

SATISFIABLE Objective value = 0.000000000e+000 Time used: 0.0 secs Memory used: 6.5 Mb (6775701 bytes)

 1 12  7 18  3
 6 19  2 13  8
11 22 15  4 17
20  5 24  9 14
23 10 21 16 25

Model has been successfully processed </lang>

and

<lang> /*Knights.mathprog

 Find a Knights Tour

 Nigel_Galloway
 January 11th., 2012

/

param ZBLS; param ROWS; param COLS; param D := 2; set ROWSR := 1..ROWS; set COLSR := 1..COLS; set ROWSV := (1-D)..(ROWS+D); set COLSV := (1-D)..(COLS+D); param Iz{ROWSR,COLSR}, integer, default 0; set ZBLSV := 1..(ZBLS+1); set ZBLSR := 1..ZBLS;

var BR{ROWSV,COLSV,ZBLSV}, binary;

void0{r in ROWSV, z in ZBLSR,c in (1-D)..0}: BR[r,c,z] = 0; void1{r in ROWSV, z in ZBLSR,c in (COLS+1)..(COLS+D)}: BR[r,c,z] = 0; void2{c in COLSV, z in ZBLSR,r in (1-D)..0}: BR[r,c,z] = 0; void3{c in COLSV, z in ZBLSR,r in (ROWS+1)..(ROWS+D)}: BR[r,c,z] = 0; void4{r in ROWSV,c in (1-D)..0}: BR[r,c,ZBLS+1] = 1; void5{r in ROWSV,c in (COLS+1)..(COLS+D)}: BR[r,c,ZBLS+1] = 1; void6{c in COLSV,r in (1-D)..0}: BR[r,c,ZBLS+1] = 1; void7{c in COLSV,r in (ROWS+1)..(ROWS+D)}: BR[r,c,ZBLS+1] = 1;

Izfree{r in ROWSR, c in COLSR, z in ZBLSR : Iz[r,c] = -1}: BR[r,c,z] = 0; Iz1{Izr in ROWSR, Izc in COLSR, r in ROWSR, c in COLSR, z in ZBLSR : Izr=r and Izc=c and Iz[Izr,Izc]=z}: BR[r,c,z] = 1;

rule1{z in ZBLSR}: sum{r in ROWSR, c in COLSR} BR[r,c,z] = 1; rule2{r in ROWSR, c in COLSR}: sum{z in ZBLSV} BR[r,c,z] = 1; rule3{r in ROWSR, c in COLSR, z in ZBLSR}: BR[0,0,z+1] + BR[r-1,c-2,z+1] + BR[r-1,c+2,z+1] + BR[r-2,c-1,z+1] + BR[r-2,c+1,z+1] + BR[r+1,c+2,z+1] + BR[r+1,c-2,z+1] + BR[r+2,c-1,z+1] + BR[r+2,c+1,z+1] - BR[r,c,z] >= 0;

solve;

for {r in ROWSR} {

   for {c in COLSR} {
       printf " %2d", sum{z in ZBLSR} BR[r,c,z]*z;
   }                                                                     
   printf "\n";

} data;

param ROWS := 8; param COLS := 8; param ZBLS := 64; param Iz: 1 2 3 4 5 6 7 8 :=

1  .   .   .   .  .  .  .  .
2  .   .   .   .  .  . 48  .
3  .   .   .   .  .  .  .  .
4  .   .   .   .  .  .  .  .
5  .   .   .   .  .  .  .  .
6  .   .   .   .  .  .  .  .
7  .  58   .   .  .  .  .  .
8  .   .   .   .  .  .  .  .
;

end;

</lang>

Produces:

<lang> GLPSOL: GLPK LP/MIP Solver, v4.47 Parameter(s) specified in the command line:

--minisat --math Knights.mathprog

Reading model section from Knights.mathprog... Reading data section from Knights.mathprog... 65 lines were read Generating void0... Generating void1... Generating void2... Generating void3... Generating void4... Generating void5... Generating void6... Generating void7... Generating Izfree... Generating Iz1... Generating rule1... Generating rule2... Generating rule3... Model has been successfully generated Will search for ANY feasible solution Translating to CNF-SAT... Original problem has 10466 rows, 9360 columns, and 55330 non-zeros 3968 covering inequalities 6370 partitioning equalities Solving CNF-SAT problem... Instance has 15056 variables, 46754 clauses, and 149794 literals

============================[MINISAT]=============================

==================================================================

| 0 | 40512 143552 | 13504 0 0 0.0 | 0.000 % | | 100 | 32458 114610 | 14854 89 5138 57.7 | 46.633 % | | 250 | 32458 114610 | 16340 239 18544 77.6 | 46.633 % | | 475 | 27499 102956 | 17974 424 42212 99.6 | 46.892 % | | 813 | 27366 102490 | 19771 757 73184 96.7 | 51.541 % | | 1322 | 27366 102490 | 21748 1264 137991 109.2 | 52.245 % | | 2083 | 23226 92730 | 23923 2010 250286 124.5 | 53.620 % | | 3227 | 22239 90284 | 26315 3138 460582 146.8 | 53.620 % | | 4937 | 22239 90284 | 28947 4848 769486 158.7 | 53.620 % | | 7499 | 22206 90168 | 31842 7404 1258240 169.9 | 55.167 % | | 11346 | 21067 87284 | 35026 11248 2085553 185.4 | 55.167 % | | 17113 | 21067 87284 | 38528 17015 3625910 213.1 | 55.167 % | | 25763 | 21067 87284 | 42381 25665 5906283 230.1 | 55.167 % | | 38738 | 21051 87252 | 46619 38638 9316878 241.1 | 55.679 % | | 58199 | 21051 87252 | 51281 16434 3967196 241.4 | 55.685 % | | 87393 | 20707 86474 | 56410 45624 13013357 285.2 | 56.277 % | | 131184 | 20180 84834 | 62051 37252 8996727 241.5 | 56.542 % | | 196871 | 20180 84834 | 68256 49392 13807861 279.6 | 56.542 % | | 295399 | 20180 84834 | 75081 22688 5827696 256.9 | 56.542 % |

==================================================================

SATISFIABLE Objective value = 0.000000000e+000 Time used: 333.0 secs Memory used: 28.2 Mb (29609617 bytes)

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

Model has been successfully processed </lang>

Perl

Knight's tour using Warnsdorffs algorithm <lang perl>use strict; use warnings;

Find a knight's tour

my @board;

Choose starting position - may be passed in on command line; if
not, choose random square.

my ($i, $j); if (my $sq = shift @ARGV) {

 die "$0: illegal start square '$sq'\n" unless ($i, $j) = from_algebraic($sq);

} else {

 ($i, $j) = (int rand 8, int rand 8);

}

Move sequence

my @moves = ();

foreach my $move (1..64) {

 # Record current move
 push @moves, to_algebraic($i,$j);
 $board[$i][$j] = $move++;

 # Get list of possible next moves
 my @targets = possible_moves($i,$j);

 # Find the one with the smallest degree
 my @min = (9);
 foreach my $target (@targets) {
     my ($ni, $nj) = @$target;
     my $next = possible_moves($ni,$nj);
     @min = ($next, $ni, $nj) if $next < $min[0];
 }

 # And make it
 ($i, $j) = @min[1,2];

}

Print the move list

for (my $i=0; $i<4; ++$i) {

 for (my $j=0; $j<16; ++$j) {
   my $n = $i*16+$j;
   print $moves[$n];
   print ', ' unless $n+1 >= @moves;
 }
 print "\n";

} print "\n";

And the board, with move numbers

for (my $i=0; $i<8; ++$i) {

 for (my $j=0; $j<8; ++$j) {
   # Assumes (1) ANSI sequences work, and (2) output 
   # is light text on a dark background.
   print "\e[7m" if ($i%2==$j%2); 
   printf " %2d", $board[$i][$j];
   print "\e[0m";
 }
 print "\n";

}

Find the list of positions the knight can move to from the given square

sub possible_moves {

 my ($i, $j) = @_;
 return grep { $_->[0] >= 0 && $_->[0] < 8 
                   && $_->[1] >= 0 && $_->[1] < 8 
                   && !$board[$_->[0]][$_->[1]] } (
                   [$i-2,$j-1], [$i-2,$j+1], [$i-1,$j-2], [$i-1,$j+2],
                   [$i+1,$j-2], [$i+1,$j+2], [$i+2,$j-1], [$i+2,$j+1]);

}

Return the algebraic name of the square identified by the coordinates
i=rank, 0=black's home row; j=file, 0=white's queen's rook

sub to_algebraic {

  my ($i, $j) = @_;
  chr(ord('a') + $j) . (8-$i);

}

Return the coordinates matching the given algebraic name

sub from_algebraic {

  my $square = shift;
  return unless $square =~ /^([a-h])([1-8])$/;
  return (8-$2, ord($1) - ord('a'));

}</lang>

Sample output (start square c3):

Perl 6

Translation of: Perl

<lang perl6>my @board;

my $I = 8; my $J = 8; my $F = $I*$J > 99 ?? "%3d" !! "%2d";

Choose starting position - may be passed in on command line; if
not, choose random square.

my ($i, $j);

if my $sq = shift @*ARGS {

 die "$*PROGRAM_NAME: illegal start square '$sq'\n" unless ($i, $j) = from_algebraic($sq);

} else {

 ($i, $j) = (^$I).pick, (^$J).pick;

}

Move sequence

my @moves = ();

for 1 .. $I * $J -> $move {

 # Record current move
 push @moves, to_algebraic($i,$j);
 # @board[$i] //= [];	 # (uncomment if autoviv is broken)
 @board[$i][$j] = $move;

 # Find move with the smallest degree
 my @min = (9);
 for possible_moves($i,$j) -> @target {
     my ($ni, $nj) = @target;
     my $next = possible_moves($ni,$nj);
     @min = $next, $ni, $nj if $next < @min[0];
 }

 # And make it
 ($i, $j) = @min[1,2];

}

Print the move list

for @moves.kv -> $i, $m {

   print ',', $i %% 16 ?? "\n" !! " " if $i;
   print $m;

} say "\n";

And the board, with move numbers

for ^$I -> $i {

 for ^$J -> $j {
   # Assumes (1) ANSI sequences work, and (2) output 
   # is light text on a dark background.
   print "\e[7m" if $i % 2 == $j % 2; 
   printf $F, @board[$i][$j];
   print "\e[0m";
 }
 print "\n";

}

Find the list of positions the knight can move to from the given square

sub possible_moves($i,$j) {

 grep -> [$ni, $nj] { $ni ~~ ^$I and $nj ~~ ^$J and !@board[$ni][$nj] }, 
   [$i-2,$j-1], [$i-2,$j+1], [$i-1,$j-2], [$i-1,$j+2],
   [$i+1,$j-2], [$i+1,$j+2], [$i+2,$j-1], [$i+2,$j+1];

}

Return the algebraic name of the square identified by the coordinates
i=rank, 0=black's home row; j=file, 0=white's queen's rook

sub to_algebraic($i,$j) {

   chr(ord('a') + $j) ~ ($I - $i);

}

Return the coordinates matching the given algebraic name

sub from_algebraic($square where /^ (<[a..z]>) (\d+) $/) {

  $I - $1, ord(~$0) - ord('a');

}</lang> (Output identical to Perl's above.)

PicoLisp

<lang PicoLisp>(load "@lib/simul.l")

Build board

(grid 8 8)

Generate legal moves for a given position

(de moves (Tour)

  (extract
     '((Jump)
        (let? Pos (Jump (car Tour))
           (unless (memq Pos Tour)
              Pos ) ) )
     (quote  # (taken from "games/chess.l")
        ((This) (: 0 1  1  0 -1  1  0 -1  1))        # South Southwest
        ((This) (: 0 1  1  0 -1  1  0  1  1))        # West Southwest
        ((This) (: 0 1  1  0 -1 -1  0  1  1))        # West Northwest
        ((This) (: 0 1  1  0 -1 -1  0 -1 -1))        # North Northwest
        ((This) (: 0 1 -1  0 -1 -1  0 -1 -1))        # North Northeast
        ((This) (: 0 1 -1  0 -1 -1  0  1 -1))        # East Northeast
        ((This) (: 0 1 -1  0 -1  1  0  1 -1))        # East Southeast
        ((This) (: 0 1 -1  0 -1  1  0 -1  1)) ) ) )  # South Southeast

Build a list of moves, using Warnsdorff’s algorithm

(let Tour '(b1) # Start at b1

  (while
     (mini
        '((P) (length (moves (cons P Tour))))
        (moves Tour) )
     (push 'Tour @) )
  (flip Tour) )</lang>

Output:

-> (b1 a3 b5 a7 c8 b6 a8 c7 a6 b8 d7 f8 h7 g5 h3 g1 e2 c1 a2 b4 c2 a1 b3 a5 b7
d8 c6 d4 e6 c5 a4 c3 d1 b2 c4 d2 f1 h2 f3 e1 d3 e5 f7 h8 g6 h4 g2 f4 d5 e7 g8
h6 g4 e3 f5 d6 e8 g7 h5 f6 e4 g3 h1 f2)

PostScript

You probably shouldn't send this to a printer. Solution using Warnsdorffs algorithm. <lang postscript>%!PS-Adobe-3.0 %%BoundingBox: 0 0 300 300

/s { 300 n div } def /l { rlineto } def

% draws a square /bx { s mul exch s mul moveto s 0 l 0 s l s neg 0 l 0 s neg l } def

% draws checker board /xbd { 1 setgray

       0 0 moveto 300 0 l 0 300 l -300 0 l fill
       .7 1 .6 setrgbcolor
       0 1 n1 { dup 2 mod 2 n1 { 1 index bx fill } for pop } for
       0 setgray

} def

/ar1 { [ exch { 0 } repeat ] } def /ar2 { [ exch dup { dup ar1 exch } repeat pop ] } def

/neighbors {

       -1  2 0
        1  2 0
        2  1 0
        2 -1 0
        1 -2 0
       -1 -2 0
       -2 -1 0
       -2  1 0
       %24 x y add 3 mul roll

} def

/func { 0 dict begin mark } def /var { counttomark -1 1 { 2 add -1 roll def } for cleartomark } def

% x y can_goto -> bool /can_goto {

       func /x /y var
       x 0     ge
       x n     lt
       y 0     ge
       y n     lt
       and and and {
               occupied x get y get 0 eq
       } { false } ifelse
       end

} def

% x y num_access -> number of cells reachable from (x,y) /num_access {

       func /x /y var
       /count 0 def
       x y can_goto {
               neighbors
               8 { pop y add exch x add exch can_goto {
                               /count count 1 add def
                       } if
               } repeat
               count 0 gt { count } { 9 } ifelse
       } { 10 } ifelse
       end

} def

% a circle /marker { x s mul y s mul s 20 div 0 360 arc fill } def

% n solve -> draws board of size n x n, calcs path and draws it /solve {

       func /n var
       /n1 n 1 sub def

       /c false def

       8 n div setlinewidth
       gsave

       0 1 n1 { /x exch def c not {
       0 1 n1 {
               /occupied n ar2 def
               c not {
                       /c true def
                       /y exch def
                       grestore xbd gsave
                       s 2 div dup translate
                       n n mul 2 sub -1 0 { /iter exch def
                               c {
                               0 setgray marker x s mul y s mul moveto
                               occupied x get y 1 put
                               neighbors
                               8 { pop y add exch x add exch 2 copy num_access 24 3 roll } repeat
                               7 { dup 4 index lt { 6 3 roll } if pop pop pop } repeat

                               9 ge iter 0 gt and { /c false def } if
                               /y exch def
                               /x exch def
                               .2 setgray x s mul y s mul lineto stroke
                       } if } for
                       % to be nice, draw box at final position
                       .5 0 0 setrgbcolor marker
                       y .5 sub x .5 sub bx 1 setlinewidth stroke
                       stroke
               } if
       } for } if } for showpage
       grestore
       end

} def

3 1 100 { solve } for

%%EOF</lang>

Prolog

Worlks with SWI-Prolog.
Knights tour using Warnsdorffs algorithm

<lang Prolog>% N is the number of lines of the chessboard knight(N) :- Max is N * N, length(L, Max), knight(N, 0, Max, 0, 0, L), display(N, 0, L).

% knight(NbCol, Coup, Max, Lig, Col, L), % NbCol : number of columns per line % Coup : number of the current move % Max : maximum number of moves % Lig/ Col : current position of the knight % L : the "chessboard"

% the game is over knight(_, Max, Max, _, _, _) :- !.

knight(NbCol, N, MaxN, Lg, Cl, L) :- % Is the move legal Lg >= 0, Cl >= 0, Lg < NbCol, Cl < NbCol,

Pos is Lg * NbCol + Cl, N1 is N+1, % is the place free nth0(Pos, L, N1),

LgM1 is Lg - 1, LgM2 is Lg - 2, LgP1 is Lg + 1, LgP2 is Lg + 2, ClM1 is Cl - 1, ClM2 is Cl - 2, ClP1 is Cl + 1, ClP2 is Cl + 2, maplist(best_move(NbCol, L), [(LgP1, ClM2), (LgP2, ClM1), (LgP2, ClP1),(LgP1, ClP2), (LgM1, ClM2), (LgM2, ClM1), (LgM2, ClP1),(LgM1, ClP2)], R), sort(R, RS), pairs_values(RS, Moves),

move(NbCol, N1, MaxN, Moves, L).

move(NbCol, N1, MaxN, [(Lg, Cl) | R], L) :- knight(NbCol, N1, MaxN, Lg, Cl, L); move(NbCol, N1, MaxN, R, L).

%% An illegal move is scored 1000 best_move(NbCol, _L, (Lg, Cl), 1000-(Lg, Cl)) :- ( Lg < 0 ; Cl < 0; Lg >= NbCol; Cl >= NbCol), !.

best_move(NbCol, L, (Lg, Cl), 1000-(Lg, Cl)) :- Pos is Lg*NbCol+Cl, nth0(Pos, L, V), \+var(V), !.

%% a legal move is scored with the number of moves a knight can make best_move(NbCol, L, (Lg, Cl), R-(Lg, Cl)) :- LgM1 is Lg - 1, LgM2 is Lg - 2, LgP1 is Lg + 1, LgP2 is Lg + 2, ClM1 is Cl - 1, ClM2 is Cl - 2, ClP1 is Cl + 1, ClP2 is Cl + 2, include(possible_move(NbCol, L), [(LgP1, ClM2), (LgP2, ClM1), (LgP2, ClP1),(LgP1, ClP2), (LgM1, ClM2), (LgM2, ClM1), (LgM2, ClP1),(LgM1, ClP2)], Res), length(Res, Len), ( Len = 0 -> R = 1000; R = Len).

% test if a place is enabled possible_move(NbCol, L, (Lg, Cl)) :- % move must be legal Lg >= 0, Cl >= 0, Lg < NbCol, Cl < NbCol, Pos is Lg * NbCol + Cl, % place must be free nth0(Pos, L, V), var(V).

display(_, _, []). display(N, N, L) :- nl, display(N, 0, L).

display(N, M, [H | T]) :- writef('%3r', [H]), M1 is M + 1, display(N, M1, T). </lang>

Output :

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

 ?- knight(20).
   1  40  81  90   3  42  77  94   5  44  73 102   7  46  69  62   9  48  51  60
  82  89   2  41  92  95   4  43  76 101   6  45  72 103   8  47  68  61  10  49
  39  80  91  96 153  78  93 100 129  74 109 104 123  70 111 120  63  50  59  52
  88  83 154  79  98 159 152  75 108 105 128  71 110 121 124  67 112 119  64  11
 155  38  97 160 157 200  99 162 151 130 107 122 127 132 141 118 125  66  53  58
  84  87 156 199 176 161 158 201 106 163 150 131 142 145 126 133 140 113  12  65
  37 182  85 178 207 198 175 164 173 216 143 166 149 222 139 146 117 134  57  54
  86 179 206 197 204 177 208 217 202 165 172 221 144 167 148 223 138  55 114  13
 183  36 181 212 209 218 203 174 215 220 227 170 281 224 303 168 147 116 135  56
 180 211 196 205 230 213 238 219 228 171 280 225 302 169 282 343 304 137  14 115
  35 184 231 210 237 246 229 214 279 226 301 298 283 342 367 308 347 344 305 136
 232 195 236 245 234 239 278 247 300 297 284 359 366 309 348 345 368 307 350  15
 185  34 233 240 261 248 287 296 285 358 299 310 341 378 365 384 349 346 369 306
 194 241 250 235 244 277 260 313 294 311 360 373 364 383 354 379 370 385  16 351
  33 186 243 262 249 288 295 286 361 316 357 340 377 372 395 386 353 380 333 388
 242 193 254 251 276 259 314 293 312 321 374 363 398 355 382 371 394 387 352  17
 187  32 263 258 267 252 289 322 315 362 317 356 339 376 399 396 381 334 389 332
 192 255 190 253 264 275 268 271 292 323 320 375 326 397 338 335 390 393  18  21
  31 188 257 266  29 270 273 290  27 318 327 324  25 336 329 400  23  20 331 392
 256 191  30 189 274 265  28 269 272 291  26 319 328 325  24 337 330 391  22  19
true .

Python

Knights tour using Warnsdorffs algorithm <lang python>import copy

boardsize=6 _kmoves = ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1))

def chess2index(chess, boardsize=boardsize):

   'Convert Algebraic chess notation to internal index format'
   chess = chess.strip().lower()
   x = ord(chess[0]) - ord('a')
   y = boardsize - int(chess[1:])
   return (x, y)

def boardstring(board, boardsize=boardsize):

   r = range(boardsize)
   lines = 
   for y in r:
       lines += '\n' + ','.join('%2i' % board[(x,y)] if board[(x,y)] else '  '
                                for x in r)
   return lines

def knightmoves(board, P, boardsize=boardsize):

   Px, Py = P
   kmoves = set((Px+x, Py+y) for x,y in _kmoves)
   kmoves = set( (x,y)
                 for x,y in kmoves
                 if 0 <= x < boardsize
                    and 0 <= y < boardsize
                    and not board[(x,y)] )
   return kmoves

def accessibility(board, P, boardsize=boardsize):

   access = []
   brd = copy.deepcopy(board)
   for pos in knightmoves(board, P, boardsize=boardsize):
       brd[pos] = -1
       access.append( (len(knightmoves(brd, pos, boardsize=boardsize)), pos) )
       brd[pos] = 0
   return access

def knights_tour(start, boardsize=boardsize, _debug=False):

   board = {(x,y):0 for x in range(boardsize) for y in range(boardsize)}
   move = 1
   P = chess2index(start, boardsize)
   board[P] = move
   move += 1
   if _debug:
       print(boardstring(board, boardsize=boardsize))
   while move <= len(board):
       P = min(accessibility(board, P, boardsize))[1]
       board[P] = move
       move += 1
       if _debug:
           print(boardstring(board, boardsize=boardsize))
           input('\n%2i next: ' % move)
   return board

if __name__ == '__main__':

   while 1:
       boardsize = int(input('\nboardsize: '))
       if boardsize < 5:
           continue
       start = input('Start position: ')
       board = knights_tour(start, boardsize)
       print(boardstring(board, boardsize=boardsize))</lang>

Sample runs

boardsize: 5
Start position: c3

19,12,17, 6,21
 2, 7,20,11,16
13,18, 1,22, 5
 8, 3,24,15,10
25,14, 9, 4,23

boardsize: 8
Start position: h8

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

boardsize: 10
Start position: e6

29, 4,57,24,73, 6,95,10,75, 8
58,23,28, 5,94,25,74, 7,100,11
 3,30,65,56,27,72,99,96, 9,76
22,59, 2,63,68,93,26,81,12,97
31,64,55,66, 1,82,71,98,77,80
54,21,60,69,62,67,92,79,88,13
49,32,53,46,83,70,87,42,91,78
20,35,48,61,52,45,84,89,14,41
33,50,37,18,47,86,39,16,43,90
36,19,34,51,38,17,44,85,40,15

boardsize: 200
Start position: a1

510,499,502,101,508,515,504,103,506,5021 ... 195,8550,6691,6712,197,6704,201,6696,199
501,100,509,514,503,102,507,5020,5005,10 ... 690,6713,196,8553,6692,6695,198,6703,202
498,511,500,4989,516,5019,5004,505,5022, ... ,30180,8559,6694,6711,8554,6705,200,6697
99,518,513,4992,5003,4990,5017,5044,5033 ... 30205,8552,30181,8558,6693,6702,203,6706
512,497,4988,517,5018,5001,5034,5011,504 ... 182,30201,30204,8555,6710,8557,6698,6701
519,98,4993,5002,4991,5016,5043,5052,505 ... 03,30546,30183,30200,30185,6700,6707,204
496,4987,520,5015,5000,5035,5012,5047,51 ... 4,30213,30202,31455,8556,6709,30186,6699
97,522,4999,4994,5013,5042,5051,5060,505 ... 7,31456,31329,30184,30199,30190,205,6708
4986,495,5014,521,5036,4997,5048,5101,50 ... 1327,31454,30195,31472,30187,30198,30189
523,96,4995,4998,5041,5074,5061,5050,507 ... ,31330,31471,31328,31453,30196,30191,206

...

404,731,704,947,958,1013,966,1041,1078,1 ... 9969,39992,39987,39996,39867,39856,39859
 5,706,735,960,955,972,957,1060,1025,106 ... ,39978,39939,39976,39861,39990,297,39866
724,403,730,705,946,967,1012,971,1040,10 ... 9975,39972,39991,39868,39863,39860,39855
707, 4,723,736,729,956,973,996,1061,1026 ... ,39850,39869,39862,39973,39852,39865,298
402,725,708,943,968,945,970,1011,978,997 ... 6567,39974,39851,39864,36571,39854,36573
 3,722,737,728,741,942,977,974,995,1010, ... ,39800,39849,36570,39853,36574,299,14088
720,401,726,709,944,969,742,941,980,975, ... ,14091,36568,36575,14084,14089,36572,843
711, 2,721,738,727,740,715,976,745,940,9 ... 65,36576,14083,14090,36569,844,14087,300
400,719,710,713,398,717,746,743,396,981, ... ,849,304,14081,840,847,302,14085,842,845
 1,712,399,718,739,714,397,716,747,744,3 ... 4078,839,848,303,14082,841,846,301,14086

The 200x200 example warmed my study in its computation but did return a tour.

P.S. There is a slight deviation to a strict interpretation of Warnsdorffs algorithm in that as a conveniance, tuples of the length of the night moves followed by the position are minimized so knights moves with the same length will try and break the ties based on their minimum x,y position. In practice, it seems to give comparable results to the original algorithm.

Ruby

Solve a Knight's Tour
Nigel_Galloway
May 6th., 2012.

class Cell

 def initialize(row=0, col=0, value=nil)
   @adj = [[row-1,col-2],[row-2,col-1],[row-2,col+1],[row-1,col+2],[row+1,col+2],[row+2,col+1],[row+2,col-1],[row+1,col-2]]
   @t = false
   $zbl[value] = false unless value == nil
   @value = value
 end
 def try(value)
   return false if @value == nil
   return true if value > E
   return false if @t
   return false if @value > 0 and @value != value
   return false if @value == 0 and not $zbl[value]
   @t = true
   h = Hash.new
   n = 0
   @adj.each{|x|
     h[Board[x[0]][x[1]].wdof*10+n] = Board[x[0]][x[1]]
     n += 1
   }
   h.sort.each{|key,cell|
     if (cell.try(value+1)) then 
       @value = value
       return true                                  
     end
   }
   @t = false                                      
   return false
 end
 def wdon
   return 0 if @value == nil
   return 0 if @value > 0
   return 0 if @t
   return 1
 end
 def wdof
   res = 0
   @adj.each{|x| res += Board[x[0]][x[1]].wdon}
   return res
 end
 def value                                         
   return @value
 end

end

Rows = 9 Cols = 9 E = 64 $zbl = Array.new(E+1,true) Board = [[Cell.new(),Cell.new(),Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new() ,Cell.new(),Cell.new()],

        [Cell.new(),Cell.new(),Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()      ,Cell.new(),Cell.new()],
        [Cell.new(),Cell.new(),Cell.new(2,2,0),Cell.new(2,3,0),Cell.new(2,4,0),Cell.new(2,5,0),Cell.new(2,6,0),Cell.new(2,7,0),Cell.new(2,8,0),Cell.new(2,9,0) ,Cell.new(),Cell.new()],
        [Cell.new(),Cell.new(),Cell.new(3,2,0),Cell.new(3,3,0),Cell.new(3,4,0),Cell.new(3,5,0),Cell.new(3,6,0),Cell.new(3,7,0),Cell.new(3,8,0),Cell.new(3,9,0) ,Cell.new(),Cell.new()],
        [Cell.new(),Cell.new(),Cell.new(4,2,0),Cell.new(4,3,0),Cell.new(4,4,0),Cell.new(4,5,0),Cell.new(4,6,0),Cell.new(4,7,0),Cell.new(4,8,0),Cell.new(4,9,0) ,Cell.new(),Cell.new()],
        [Cell.new(),Cell.new(),Cell.new(5,2,0),Cell.new(5,3,1),Cell.new(5,4,0),Cell.new(5,5,0),Cell.new(5,6,0),Cell.new(5,7,0),Cell.new(5,8,0),Cell.new(5,9,0) ,Cell.new(),Cell.new()],
        [Cell.new(),Cell.new(),Cell.new(6,2,0),Cell.new(6,3,0),Cell.new(6,4,0),Cell.new(6,5,0),Cell.new(6,6,0),Cell.new(6,7,0),Cell.new(6,8,0),Cell.new(6,9,0) ,Cell.new(),Cell.new()],
        [Cell.new(),Cell.new(),Cell.new(7,2,0),Cell.new(7,3,0),Cell.new(7,4,0),Cell.new(7,5,0),Cell.new(7,6,0),Cell.new(7,7,0),Cell.new(7,8,0),Cell.new(7,9,0) ,Cell.new(),Cell.new()],
        [Cell.new(),Cell.new(),Cell.new(8,2,0),Cell.new(8,3,0),Cell.new(8,4,0),Cell.new(8,5,0),Cell.new(8,6,0),Cell.new(8,7,0),Cell.new(8,8,0),Cell.new(8,9,0) ,Cell.new(),Cell.new()],
        [Cell.new(),Cell.new(),Cell.new(9,2,0),Cell.new(9,3,0),Cell.new(9,4,0),Cell.new(9,5,0),Cell.new(9,6,0),Cell.new(9,7,0),Cell.new(9,8,0),Cell.new(9,9,0),Cell.new(),Cell.new()],
        [Cell.new(),Cell.new(),Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()      ,Cell.new(),Cell.new()],
        [Cell.new(),Cell.new(),Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()     ,Cell.new()      ,Cell.new(),Cell.new()]]

require 'benchmark' puts Benchmark.measure {Board[5][3].try(1)} (1..Rows).each{|r|

 (1..Cols).each{|c| printf("%3s",Board[r][c].value)}
 puts ""}

</lang> Which produces:

>ruby Program.rb
  0.000000   0.000000   0.000000 (  0.000000)

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

Tcl

<lang tcl>package require Tcl 8.6; # For object support, which makes coding simpler

oo::class create KnightsTour {

   variable width height visited

   constructor {{w 8} {h 8}} {

set width $w set height $h set visited {}

   method ValidMoves {square} {

lassign $square c r set moves {} foreach {dx dy} {-1 -2 -2 -1 -2 1 -1 2 1 2 2 1 2 -1 1 -2} { set col [expr {($c % $width) + $dx}] set row [expr {($r % $height) + $dy}] if {$row >= 0 && $row < $height && $col >=0 && $col < $width} { lappend moves [list $col $row] } } return $moves

   method CheckSquare {square} {

set moves 0 foreach site [my ValidMoves $square] { if {$site ni $visited} { incr moves } } return $moves

   method Next {square} {

set minimum 9 set nextSquare {-1 -1} foreach site [my ValidMoves $square] { if {$site ni $visited} { set count [my CheckSquare $site] if {$count < $minimum} { set minimum $count set nextSquare $site } elseif {$count == $minimum} { set nextSquare [my Edgemost $nextSquare $site] } } } return $nextSquare

   method Edgemost {a b} {

lassign $a ca ra lassign $b cb rb # Calculate distances to edge set da [expr {min($ca, $width - 1 - $ca, $ra, $height - 1 - $ra)}] set db [expr {min($cb, $width - 1 - $cb, $rb, $height - 1 - $rb)}] if {$da < $db} {return $a} else {return $b}

   method FormatSquare {square} {

lassign $square c r format %c%d [expr {97 + $c}] [expr {1 + $r}]

   method constructFrom {initial} {

while 1 { set visited [list $initial] set square $initial while 1 { set square [my Next $square] if {$square eq {-1 -1}} { break } lappend visited $square } if {[llength $visited] == $height*$width} { return } puts stderr "rejecting path of length [llength $visited]..." }

   method constructRandom {} {

my constructFrom [list \ [expr {int(rand()*$width)}] [expr {int(rand()*$height)}]]

   method print {} {

set s " " foreach square $visited { puts -nonewline "$s[my FormatSquare $square]" if {[incr i]%12} { set s " -> " } else { set s "\n -> " } } puts ""

   method isClosed {} {

set a [lindex $visited 0] set b [lindex $visited end] expr {$a in [my ValidMoves $b]}

}</lang> Demonstrating: <lang tcl>set kt [KnightsTour new] $kt constructRandom $kt print if {[$kt isClosed]} {

   puts "This is a closed tour"

} else {

   puts "This is an open tour"

}</lang> Sample output:

      e6 -> f8 -> h7 -> g5 -> h3 -> g1 -> e2 -> c1 -> a2 -> b4 -> a6 -> b8
   -> d7 -> b6 -> a8 -> c7 -> e8 -> g7 -> h5 -> g3 -> h1 -> f2 -> d1 -> b2
   -> a4 -> c3 -> b1 -> a3 -> b5 -> a7 -> c8 -> e7 -> g8 -> h6 -> f7 -> h8
   -> g6 -> h4 -> g2 -> f4 -> d5 -> f6 -> g4 -> h2 -> f1 -> e3 -> f5 -> d6
   -> e4 -> d2 -> c4 -> a5 -> b7 -> d8 -> c6 -> e5 -> f3 -> e1 -> d3 -> c5
   -> b3 -> a1 -> c2 -> d4
This is a closed tour

The above code supports other sizes of boards and starting from nominated locations: <lang tcl>set kt [KnightsTour new 7 7] $kt constructFrom {0 0} $kt print if {[$kt isClosed]} {

   puts "This is a closed tour"

} else {

   puts "This is an open tour"

}</lang> Which could produce this output:

      a1 -> c2 -> e1 -> g2 -> f4 -> g6 -> e7 -> f5 -> g7 -> e6 -> g5 -> f7
   -> d6 -> b7 -> a5 -> b3 -> c1 -> a2 -> b4 -> a6 -> c7 -> b5 -> a7 -> c6
   -> d4 -> e2 -> g1 -> f3 -> d2 -> f1 -> g3 -> e4 -> f2 -> g4 -> f6 -> d7
   -> e5 -> d3 -> c5 -> a4 -> b2 -> d1 -> e3 -> d5 -> b6 -> c4 -> a3 -> b1
   -> c3
This is an open tour