|
A cyclic knight's tour is a sequence of knight's moves that
visit every square of an n x n chessboard, returning to
the first square.
These are some images from Ian Parberry's
research on cyclic knight's tours in the 1990s. See these papers
for more information. Some of the tours are generated by a random walk,
one is generated by a neural network, some are generated by a divide-and-conquer
algorithm that gives the tours a tiled look. Some are symmetric under rotations.
|
6x6, Random
| The following small knight's tour was used as part of the base of the recursion in a divide-and-conquer algorithm described in Ian Parberry, "An Efficient Algorithm for the Knight's Tour Problem", Discrete Applied Mathematics, Vol. 73, pp. 251-260, 1997. [pdf]. |
8x8, Random
| The following small knight's tour was used as part of the base of the recursion in a divide-and-conquer algorithm described in Ian Parberry, "An Efficient Algorithm for the Knight's Tour Problem", Discrete Applied Mathematics, Vol. 73, pp. 251-260, 1997. [pdf]. |
10x10, Random
| The following small knight's tour was used as part of the base of the recursion in a divide-and-conquer algorithm described in Ian Parberry, "An Efficient Algorithm for the Knight's Tour Problem", Discrete Applied Mathematics, Vol. 73, pp. 251-260, 1997. [pdf]. You may have noticed by now that all of the closed knight's tours you have seen so far (6x6, 8x8, and 10x10) have even sides. That's because there can be no knight's tours on an odd-sided board (to see this, consider the fact that on a real chessboard, the squares visited in a knight's tour must alternate between black and white). |
10x10, Invariant Under 90° Rotation
| Closed knight's that are invariant under a 90° rotation exist on nxn boards for all even n at least 6 that is not divisible by 4 (Dejter, 1983). This tour is from Ian Parberry, "An Efficient Algorithm for the Knight's Tour Problem", Discrete Applied Mathematics, Vol. 73, pp. 251-260, 1997. [pdf]. |
12x12, Invariant Under 180° Rotation
| Closed knight's that are invariant under a 180° rotation exist on nxn boards for all even n at least 10. This tour is from Ian Parberry, "An Efficient Algorithm for the Knight's Tour Problem", Discrete Applied Mathematics, Vol. 73, pp. 251-260, 1997. [pdf], as are the following 14x14, 16x16, 18x18, and 20x20 knight's tours. |
14x14, Invariant Under 90° Rotation
16x16
18x18, Invariant Under 90° Rotation
20x20, Invariant Under 180° Rotation
26x26, Found by a Neural Network
| The following was the largest closed knight's tour I could generate at the time using the Hopfield network of Takefuji and Lee. More details appear in Ian Parberry, "Scalability of a Neural Network for the Knight's Tour Problem", Neurocomputing, Vol. 12, pp. 19-34, 1996. [pdf] |
30x30
| The following was generated by a divide-and-conquer algorithm described in "An Efficient Algorithm for the Knight's Tour Problem", Discrete Applied Mathematics, Vol. 73, pp. 251-260, 1997. [pdf]. |
60x60
| The following was generated by a divide-and-conquer algorithm described in "An Efficient Algorithm for the Knight's Tour Problem", Discrete Applied Mathematics, Vol. 73, pp. 251-260, 1997. [pdf]. |
60x60, Random Walk with Warnsdorf's Heuristic
| The following was generated by a random walk algorithm due to Euler in 1795 modifed with a heuristic due to Warnsdorf in 1823. It appears in Ian Parberry, "Scalability of a Neural Network for the Knight's Tour Problem", Neurocomputing, Vol. 12, pp. 19-34, 1996. [pdf] |
80x80, Random Walk with Warnsdorf's Heuristic
| The following tours were generated using the same random walk algorithm as was used in the 1990s to generate the preceding 60x60 knight's tour, but were created in 2010 on a much faster computer than was available back then. |
100x100
120x120
|
The following knight's
tour is on a 120x120 chessboard, which has 14,400 squares. Therefore it would take
a knight 14,400 moves to complete the circuit,
which would take 4 hours to perform in the real world
at one move per second with a real chess piece,
assuming you don't make any mistakes. Oh, and if each square is 1 inch by 1 inch, the board
would be 10 feet on a side.
|
40x40
|
This is a 40x40 chessboard with the letter "I" (for "Ian") cut out of it.
|
40x40
|
"Ian" spelled out with 40x40 knight's tours.
|
Also available, more images of knight's tours found using PerS3phone, a cluster of game consoles.