Back to Non-Intersecting Page.
This page was begun on 30 March 2015.
This page is to record solutions to the problem of constructing closed knight's paths of maximum length without self-intersection and showing quaternary symmetry on square boards of all sizes. Much work on this subject has been in progress recently, beginning in March 2015, in email correspondence between George Jelliss and Bernard Lemaire, but contributions from anyone are invited. The tours with binary symmetry have now (16 April 2015) been moved to a separate page.
All the tours here apart from three on the small boards of sides 4, 5 and 6, show 90 degree rotational symmetry, which leads to patterns that we find fascinating and often amusing. It should be noted that a path in this form of symmetry consists of four congruent parts related by 90 degree rotation. If we imagine the boards to be chequered then on an odd sided board a 90 degree rotation carries a cell to one of the same colour, while on an even sided board the cells are of opposite colour. A knight changes the colour of cell on which it stands with every move. So a knight path between cells of opposite colour is an odd number of moves, and a knight path between cells of the same colour takes an even number of moves. So the path length on an odd-sided board is 4 times an even number, and on an even-sided board is 4 times an odd number. To improve a solution therefore it is necessary to insert an extra two moves in each quarter, increasing the total length by 8.
The percentage fraction given is the "efficiency" = number of moves used in tour/number of cells in board = L/n². In the case of a closed tour the number of moves is the same as the number of cells used.
The quarter-lengths for the smaller boards of side 2m follow the formula (m−2)(m−1)+1 = m² − 3m + 3, which is exact for m = 2, 3, 4, 5, but thereafter these values are above the best achieved lengths. The ratio (m² − 3m + 3)/m² = 1 −3(m−1)/m² tends to 1 as m increases, which suggests the efficiency can approach 100% as the board size increases.
I have now (23 April) worked out that the method devised for the 32×32 board, which will work on any board of side 8n except n = 1, generates a quarter-tour of length 16n² − 18n + 9, which gives the series 7, 37, 99, 193, 319, 477, 667, 889, 1143, 1429, 1747, ... This happens to give the correct total for the case n = 1, although the method doesn't work on the 8×8 board. The first differences of the above series are: 30, 62, 94, 126, 158, ... an arithmetic progression with common difference 32, (it is by working backwards from this that I derived the above formula).
Using the formula it is possible to calculate e = 1 − (9/16)(2n − 1)/(n²), which tends to 1 as n increases, agreeing with the previous argument. This is despite the fact that the increase in areas of close-packed lines is accompanied by an increase in uncovered cells round the edges of these areas. If I have calculated correctly this goes over 90% when n = 11, that is on board size 88×88, where e = 1747/(44×44) = 0.902376.
The problem for the smallest boards, but without the symmetry requirement, was investigated by L. D. Yarbrough in Journal of Recreational Mathematics 1968 (vol.1, nr.3, pp.140-142). The following solutions to the problem were given there. There is no solution on the 3×3 board.
4×4 4×1 = 4-move tour (25%). The first tour has oblique quaternary symmetry and the second direct quaternary symmetry (to use the Bergholt/Murray nomenclature).
5×5 4×2 = 8-move tour (32%). Strictly speaking this tour is not quaternary but octonary; a purely oblique quaternary tour is impossible.
6×6 4×3 = 12-move tours (33.3%). The symmetry of the last tour here is direct quaternary.
7×7 4×6 = 24-move tour (48.9%) by L. D. Yarbrough. This tetraskelion design is the only solution on this board.
8×8 4×7 = 28-move tour (43.7%). Found by George Jelliss (24 March 2015). (Can this 8×8 tour really be original? I've not seen it published anywhere before.)
9×9 4×10 = 40-move tours (49.3%) by Bernard Lemaire (26 and 31 March 2015).
10×10 4×13 = 52-move tour (52%) by George Jelliss (25 March 2015).
11×11 4×16 = 64-move tour (52.8%) by George Jelliss (27 March 2015).
12×12 4×19 = 76-move tours (52.7%) by George Jelliss (3) (26 March 2015) and Bernard Lemaire (2) (29 March and 4 April 2015). The first three were originally published in my Jeepyjay Diary.
Could an 84-move solution still be possible?
13×13 4×24 = 96-move tours (56.8%) by Bernard Lemaire (27 March and 10 April 2015).
14×14 4×27 = 108-move tours (55.1%) by George Jelliss (2) and Bernard Lemaire (1) (28 March 2015) plus a further 9 by GJ (4 April 2015) and another 1 by BL (14 April 2015).
It still looks as if a 116 solution might be possible? 112 has been reached in binary symmetry.
15×15 4×32 = 128-move tours (56.8%) by Bernard Lemaire (28 March and 15 April 2015).
16×16 4×41 = 164-move tour (64%) by George Jelliss (18 March 2015). It was this tour, and an accompanying binary tour of the same length, that set off the current research.
17×17 4×46 = 184-move tour (63.6%) by George Jelliss (22 April 2015) adds 8 to previous best.
18×18 4×55 = 220-move tour (67.9%) by George Jelliss (19 April 2015) previous was 204 moves.
19×19 4×60 = 240-move tour (66.4%) by Bernard Lemaire (30 March 2015).
20×20 4×71 = 284-move tour (71%) by George Jelliss (9 April 2015).
21×21 4×74 = 296-move tour (67.1%) by Bernard Lemaire (14 April 2015) adding 8 moves to the previous best.
Two further examples by George Jelliss (28 and 29 April 2015) are shown. Is a quarter-tour of 76 moves possible?
22×22 4×85 = 340-move tour (70.2%) by George Jelliss (20 April 2015) this adds 8 moves to the previous best.
23×23 4×94 = 376-move tour (71%) by Bernard Lemaire (12 April 2015).
This is an improved version (previous length was 344)
24×24 4×103 = 412-move tour (71.5%) by Bernard Lemaire (16 April 2015).
This is a considerably improved record (+16). See the 32×32 case for the previous diagram.
25×25 4×112 = 448-move tour (71.68%) by Bernard Lemaire (7 April 2015). The figure of 452 previously given was an error.
26×26 4×125 = 500-move tour (73.9%) by George Jelliss (7 April 2015).
The pattern in this can be varied by folding in or out the acute-angled Vs in the diagonal g3 to n10.
I also have an alternative version with a different route in the k8-m12-q10-o6 area.
27×27 4×130 = 520-move tour (71.3%) by Bernard Lemaire (16 April 2015).
28×28 4×145 = 580-move tour (73.9%) by George Jelliss (25 March 2015).
29×29 4×158 = 632-move tour (75.1%) by Bernard Lemaire (14 April 2015).
30×30 4×169 = 676-move tour (75.1%) by Bernard Lemaire (17 April 2015) an increase of 32 on the previous length!
31×31 4×180 = 720-move tour (74.9%) by Bernard Lemaire (20 April 2015).
32×32 4×193 = 772-move tour (75.3%) by George Jelliss (12 April 2015).
The pattern can be varied by folding in or out some of the acute-angle Vs in the main diagonals (i.e. d4-p16 etc).
This systematic pattern can be used on boards of side 16, 24, 32, 40, ... using Robin Merson's "VW extension" method.
In fact I found the 32×32 solution first and then noticed it could be reduced or expanded in this way.
On the 16×16 board it gives 4×37 = 148 moves (57.8%). And on the 24×24 gives 4×99 = 396 moves (68.7%)
but these are less than the best achieved, so the 32×32 case can also probably be bettered.
On the 40×40 board this pattern is of length 4 × 319 = 1276 moves (79.75%). Here is the 24×24 version for comparison:
>
Bernard Lemaire reports tours on 33×33 of 832 moves (76.4%), 34×34 of 900 moves (77.9%) and on 35×35 of 968 moves (79.0%).
The table gives the maximum number of moves achieved for each board size under the quaternary symmetry condition.
L = number of moves in tour (same as number of cells used in the case of closed tours).
e = L/n² the "efficiency" of the solution.
| side | L | e | side | L | e | side | L | e |
| 3 | 0 | 0 | 13 | 96 | 0.5680 | 23 | 376 | 0.7108 |
| 4 | 4 | 0.25 | 14 | 108 | 0.5510 | 24 | 412 | 0.7153 |
| 5 | 0^ | 0 | 15 | 128 | 0.5689 | 25 | 448 | 0.7168 |
| 6 | 12 | 0.3333 | 16 | 164 | 0.6406 | 26 | 500 | 0.7396 |
| 7 | 24 | 0.4898 | 17 | 184 | 0.6367 | 27 | 520 | 0.7133 |
| 8 | 28 | 0.4375 | 18 | 220 | 0.6790 | 28 | 580 | 0.7398 |
| 9 | 40 | 0.4938 | 19 | 240 | 0.6648 | 29 | 632 | 0.7515 |
| 10 | 52 | 0.52 | 20 | 284 | 0.71 | 30 | 676 | 0.7511 |
| 11 | 64 | 0.5289 | 21 | 296 | 0.6712 | 31 | 720 | 0.7492 |
| 12 | 76 | 0.5278 | 22 | 340 | 0.7025 | 32 | 772 | 0.7539 |