By G. P. Jelliss
This page revised 22 July 2003, 13 March 2011, 3 August 2011, 18, 25, 30 March 2015, 16 April 2015.
This subject has now been spread over three further pages:
Non-Intersecting Knight Tours with Simple Symmetry
Non-Intersecting Knight Tours with Higher Symmetry
Non-Intersecting Tours by Other Pieces
Other web-pages showing significant numbers of results on this recreation are these:
Alex Chernov (tables of results including rectangles and other leapers).
Eric Bainville (diagrams of all solutions 3×3 to 9×9)
Jean-Charles Meyrignac (tables of results including rectangles up to 16×16).
A simple question, or group of questions, that leads to some interesting convoluted patterns and is difficult to answer with certainty is: What is the longest journey a given piece can make on a given board without entering any cell twice or crossing its own path?
Although it may not visit all cells of the board, such a path is often called a ‘tour’ since it never passes through a cell twice and it covers the maximum area possible under the conditions. The length L of a path is counted by the number of moves and its coverage C by the area of the board used, measured by the number of cells visited. In a closed tour C = L, but in an open tour C = L + 1.
The history and results of the problem for other pieces than the knight are now on a separate page.
The problem for the case of the knight on the normal 8×8 chessboard was proposed by Thomas Rayner Dawson (1889- 1951) in his puzzle column "Echecs Feeriques" in the Belgian magazine L'Echiquier (December 1930, problem 186, p.1085) where he asks for open tours in 35 and closed in 32 moves, giving an example in 30 moves to show the idea. The three solutions, diagrammed below, are given in the January 1931 issue p.1150 in algebraic coordinate form. The closed tour of 32 moves is by the Romanian chess problemist Wolfgang Pauly (1876-1934) [not to be confused with the Austro-Swiss physicist Wolfgang Pauli (1900-1958)].
The problem was rediscovered by L. D. Yarbrough in Journal of Recreational Mathematics 1968 (vol.1, nr.3, pp.140-142), who considered knight paths on all small rectangular boards up to 9×9. Some of his results were improved on in letters in the same journal 1969 (vol.2, nr.3, pp.154-157) by R. E. Ruemmler, D. E. Knuth and M. Matsuda. The Dawson/Pauly results were confirmed as being the best possible.
Robin Merson reported that he first became interested in this problem through some items that appeared in the magazine Games & Puzzles in 1972-3, where he published a letter (issue 9) outlining some results. His results reported here were first published in the Games and Puzzles Journal issue 17 (1999), which was based mainly on work that he sent to me in 1990-91. It was only in 2002 that I learnt that Robin had died in August 1992. Not all of his results are reproduced below, so I include here PDF copies of the letters and accompanying diagrams that he sent to me (a) 9 November 1990 on open paths and (b) 23 April 1991 on closed paths. Where red ink is referred to this is mostly the first figure cited.
Contributions from other authors are acknowledged where appropriate.
L. D. Yarbrough (1968) gave results for all rectangular boards up to 9×9.
Other correspondents in the same journal (1969) improved on these results:
R. E. Ruemmler (7×8 and 5×9 to 9×9),
D. E. Knuth (5×6, 6×6, 7×8, 8×8, and 5×9) and
M. Matsuda (6×6, 6×8, 5×9, 7×9 and 9×9).
The best results of these authors, up to 9×9, by number of moves, are:
3×3 = 2; 3×4 = 4; 3×5 = 5; 3×6 = 6 closed; 3×7 = 8; 3×8 = 9; 3×9 = 10.
4×4 = 5; 4×5 = 7; 4×6 = 9 open, 8 closed; 4×7 = 11; 4×8 = 13 open, 12 closed; 4×9 = 15.
5×5 = 10 open, 8 closed; 5×6 = 14; 5×7 = 16; 5×8 = 19 open, 18 closed; 5×9 = 22 open, 20 closed.
6×6 = 17 open or reentrant; 6×7 = 21; 6×8 = 25 open, 22 closed; 6×9 = 29.
7×7 = 24 open, 24 closed; 7×8 = 30 open, 29 open symmetric, 26 closed; 7×9 = 35.
8×8 = 35 open or reentrant, 32 closed; 8×9 = 42.
9×9 = 47.
Diagrams of a few interesting small-board tours follow.
The 17-move 6×6 open path was found by Knuth and Matsuda (1969) independently and is unique, apart from rotation or reflection. It has been quoted many times, e.g. in Martin Gardner's Scientific American column (April 1969) and his Mathematical Circus and in K. Fabel et al, Schach und Zahl (1978), without due acknowledgement.
The 7×7 open solution open by Knuth (1969) is symmetric by 180° rotation, and the closed solution by Yarbrough (1969) is symmetric by 90°rotation. Separate pages have now been opened for tours of these types.
The 7×8 open solution of 30 moves by Knuth and Ruemmler (1969) independently is also unique. For other tours on oblong boards see the websites mentioned above. Here we cover only square boards. This is particularly mentioned here because it includes a corner formation that is common on larger boards.
Here are diagrams of the Dawson and Pauly results on the 8×8 board mentioned in the introduction. The Bainville site notes variant solutions. I have redrawn these tours so that they are individually diagrammed, and in the orientation as originaly published.
Here is the 9×9 solution in 47 moves by Matsuda (1969).
The following diagrams are some example open tours by Robin Merson, including an illustration of his VW extension method (explained in the Analysis section below) and new results by Jelliss, Fischer, Chernov and Lemaire.
10×10, open, 61 moves and closed 54 moves (Merson 1990/91).
Tours 18×18 can be formed by VW extension of these 10×10 tours but the one derived from the open tour covers only 237 cells and 238 is possible. The closed tour derived is shown below.
11×11, open, 76 moves (Merson 1990).
13×13, open, 113 moves (Merson 1990);
13×13 closed, 106 moves by Alex Chernov (3 August 2011), previous solution was 104.
The following two results by Alexander Fischer, sent to me in 2006, were first published in the delayed issue Games and Puzzles Journal #45 in April 2010.
14×14, open, 135 moves by Alexander Fischer (11 September 2006), previous solution was 134 moves.
16×16 open 183 moves by Alexander Fischer (6 Sepetember 2006), previous solution was 181 moves,
16×16 closed, 172 moves by Robin Merson (1991).
The case of a 16×16 tour of 181 moves extended to a 24×24 tour of 453 moves, is shown in the 24×24 section below. Robin Merson conjectured, from the table, that a 183 path 16×16 ought to be possible but was not able to find one. This was achieved by Alexander Fischer (2006).
17×17. open, 211 moves (was 210), by Bernard Lemaire (11 March 2015).
18×18, closed, 222 moves by Robin Merson (1990), formed by VW extension of the 10×10 closed example. Note that on two edges the VW-formation is moved in one step to allow the extra connecting path to pass round the outside. This is not the maximum as 226 can be reached. This tour can in turn be extended to a 26×26 of 518 moves, but 520 is possible.
The 238-move open tour by George Jelliss (22 July 2003) is inserted alongside; this differs only in removal of two and addition of three moves in Robin Merson's 237-move solution.
19×19, open, 268 moves by Robin Merson (1990), formed by VW extension of 11×11.
24×24. open 453 moves by Robin Merson (1990).
A version of this diagram was the cover illustration in the Games and Puzzles Journal issue 17 (1999), showing a non-intersecting knight path by Robin Merson, which covers 454 cells on a 24×24 board, leaving 122 cells unused. The heavy lines solve the 16×16 case in 182 cells.
The 24-size was the largest open tour that Robin Merson actually diagrammed in his letters to me. The figure for 26 shown in the table was mentioned as an extension from the 237-move 18×18 solution, and the figures for 25 and 27 to 30 are implied by his graph of ‘excess’ values shown at the end of this article.
25×25, open, 499 moves, by Bernard Lemaire (11 March 2015), by extension from his 17×17 example (was 498).
The table gives the maximum sizes, in number of moves, achieved for open and closed non-intersecting paths on square boards of various sizes. Robin Merson's values for open paths up to 9×9 agree with the work of Yarbrough and Co. Improvements may still be possible on some of the larger boards. [Improvements since first publication are marked in red. Some of these are new results from the Alex Chernov (aka Alex Black) website: 24: 453→455; 26: 541→542; 30: 742→743; 31: 789 by N. Makarova (no previous result noted).
| side | open | closed | side | open | closed | side | open | closed |
| 3 | 2 | 0 | 13 | 113 | 106 | 23 | 414 | 396 |
| 4 | 5 | 4 | 14 | 135 | 124 | 24 | 455 | 434 |
| 5 | 10 | 8 | 15 | 158 | 148 | 25 | 499 | 476 |
| 6 | 17 | 12 | 16 | 183 | 172 | 26 | 542 | 520 |
| 7 | 24 | 24 | 17 | 211 | 200 | 27 | 588 | 564 |
| 8 | 35 | 32 | 18 | 238 | 226 | 28 | 638 | 612 |
| 9 | 47 | 42 | 19 | 268 | 256 | 29 | 689 | 662 |
| 10 | 61 | 54 | 20 | 302 | 288 | 30 | 743 | 714 |
| 11 | 76 | 70 | 21 | 337 | 322 | 31 | 789 | 768 |
| 12 | 94 | 86 | 22 | 374 | 360 | 32 | 772 |
The simplest arrangements of knights moves that cover an area completely are (a) the close-packed parallels (b) lateral zigzags, (c) diagonal zigzags or (d) combinations of these. When we consider the ways of joining up these lines in adjacent pairs, using links that fit closely to the edges and corners, the diagonal zigzags (c) or the lengthened type (d) prove the most economical.
Robin Merson draws particular attention to the following cases to which he gives names. It is possible to interpolate a VW structure in each edge of certain tours n×n to give a tour on an (n + 8)-side square, though this does not always guarantee that the resulting tour is of maximum length.
Robin gives the following instructions for determining the length of a tour without counting all lines: Put (n – 2) black crosses (x) along each edge on unvisited squares [i.e. one in each row or column perpendicular to the edge, except at the ends]. Put a red blob (o) in each remaining unvisited square, and count the number of such blobs, b, which he calls the loss of the tour. Then the length in the case of an open tour is L = n² – 4(n – 2) – b – 1 = n² – 4n + 7 – b. For example in the 11×11 tour shown below n = 11, b = 8, L = 76. [If instead of the length L we count the coverage C, Merson's formula can be put in the form C = (n – 2)² + 4 – b, true for open or closed tours. The estimate C » (n – 2)² + 4 is a slight improvement on the value (m – 2)(n – 2) conjectured by Yarbrough for rectangular boards.] Note that eight voids (x), one for each extra rank or file, plus four extra voids (blobs, o) are introduced by each VW formation, one inserted in each side.
What function remains constant during the VW extensions? The board size increases from n to n' = n + 8. In the n×n tour we have C = n² – 4n + 8 – b. In the open tour case the loss becomes b' = b + 16 (4 extra blobs in each side) while in the closed tour case it becomes b' = b + 24 (4 extra blobs at top and left, 8 extra at right and bottom). Thus in the open case 2n – b remains constant (i.e. 2n' – b' = 2n – b), while in the closed case 3n – b is constant. These numbers can be called the excess (E) of the tour. Writing them as gn – b (g = 2 for open, 3 for closed) we find the formula: E = C – n² + (4 + g)n – 8, where 4 + g equals 6 for open, 7 for closed.
Below are plots of E for the maxima so far found. In the open case for n > 10, C > n² – 6n + 22. The plot suggests that the maximum value of E for open tours is 16, or does it increase further? For closed tours the excess increases to a peak of 22 and then falls off, and Robin said he would be surprised if it is greater than 16 for any n greater than 31. To summarise: for 7 < n < 31 maximum length tours have a length of at least n² – 7n + 24 and for n > 31 have a length of at least n² – 7n + 22.
Plots of excess for closed and open tours.
[The above account is simplified slightly from Merson's original version, in which he defined an 'excess' for a closed tour equivalent to E + 8, and a 'strength' for an open tour equivalent to E + 7 (the difference of 1 resulting from defining it in terms of the length L = C – 1).]
I have not yet attempted to update this graph to take account of recent results.