Sections on this page: — What are we Counting?
— Total Numbers of 8×8 Knight's Tours — Update on Number of Open Tours
— Enumeration of 8×8 Compartmental Tours
— Enumeration of Rogetian Tours
— Appendix [on separate page] Closed Squares and Diamonds Tours with 4 Slants.
The counting of anything requires first of all that we have a clear idea of what it is we are counting. This seems obvious enough, but in the case of knight's tours there is often considerable confusion arising from carelessness on this basic point. My preference is to work with small numbers where possible and accordingly regard a knight's tour as a geometrical object that can be rotated and reflected and be seen in various different orientations. This idea was expressed graphically by H. J. R. Murray (1942) in this way:
|
If we trace a tour in ink on a piece of transparent paper, turn the paper over and ink in the tour as it appears through the paper, and then carefully cut out the diagram, it is impossible for anyone to say with certainty how the tour was oriented from which it was traced. |
On the 8×8 board all G geometrically distinct open tours are asymmetric so the number of open tour diagrams is T = 8G and the number of open tour numberings is N = 2T = 16G since each can be numbered from either end.
For the closed tours on the 8×8 board the situation is more complicated. Let C be the number of geometrically distinct closed tours (these are geometrical paths with no end points). Of these a certain number B are symmetric closed tours having binary symmetry (unchanged by 180 degree rotation). Thus the number of asymmetric closed tours is A = C – B, and since asymmetric tours can be diagrammed in 8 orientations and symmetric tours in 4 orientations, the number of closed tour diagrams is D = 8A + 4B = 8C – 4B.
If we now number these tours we have a choice of 64 cells to start from and 2 directions in which to go along the tour, thus generating E = 128D closed tour numberings. These E numbered tours are included among the N open tour numberings (they are those with 1 and 64 a knight move apart).
We may also want to know the number R of reentrant tours counted geometrically, that is open tours that have their ends a knight's move apart (so R < G). By joining the end-points of a reentrant tour we get a unique closed tour, but by deleting a move from a closed tour we can form either 32 or 64 different reentrant tours, depending on whether the closed tour is symmetric or asymmetric. Thus R = 64A + 32B = 64(C − B) + 32B = 64C − 32B = 8D = E/16.
Caution: on other boards other types and degrees of symmetry are usually possible, so that different formulas apply.
Thus to count the chessboard tours thoroughly, involves determining all the quantities: G, T, N, R, A, B, C, D, E, which can be expressed in terms of the basic quantities G, C, B (open tours, closed tours, and symmetric closed tours). I have expressed the view elsewhere that counting tour diagrams or numbered diagrams is like counting a combined herd of zebras and ostriches by the number of legs!
Euler (1759) merely noted that the number of tours possible was very great. C. F. von Jaenisch (1862, vol.2, p.268) in attempting to quantify the matter argued that there are 168 knight's moves in the complete net of moves on the 8×8 board (42 in each of the 4 directions) and a open knight's tour uses 63 of these, so an upper bound on the number of open tours is the number of ways of choosing 63 objects from a set of 168 which is 168C63 = 168!/(168 − 63)!63! = 168!/105!63!. This is difficult to calculate but according to Dawson (1922) is approximately 1.22×(10^47). Since this count includes un-tourlike patterns such as all moves incident with de3456 (plus 3) it is clearly way over the mark. [How absurdly far over the mark is made clear when one reads in Richard Dawkins The Blind Watchmaker (Penguin Books 1991) that the chance of a monkey typing a short sentence from Shakespeare is estimated as only 1 in 10^40.]
F. Douglas (Chess Amateur1922) found another approach to the problem by considering each cell separately, noting that there are 4 cells (the corners) where 2 moves are available, 8 where there are 3 moves, 20 with 4 moves, 16 with 6 moves and 16 with 8 moves. The number of ways a knight path can pass through a cell where there are n moves is nC2 (and 2C2 = 1, 3C2 = 3, 4C2 = 6, 6C2 = 15, 8C2 = 28). Thus if we choose the moves through the black cells we get (1^2)(3^4)(6^10)(15^8)(28^8) patterns of 64 moves. This formula simplifies to (2^26)(3^22)(5^8)(7^8) which is about 4.74×(10^30). This is better than Jaenisch but still way out, since it includes many arrangements where some white cells are not used and others are multiply joined. H. A. Adamson in the same source made some minor refinements to this count but the total is still in the region of 10^28.
O. T. Blathy (Chess Amateur 1922) was inspired by the above method to try a statistical approach, which I've simplified here. He takes the geometric mean of the number of moves at each cell: namely the 64th root of [(2^4)(3^8)(4^20)(6^16)(8^16)] which I work out as 5.256. Then we choose a start cell (64 choices) make our first move (5.256 choices) then our second move (4.256 choices) then down to the 63rd move (which I take as 1 choice), reducing the factor 4.256 by 0.07 (i.e. 4.256/61) at each step. Finally we divide this total (N) by 16 (to give G). If my calculations are right this gives G = 1.91×(10^16). Blathy's original method was more complicated, involving cutting off the corners and merging cells such as b3-c2 to leave a 56-cell board, and various other refinements, to arrive at a total for the 64-cell board of 6×(10^11), which, if the most recent results for closed tours are correct, is too low a figure.
The result in heavy type above is compatible with the total of reentrant tours deduced from the results of Knuth and McKay reported in the next section. If the number of reentrant tours is 1/16 of the number of open tours, as is the case for the compartmental tours enumerated below, then the number of reentrant tours, as derived from the Knuth and McKay data, suggest a total G = 1.6×(10^15).
To determine the exact number of open tours remains an open problem.
|
From various correspondents it appears that the number of 8×8 open tours is no longer unknown. We can take Chernov's figure [link below], and since all even × even open tours are asymmetric, can divide by the number of symmetries (8 for the original figures, 16 for the OEIS version as they include reverse directions as well) to get G = 1,224,489,260,686,244 - which is somewhat less than the earlier estimates, but not unreasonable. We can also get for the 6×6, G = 414,870. Both 6×6 and 8×8 have a probability of being re-entrant higher than 'chance' because of the non-random distribution of endpoints. Link to A Chernov (Alex Black) site: Open Knight's Tours Extract from the Chernov site (in computer translation from Russian): In 1997, Brandan D. McKay counted [link below] the number of closed paths of a knight on 8×8 board. For unclosed paths, only an estimate of the number is known [cites our page here]. On the network we managed to find a page [link below], where Guenter Stertenbrink gives data by the number of paths for different boards, including 7×7. The number of open knight paths for a 7×7 board is 82787609160. That's without regard to direction. Taking into account the direction, there are twice as many and equal to 165575218320. The number of open paths of the knight for an 8×8 board is equal to 9795914085489952 or taking into account the direction of 19591828170979904. He then describes the algorithm that was used to count the quantity and the results are given. Link: Brendan D.McKay Knight's Tours an 8x8 Chessboard Link: Guenter Stertenbrink 2005/02/24 Number of Knight's Tours . |
Brave attempts were made to calculate the figures for closed tours in the precomputer age. Paul de Hijo (1882) estimated B as more than 413,000, and H. J. R. Murray (1942) placed it between 350,000 and 390,000, but these figures are now known to be short by a factor of about two.
D. E. Knuth (in a letter to G. P. Jelliss, 5 January 1993) stated that the number of symmetric closed tours is B = 608,233. This total has been confirmed by McKay (1997). [In the letter cited Prof. Knuth also incidentally added that the number of 8×8 closed symmetric celtic tours is 2321. These are tours in which no triangles of minimum size occur (such as formed by the moves a1-c2, b2-d1, b1-c3).]
B. D. McKay, (1997) has reported that the total number of closed tours (or in his jargon “equivalence classes under rotation and reflection of the board”) is C = 1,658,420,855,433. These results combined give the number of asymmetric closed tours A = 1,658,420,247,200 and the number of closed tour diagrams (in his jargon “undirected tours”) as D = 13,267,364,410,532. This work doesn't seem to have received any independent confirmation yet. The previous figure for D published by M. Löbbing and I. Wegener (1996) is definitely wrong (not being divisible by 4).
From these results we can also deduce the reentrant tours total R = 106,138,915,284,256 = 8D.
Probably the most natural way to form tours on larger boards is to divide the board up into smaller tourable compartments and to join together tours in those compartments in some way. Our test for whether a tour is compartmental is that the number of moves through the edges of any compartment (which must consist of more than one cell) shall be one or two.
One of the simplest ways of constructing a knight's tour of the standard chessboard is to join together two 4×8 half-board tours. In the section on 4-rank boards we have reported how C. Flye Sainte-Marie (1877) correctly counted the tours on the half-chessboard. This he did by counting the 'half-tours' on the white-inner -black-outer cells of the 4×8 board finding 118 with inner end on the a file, 32 on the c file, 52 on the e file, 42 on the g file, from which the total of the full 4×8 tours is calculated as 118×32 + 32×54 + 54×42 = 3776 + 1728 + 2268 = 7772 geometrically distinct.
We can use these results to calculate the number of 8×8 tours formed from two 4×8 tours. If we make a single join between the ends there are three cases to consider, when the joining move is a4-c5, b4-d5, c4-e5. Other cases are rotations or reflections of these. As shown in the page on 4-rank tours the numbers of 4×8 tours commencing at a4, b4, c4, d4 are respectively 7630, 2740, 2066, 3108 (adding to twice the above total). So the numbers of 8×8 tours joining a4-c5 is 7630×2066 = 15,763,580, and those b4-d5 are 2740×3108 = 8,515,920, and those c4-e5 are 2066×3108 = 6,421,128. Adding these three totals we get, for the number of geometrically distinct 8×8 tours formed of two 4×8 tours connected by a single link, the grand total: 30,700,628.
Tours of this type were called by M. Kraitchik (1927) ‘parcours bi-semiaréolaires’ {double-halfboard tours} and he calculated their number as this figure multiplied by 4, that is 122,802,512, counting the number of different diagrams formed by them if the division line between the two half-tours is horizontal. [This number is quoted in Rouse Ball's Mathematical Recreations where it is wrongly described as “the number of reentrant paths of a particular type”.]
Probably of more interest are the 8×8 tours formed by joining two 4×8 tours together by two links to make a closed tour. In this case there are 12 geometrically distinct methods of joining. Note of course that the two ends of the 4×8 tour must be on opposite coloured cells, i.e. one in an odd-numbered file and the other even. We code the linkages according to the files used.
Using the numbers of geometrically distinct 4×8 tours with ends on given files, calculated as G(i,j) in the analysis of 4×8 tours, we find the following totals:
| Linkage | Formula | Calculation | Totals |
| 12,34 | G(1,2)×G(3,4) | 672×208 | 139,776 |
| 14,23 | G(1,4)×G(2,3) | 772×180 | 138,960 |
| 14,36 | G(1,4)×2G(3,6) | 772×136 | 104,992 |
| 16,34 | G(1,6)×G(3,4) | 502×208 | 104,416 |
| 16,38 | [G(1,6)/2]×[G(1,6)+1] | 251×503 | 126,253 |
| 18,36 | G(1,8)×2G(3,6) | 936×136 | 127,296 |
| 23,45 | G(2,3)×G(4,5) | 180×304 | 54,720 |
| 25,34 | G(2,5)×G(3,4) | 276×208 | 57,408 |
| 25,47 | [G(2,5)/2]×[G(2,5)+1] | 138×277 | 38,226 |
| 27,45 | G(2,7)×2G(4,5) | 120×304 | 36,480 |
| 34,56 | [G(3,4)/2]×[G(3,4)+1] | 104×209 | 21,736 |
| 36,45 | G(3,6)×2G(4,5) | 68×304 | 20,672 |
| total of closed double-halfboard tours 970,935 | |||
Of these closed tours we derive from the centro-symmetric connections (16,38) and (25,47) and (34,56) respectively only 502 + 276 + 208 = 986 symmetric tours. Tours of this type were first studied by Euler (1759). We can now calculate the number of tour diagrams, assuming the division line to be horizontal, since under this restriction each symmetric tour has two orientations and each asymmetric tour four orientations: T = 2S + 4(G – S) = 4G – 2S = 3,881,772.
We can also calculate how many reentrant tours are included among the single-linked open tours. By deleting one of the two links from the closed tours, each symmetric tour gives one reentrant tour and each asymmetric tour gives two, hence: S + 2(G – S) = 2G – S = R = 1,940,884. This figure, multiplied by 16 so as to count the tours in all 8 orientations and numbered from either end, i.e. 31,054,144, was given by E. M. Laquière (1881). Thus almost 1/16 of the double-halfboard tours are reentrant.
Here I seek to enumerate all tours of the Rogetian type in which each net is toured in one piece. The basic idea of the method used here is due to H. J. R. Murray, who gives an account of his attempt at the problem in The Knight's Problem ms (1942) pages 96-100. The total he arrives at is 3,964,272, but there appear to be some errors in the data he worked from, and his account is difficult to follow. Is it possible that I have made an error and missed out a factor of 2 or even 4 somewhere? The results reported below need to be independently checked.
A Rogetian tour of the type we are interested in is either an open tour with three slants or a closed tour with four slants. We deal with the more general open case first. [For an explanation of Roget's method and straights and slants see the history page on Squares, Diamonds and Roget's Method.]
If we divide the board into blocks of 2×2 cells and number them 1 to 16 then this numbering in conjunction with Roget's LEAP indexing gives a name to every cell on the board; for example L1 is the L-cell in block 1. If we number the blocks according to a wazir tour (I use the H-shaped tour, since it has maximum symmetry) then straights (LL, EE, AA, PP) take the knight to a block of opposite parity (even to odd or odd to even) while slants (LE, LA, PE, PA) do not alter the parity.
The LEAP index diagram on the 8×8 board has the properties that (a) 180° rotation does not alter any of the indices, (b) 90° rotation interchanges L and P but leaves E and A unchanged, (c) reflection in a diagonal interchanges E and A but leaves L and P unchanged, (d) reflection in a median interchanges both pairs (since such a reflection is equivalent to reflection in diagonal combined with 90° rotation).
The four nets formed by the straights can be seen to be distorted versions of the moves of a wazir (single-step rook) on a 4×4 board. The number of ways a knight can then tour one of Roget's nets, from one given block to another, is thus the same as the number of ways a wazir can tour a corresponding 4×4 board whose cells represent the blocks.
The three-slant tour (showing the letter K) illustrated here is one of 25 that include three three-unit lines; the others differ only in the paths of the end sections LL and AA (five choices each: end blocks 1, 3, 9, 11 or 13). I dedicate this tour to Donald Knuth: the three lines of the K enclose a size 2 triangle. A closed four-slant tour with four three-unit lines is impossible. Two of the 25 tours are reentrant, but I have preferred the non-reentrant tour shown since it is unique among the 25 in that its four knight-paths are equivalent to the same non-reentrant wazir tour.
|
Theorem: Any directed three-slant open tour can be arranged, by rotation, reflection or reversal of direction
of description (if necessary) so that it tours the four nets in the sequence LEPA.
|
If a tour is presented in LEPA form it remains in LEPA form when rotated 180°, but the middle EP slant is altered from (a, b) to (a ± 8, b ± 8) where a and b are the numbers of the blocks it connects. So we only need to calculate the number of tours with the EP slant starting on a low-numbered block (1 to 8).
A complete LEPA tour is formed of four paths, LL, EE, PP, AA joined by three slants LE, EP, PA. If the middle slant EP is odd (i.e. connects odd-numbered blocks) then slants LE and PA must be even, and vice versa. The list of blocks used by the end cells and slants gives a sort of ‘formula’ for a Rogetian tour. For example the illustrated tour (K) has formula 13(8,10)(1,5)(16,8)13. If we ensure the middle E < 9 then there are 8×12×6×6×8 = 432×64 formulae with odd EP (there being 8 choices for the end-points namely all the odd blocks, 12 for even LE, 6 for odd EP, 6 for even PA) and there are 8×6×3×12×8 = 216×64 formulae with even EP; total (432 + 216)×64 = 648×64 = 41,472.
The numbers of wazir tours from corner, middle and edge cells to other cells are summarised in these three charts: The start cell is marked X.
A corner (52)
8 0 4 0 0 8 0 4 6 0 8 0 X 6 0 8 |
B middle (36)
8 0 4 0 0 4 0 4 2 X 4 0 0 2 0 8 |
C edge (25)
6 0 2 0 X 2 0 1 4 0 4 0 0 2 0 4 |
If we take the median value of 4 choices for each of the four connecting routes LL, EE, PP, AA, this provides us with a rough estimate for the total number of 3-slant tours of 41472×256 = 10,616,832 = approx. 10 million, which proves to be close to the actual figure found.
To express the calculation of the number of three-slant knight tours mathematically denote by LE(i,j) an array which takes the value 1 if cell Li joins to cell Ej and 0 otherwise. This represents all the LE slants. Arrays EP(i,j) and PA(i,j) are similarly defined. Then let C(i,j) denote the number of wazir routes connecting block i to block j. This will be 0 when i and j are both odd or both even. The values of C(i,j) for i odd and j even are shown below. This table can be read row-column or column-row, since C(i,j) = C(j,i). Also shown are the even values of LE(i.j); the six odd-value 1s occur at {1,5}, {1,9} and {9,13}.
C 1 3 5 7 9 11 13 15 |
2 4 6 8 10 12 13 16 2 2 8 4 4 4 8 4 6 6 8 8 4 4 8 8 2 4 6 2 2 1 4 4 1 2 6 2 4 2 4 4 4 4 8 4 2 2 8 4 4 4 8 8 6 6 8 8 2 1 4 4 2 4 6 2 4 2 4 4 1 2 6 2 |
eLE 2 4 6 8 10 12 14 16 |
2 4 6 8 10 12 13 16 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 |
We can now calculate the number of LEPA tours between blocks a and h from the formula:
[C(a,b)LE(b,c)C(c,d)]EP(d,e)[C(e,f)PA(f,g)C(g,h)] summed over the repeated suffixes (Einstein's convention).
Since LE for example is either 1 or 0 the first bracket only gives a nonzero value when the LE value is 1:
it merely acts as a ‘permitter’. This calculation can be reduced to the smaller 8×8 arrays instead
of 16×16 by treating the cases with EP even or odd separately.
The above calculations, done by hand using a small electronic calculator in the early 1990s, led to the following results (not yet independently checked, which is why I am not reproducing the full calculations just this summary). The LE column gives the number of LL-EE routes ending at block x. The EP column is the middle slant (x, y). The PA column gives the number of PP-AA routes starting at block y. The third column is the product of these two numbers.
| LE | EP | PA | Product |
| 1708 | (1,3) | 1336 | 2,281,888 |
| 1708 | (1,5) | 546 | 932,568 |
| 2668 | (3,1) | 704 | 1,878,272 |
| 1191 | (5,1) | 704 | 838,464 |
| 1191 | (5,7) | 510 | 607,410 |
| 1227 | (7,5) | 546 | 669,942 |
| 510 | (2,16) | 1708 | 871,080 |
| 704 | (8,10) | 1227 | 863,808 |
| 704 | (8,16) | 1708 | 1,202,432 |
| Total tours with 3 slants 10,145,864 | |||
The above count of tours with three slants includes reentrant tours, where the initial L-cell and the final A-cell are a knight's move apart. These AL moves are slants. Thus every reentrant open tour with three slants determines one closed tour with four slants. However, from one closed tour with four slants we can derive eight reentrant open tours with three slants, by deleting the AL slant in each of the eight orientations of the tour, which are all distinct since all Rogetian closed tours are asymmetric (symmetric tours contain at least eight slants).
The same formulae can be used for the calculation as given for three-slant tours, except that the values inserted for the first and last factors have to be reduced to apply to individual initial and final cells. Note that the total of reentrant tours with odd middle-slant is the same as the total with even middle-slant. This follows since from each closed tour we derive two even-middle and two odd-middle reentrant tours. Since this enumeration has not been independently checked only a summary of the totals is given here.
| L1-A9 | 205,232 | |
| L1-A15 | 148,812 | odd subtotal: |
| L7-A9 | 147,756 | 501,800 |
| L2-A4 | 42,316 | |
| L4-A2 | 46,428 | |
| L4-A8 | 64,360 | |
| L6-A8 | 157,616 | |
| L8-A4 | 58,344 | even subtotal: |
| L8-A6 | 132,736 | 501,800 |
| Total reentrant tours with 3 slants: 1,003,600 | ||
| Total closed tours with 4 slants: 125,450 | ||
| (this is an eighth of the reentrant total) | ||
As has been noted in the history pages, Roget's method is often confused with the squares and diamonds method. This is because there are some tours that are of both these types. The Rogetian tours with three slants that are also squares and diamonds tours can be enumerated by adapting the methods outlined above. The number of wazir tours connecting the blocks is considerably reduced under this condition. There is only ever one possible connection, or none. I find the results:
| Total 3-slant open tours of squares and diamonds type = 2688 |
| Total of these reentrant = 368 |
| Total 4-slant closed tours of squares and diamonds type = 368/8 = 46 |
As a check on these results I have actually constructed these 46 tours by a graphical method, and show them in an Appendix: Closed Squares and Diamonds Tours with 4 Slants.