Sections on this page: — What are we Counting?
— Total Numbers of 8×8 Knight's Tours
— Enumeration of 8×8 Compartmental Tours
— Enumeration of Rogetian Tours
— Appendix 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 endpoints 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 untourlike 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 b3c2 to leave a 56cell board, and various other refinements, to arrive at a total for the 64cell 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.
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 a1c2, b2d1, b1c3).]
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 halfboard tours. In the section on 4rank boards we have reported how C. Flye SainteMarie (1877) correctly counted the tours on the halfchessboard. This he did by counting the 'halftours' on the whiteinner blackouter 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 a4c5, b4d5, c4e5. Other cases are rotations or reflections of these. As shown in the page on 4rank 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 a4c5 is 7630×2066 = 15,763,580, and those b4d5 are 2740×3108 = 8,515,920, and those c4e5 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 bisemiaréolaires’ {doublehalfboard 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 halftours 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 oddnumbered 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 doublehalfboard tours 970,935 
Of these closed tours we derive from the centrosymmetric 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 singlelinked 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 doublehalfboard 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 96100. 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 Lcell in block 1. If we number the blocks according to a wazir tour (I use the Hshaped 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 (singlestep 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 threeslant tour (showing the letter K) illustrated here is one of 25 that include three threeunit 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 fourslant tour with four threeunit lines is impossible. Two of the 25 tours are reentrant, but I have preferred the nonreentrant tour shown since it is unique among the 25 in that its four knightpaths are equivalent to the same nonreentrant wazir tour.
Theorem: Any directed threeslant 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 lownumbered 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 oddnumbered 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 endpoints 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 3slant 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 threeslant 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 rowcolumn or columnrow, since C(i,j) = C(j,i). Also shown are the even values of LE(i.j); the six oddvalue 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 LLEE routes ending at block x. The EP column is the middle slant (x, y). The PA column gives the number of PPAA 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 Lcell and the final Acell 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 threeslant 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 middleslant is the same as the total with even middleslant. This follows since from each closed tour we derive two evenmiddle and two oddmiddle reentrant tours. Since this enumeration has not been independently checked only a summary of the totals is given here.
L1A9  205,232  
L1A15  148,812  odd subtotal: 
L7A9  147,756  501,800 
L2A4  42,316  
L4A2  46,428  
L4A8  64,360  
L6A8  157,616  
L8A4  58,344  even subtotal: 
L8A6  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 3slant open tours of squares and diamonds type = 2688 
Total of these reentrant = 368 
Total 4slant 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.