A Tour of the Knight's Tour

The knight is a forking monster.  (Be careful who is standing nearby if you say this out loud.)  To master this particular ability of the knight you must thoroughly understand the knight’s manner of movement.  There are various exercises to develop this understanding, but probably the most interesting is the Knight’s Tour, whereby the knight, beginning at any arbitrary square, visits each square on the board only once while making 63 successive legal moves.  If, on its 64th move, it could return to its starting square, then we refer to the tour as re-entrant or closed. 

Knight tours have been known for centuries.  Chess historian H.J.R. Murray cites perhaps the earliest known such tour constructed by one al-Adli ar-Rumi who lived around 840 A.D.

There are two common methods of indicating knight tours, geometric and numeric.  The geometric method draws a line connecting each successive square that is visited by the knight, and can result in quite beautiful graphs.

The numeric method puts a ‘1’ at the knight’s starting position, and then labels the knight’s next square (the first move) with a ‘2’ and so forth until its final position is represented by the label ‘64’.  Notice that a re-entrant knight tour will result in a numeric grid where the numbers ‘1’ and ‘64’ are exactly one knight move removed from each other.   Of course, both methods can be combined with numbered squares that are connected by lines.

The tour depicted here is of particular interest since it forms a ‘semi-magic’ square.  A magic square is an n-by-n numbered matrix where the sum of all rows, columns and the two main diagonals is the same.  A knight tour cannot create a full magic square, but in the tour at the right the sum of each rank and each file is 260, with the sum of the primary diagonals being 192 and 328.

According to AT&T Research, there are 13,267,364,410,532 knight tours on a chessboard.  If you think it must be rather easy to find one of them since there are so many, you can try your luck by clicking here or here.  Sadly, while the tours are indeed numerous, they are rather like finding an equivalent number of marbles evenly distributed throughout earth’s total volume, where you would find one marble in roughly 100,000,000 cubic meters.  When the search space is large enough, any finite number becomes vanishingly small. 

Fortunately, there is a rather simple heuristic first published by Warnsdorff in 1823 that guides you to the simple creation of a knight’s tour. 

Warnsdorff’s Rule:  Move the knight to the successor square that itself has the least number of successor squares, where a successor square is defined as any unvisited square to which the knight can next move.

For example, consider the square in the preceding image labeled with '11' -- the b8 square.  It has only two successor squares (since we already visited a6), namely d7 and c6.  If we moved to potential successor d7, there would be 4 successor squares to consider next, and if we moved to potential successor c6 there would be 5 successor squares.  Hence, we choose the one with the fewest number of successors and move to square d7.  In the event of a tie for next successors, you can choose any such candidate.

Grandmaster Georges Koltanowski, who I have written about before for his world record in simultaneous blindfold games, also gave demonstrations of his additional prowess in quickly demonstrating re-entrant knight tours from any square of the board.  In one amazing demonstration of his genius, Koltanowski had audience members call out random names, numbers, words or phrases which were written down on sticky notes and placed, one per square, on each of the 64 squares of a demonstration board.  He was then blindfolded, and had someone randomly pick one of the squares 64 squares.  Starting with that square, he recited the name, number, word or phrase that was written on that sticky note, which was then removed.  Next, he recited a new entry, and its sticky note was removed.  He continued until all 64 stickies had been removed.  The sequence of squares from which he had correctly recited the texts and numbers formed a knight’s tour. 

There is no more amazing force than the human intellect.