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.


Created April 23, 2010. Last updated May 12, 2011.