This diagram was the cover illustration, 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.
Further results by Robin on square boards up to side 31 are tabulated, with some further examples and theory. You are challenged to try to improve on his results.
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.
A wazir, {0, 1}-mover, can never cross its own path, so the problem reduces to that of finding the longest path. On a rectangular board m×n the wazir can tour all the cells.
The case of the knight {1, 2} on the 8×8 board was solved in 1930, with an open path of 35 moves by T. R. Dawson and with a closed path of 32 moves by the Romanian chess problemist Wolfgang Pauly (1876-1934) [not to be confused with the Austro-Swiss physicist Wolfgang Pauli (1900-1958)]. These results were reported in L'Echiquier, December 1930, though without a diagram of Pauly's result; a diagram appears in H. J. R. Murray's unpublished 1942 knight's tour manuscript.
The knight problem for small rectangular boards was rediscovered by L. D. Yarbrough in Journal of Recreational Mathematics 1968 (vol.1, nr.3, pp.140-142). 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 (7×8 and 5×9 to 9×9), D. E. Knuth (5×6, 6×6, 7×8, 8×8, confirming the Dawson/Pauly results, 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.
A note on terminology: The Journal of Recreational Mathematics does not distinguish between 'reentrant' and 'closed'; we use 'reentrant' to describe an open path whose ends are a knight move apart; joining up the ends gives a closed path but causes at least one intersection.
Diagrams of a few interesting small-board tours follow. The 17-move 6×6 path was found by Knuth and Matsuda independently and is unique, apart from rotation or reflection, and is reentrant. 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 and closed solutions are symmetrical. The 7×8 open solution is also unique. [Due to popular demand I now also add here the 9×9 solution in 47 moves by Matsuda.]
8×8 board.
9×9 board (On this the giraffe can do no better in a closed tour than it does on the 8×8).
10×10 board.
Robin also gave solutions for antelope on 11×11, on which the unique closed path takes the form of a tetraskelion similar to those for the 7×7 knight (1,2) and 9×9 zebra (2,3); an evident progression. These cases were diagrammed in a brief report on his work in Variant Chess, (vol.1, nr.6, 1991).
The following is a table of Robin Merson's results on these longer leapers. The figures in brackets give the number of different tours found; thus (1) indicates a unique solution.
| 8×8 | 9×9 | 10×10 | 11×11 | |||||
| open | closed | open | closed | open | closed | open | closed | |
| camel | 17 (1) | 14 (5) | 23 (14) | 20 (20+) | 29 (1) | 26 (1) | ||
| zebra | 17 (3) | 12 (12) | 25 (1) | 24 (1) | 32 (9) | 28 (7) | ||
| giraffe | 15 (2) | 12 (1) | 19 (1) | 12 (1) | 25 (11) | 20 (2) | ||
| antelope | 9 (5) | 4 (2) | 13 (4) | 8 (3) | 17 (15) | 12 (7) | 25 (4) | 24 (1) |
camel = {1,3}, zebra = {2,3}, giraffe = {1,4}, antelope = {3,4}
T. R. Dawson Fairy Chess Review August 1944 (problem 6038) gave an 8×8 open tour of 52 moves for the gnu (knight + camel), i.e. {1,2} and {1,3} leaper.
Robin Merson reported that he first became interested in this problem through some items that appeared in Games & Puzzles in 1972-3, where he published a letter (issue 9) outlining some results. His later work, reported below, was sent to George Jelliss (results for open paths dated 9 November 1990 and closed paths 23 April 1991).
The table gives the maximum sizes, in number of moves, achieved for open and closed non-intersecting paths on square boards of various sizes. His 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. [George Jelliss (22 July 2003) has extended Merson's 237 moves on 18×18 to 238.]
| side | open | closed | side | open | closed | side | open | closed |
| 3 | 2 | 0 | 13 | 113 | 104 | 23 | 414 | 396 |
| 4 | 5 | 4 | 14 | 134 | 124 | 24 | 453 | 434 |
| 5 | 10 | 8 | 15 | 158 | 148 | 25 | 498 | 476 |
| 6 | 17 | 12 | 16 | 181 | 172 | 26 | 541 | 520 |
| 7 | 24 | 24 | 17 | 210 | 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 | 742 | 714 |
| 11 | 76 | 70 | 21 | 337 | 322 | 31 | 768 | |
| 12 | 94 | 86 | 22 | 374 | 360 | 32 |
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.]
The following diagrams are some example open tours by Robin Merson, including an illustration of his VW extension method, and the new 18×18 result by Jelliss. 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. The paths of side 15 and 23 are the only symmetric solutions that he produced.
10×10, open, 61 moves and closed 54 moves.
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.
13×13, open, 113 moves.
15×15. open, 158 moves, symmetric.
18×18, closed, 222 moves (226 can be reached), 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 tour can in turn be extended to a 26×26 of 518 moves, but 520 is possible. [The new 238-move open tour by George Jelliss 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, formed by VW extension of 11×11.
23×23, open, 414 moves, symmetric, by VW extension from 15×15 example.
The case of a 16×16 tour of 181 moves extended to a 24×24 tour of 453 moves, is shown in the Introduction above. Robin Merson conjectured, from the table, that a 183 path 16×16 ought to be possible but was not able to find one. The 24-size was the largest open tour that he 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.
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).]