Knight's tour

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.

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

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<size_t N = 8> class Board { public:

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

   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) {
       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());
       sort(counts.begin(), counts.end()); // Lexicographic sort

       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;
       sx = x0;
       sy = y0;

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

       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) {
                   get<2>(order[n]) = i + 1;
                   ++n;
                   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<size_t 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

Icon and Unicon

This implements Warnsdorff's algorithm using unordered sets. Tie breaking amongst least accessible squares is random.

The algorithm doesn't always generate a complete tour. Before implementing corrective measures such as backtracking, further investigation is in order. Published research suggests the order the Knights moves are presented for tie breaking may be significant and better results may be obtainable using ordered sets or other heuristics. <lang Icon>procedure main(A) B := KnightsTour(8) # Try a tour (\DumpBoard)(B) # for debug, ignored if omitted end

procedure KnightsTour(N) #: Warnsdorff’s algorithm moves := [] visited := set()

B := Board(N) # create board

sq := ?B.cols || ?B.rows # initial random position repeat {

  put(moves,sq)                   # record move
  insert(visited,sq)              # mark visited
  choices := B.movesto[sq] -- visited
  sq := ?(choices ** \!B.accessibility) | break # least accessible
  }

ShowTour(B,moves) return moves end

procedure Board(N) #: create board N := *&lcase >=( 0 < integer(N)) | stop("N=",image(N)," is out of range.") B := board(N,table(),list(8),[],&lcase[1+:N]) # 8 = max # accessible moves every put(B.rows,N to 1 by -1) every sq := !B.cols || !B.rows do {

  every insert(B.movesto[sq] := set(), KnightMoves(sq,B)) # moves from sq
  /B.accessibility[*B.movesto[sq]] := set()               # accessibility
  insert(B.accessibility[*B.movesto[sq]],sq)              # add sq to this set
  }

return B end

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

  if (abs(i)~=abs(j)) & (0<(ri:=cr[2]+i)<=B.N) & (0<(cj:=cr[1]+j)<=B.N) then
     suspend B.cols[cj]||B.rows[ri]

end

procedure sq2cr(sq,B) #: return col & row from algebraic c := find(sq[1],B.cols) | runerr(205,sq) r := integer(B.rows[sq[2:0]]) | runerr(205,sq) return [c,r] end

procedure ShowTour(B,moves) #: show the results write("Board size = ",B.N) write("Tour length = ",*moves)

every !(squares := list(B.N)) := list(B.N,"-") every cr := sq2cr(moves[m := 1 to *moves],B) do

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

every (hdr1 := " ") ||:= right(!B.cols,3) every (hdr2 := " +") ||:= repl((1 to B.N,"-"),3) | "-+" every write(hdr1|hdr2) every r := 1 to B.N do {

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

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

<lang Icon>procedure DumpBoard(B) #: dump the board structure for analysis write("Board size=",B.N) every put(K := [],key(B.movesto)) write("Moves to :") every writes(k := !sort(K)," : ") do {

  every writes(!sort(B.movesto[k])," ")
  write()
  }

write("Accessibility :") every A := B.accessibility[a := 1 to 8] do

  if \A then {
     writes(a," : ")
     every writes(!A," ")
     write()
     }

end</lang>

Output:

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

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># Find a knight's tour

1. The map ensures that each row gets its own array,
2. rather than all being references to a single one.

my @board = map { [ @{[ @$_ ]} ] } ( [ (0) x 8 ] ) x 8;

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])$/;
  $j = ord($1) - ord('a'); $i = 8 - $2; 
  return ($i, $j);

}</lang>

Sample output (start square c3):

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.