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.
C++
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
9!:37]0 64 4 4 NB. truncate lines longer than 64 characters and only show first and last four lines
ktourw 31 NB. solution for a 31 x 31 board 0 69 956 121 72 67 74 105 78 65 76 85 102 63 90 87 ...
953 122 71 68 955 120 79 66 75 104 107 64 89 86 113 62 ...
70 1 954 957 930 73 908 119 106 77 84 103 116 101 88 95 ...
123 952 929 932 911 960 945 80 909 118 903 108 83 112 851 114 ... ... 135 474 507 444 401 472 439 418 399 420 407 396 273 280 289 262 ...
14 443 138 473 440 403 400 285 406 397 272 281 288 261 240 269 ...
139 136 441 16 141 284 405 18 143 282 287 20 145 270 259 22 ... 442 15 140 137 404 17 142 283 286 19 144 271 260 21 146 239 ...
ktourw 88x NB. 88x88 is the largest that this implementation can handle 0 7711 174 7743 7708 7713 172 7703 7700 7693 170 7691 7680... 175 7736 7709 7712 173 7740 7707 7714 171 7702 7699 7694 169...
7710 1 7728 7739 7742 7719 7724 7701 7704 7697 7692 7673 7690... 7735 176 7737 7720 7731 7722 7741 7706 7715 7672 7695 7698 7669... ...
42 353 358 373 366 349 392 383 376 345 420 409 402... 217 356 219 352 361 372 367 348 369 382 377 344 379... 220 43 354 359 222 45 350 371 224 47 346 381 226... 355 218 221 44 351 360 223 46 347 370 225 48 343...</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 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.