Knight's tour: Difference between revisions

Content added Content deleted

Inline

Revision as of 12:46, 12 January 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 knight should end within a knight's move of its start position, (this would have then been a closed tour).

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

Bracmat

<lang> ( 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>

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;
       copy(transversal(counts[], 1), 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>

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.

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