Knight's tour: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎Tcl: Added implementation)
m (→‎{{header|Tcl}}: Show setting the board size and starting location)
Line 938: Line 938:
-> b3 -> a1 -> c2 -> d4
-> b3 -> a1 -> c2 -> d4
This is a closed tour
This is a closed tour
</pre>
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:
<pre>
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
</pre>
</pre>

Revision as of 13:20, 3 June 2011

Task
Knight's tour
You are encouraged to solve this task according to the task description, using any language you may know.

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. The tour does not need to be closed.

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.

C++

Works with: C++0x

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

<lang cpp>#include <iostream>

  1. include <iomanip>
  2. include <array>
  3. include <string>
  4. include <tuple>
  5. 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;

}</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

D

Translation of: C++

<lang d>import std.stdio, std.typecons, std.random, std.typetuple, 

      std.string, std.range, std.algorithm, std.conv;

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

   alias Tuple!(int, "x", int, "y") P;
   const 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) {
               const 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
       }

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

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

   assert(start.length >= 2);
   /*const*/ P 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) {
       const int x = order[n][0];
       const int y = order[n][1];
       bool ok = false;
       foreach (i; order[n][2] .. 8) {
           /*const*/ 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)) {
       const form = "%" ~ format(format(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]

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>

Perl

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

  1. Find a knight's tour

my @board;

  1. Choose starting position - may be passed in on command line; if
  2. 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);

}

  1. 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];

}

  1. 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";

  1. 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";

}

  1. 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]);

}

  1. Return the algebraic name of the square identified by the coordinates
  2. 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);

}

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

PicoLisp

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

  1. Build board

(grid 8 8)

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

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

   knightmoves(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.

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
Retrieved from "https://rosettacode.org/wiki/Knight%27s_tour?oldid=183327"