Knight's tour: Difference between revisions

Content added Content deleted

Inline

Revision as of 13:05, 30 May 2011

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>

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

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);
   }

   random_shuffle(counts.begin(), counts.end()); // Shuffle to randomly break ties
   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 x = start[0] - 'a';
   int y = N - (start[1] - '0');
   data[y][x] = 1;
   sx = x;
   sy = y;

   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<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;
 Board<8> b2;
 Board<31> b3; // Max size for <1000 squares

 b1.solve("c3");
 cout << b1 << endl;

 b2.solve("b5");
 cout << b2 << endl;

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

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

Perl

Knight's tour using Warnsdorffs algorithm <lang perl># Find a knight's tour

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

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

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])$/;
  $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