The enumerations of 3×n tours described below have mainly been obtained by the method of breaking up a tour into components, which are groups of cells symmetrically arranged, with the property that the pattern of knight's moves connecting the cells of the component can be reflected or rotated without breaking its links with the other components of the tour. The cells and moves within a component are usually interconnected, but this is not essential. A diagram with k singly-symmetric components represents a family of 2^(k–1) tours, formed by twiddling the components, keeping one fixed (i.e. two components give 2 tours, three give 4 tours and so on).
The tours are catalogued by increasing size of board, and later sections are restricted to symmetric tours. Closed tours have now been put onto a separate page.
In a tour of a three-rank board with no end-points in the first two files the moves through these files form a fixed pattern (or its reflection top to bottom). If there are no end-points in the first three files, the moves through these files form one of two patterns: a 10-cell component (A) or a 12-cell open tour 3×4 (B).
Proof: (a) In a tour without end-points on the first two files the moves through a1, a2, a3 and b2 on any three-rank board are fixed, and they determine also the path through c2. Now we cannot have b1-d2 and b3-d2 because a 6-move short circuit is formed, and we cannot have b1-c3 and b3-c1 since an 8-move short circuit is formed. We must therefore have either b1-d2 and b3-c1 or its reflection b3-d2 and b1-c3. The first files of a tour with no end-points in the first two files can thus always be oriented to show the pattern in the first diagram below. (b) From c1 we must now connect either to e2, producing the comet pattern (A) or to d3 which completes the 3×4 tour (B).
Any knight's tour on a three-rank board can be extended by four files.
Proof: The asymmetric 3×4 tour (B) can be attached to one end of the tour by deleting a vertical move in the last two files and joining the loose ends to the ends of the 3×4 tour. (In the diagram the deleted move is printed lightly and the inserted moves are printed heavily.) Such a vertical end move always exists since if none existed the only possible end formation would have end points in both corners, entered horizontally, and two such moves join to give a two-move path, not a tour.
Open knight's tours exist on all 3×n boards except 3×3, 3×5 and 3×6.
Proof: (a) No tour exists on the 3×3 board since a knight on the centre cell has no cell to move to. (b) No tour exists on the 3×5 since a tour on an odd×odd board must be open and have its ends on cells of the majority colour (when the cells are coloured alternately, i.e. chequered); the cells a2 and e2 on the 3×5 are of the minority colour and the passages through them form a short circuit. (c) No tour is possible on the 3×6 since there are 22 moves incident with the two middle files, and only 4 other moves. An open tour would use 17 moves, at most two on each cell of the middle files, making 12, leaving 5 others required, but only 4 are available. (d) Tours on 3×4, 3×7, 3×9 and 3×10 boards are shown hereafter. (e) The existence of tours on boards of all other lengths is proved by the four-file extension method shown above. The 3×4 extends to 3×8 and every side > 10 equals 4k + 7, 8, 9 or 10.
The impossibility of 3×5 and 3×6 tours was noted by Euler (1759) and by Willis (1821) but without proof.
Symmetric open tours exist on all 3×n boards except 3×3, 3×5 and 3×6.
Proof: (a) On 3×3, 3×5 and 3×6 no tours exist by the earlier theorem. (b) Copies of the corner-to-corner 3×4 tour join together to cover all boards 3×4k symmetrically. (c) Symmetric tours b2...y2 (where y is the next-to-last file) exist on boards 3×7, 3×9, 3×10, 3×11, 3×13, 3×14 (for examples see hereafter) and these extend at both ends by the method given above to cover all further cases.
This is the smallest rectangular board admitting a knight's tour. The three geometrically distinct tours were given by Leonhard Euler (1759). Actually he gave them in numerical form in which case there are four, since the asymmetric one gives two distinct numerical forms.
The 14 tours were counted by U. Papa (1920). By end-separations there are 6 {1,1}, 2 {1,3}, 4 {1,5} and 2 {0,4}, the last two being symmetric. The tours are related by reflection of components, for example the star in the last three files of the first tour reflects in the f file (or pivots about f3) to give the second tour, and then the star extended by one move reflects in the middle rank to give the third tour, and by reflection in the f-file again gives the fourth tour. The tours in the second row are similarly related, and each is derived from the one above by left-right reflection of the central lozenge. The four tours in the third row are also related this way and by up-down reflection of the comet. In the two symmetric tours (which provide the b2-y2 example for Theorem 3.4) the moves on the cells b2, f2, d1, d3 form a disconnected component that is reflected in the centre file.
The construction of tours on this board has been especially popular, presumably because they can be used together with 5×8 tours to form compartmental tours of the 8×8 standard chessboard. Nevertheless, their enumeration has proved to be a tricky problem. The correct figure of 104 does not seem to have been given until my article in Chessics (1985). Of these tours 10 are symmetric (Papa 1920) and therefore the number of oriented tours is 10×2 + 94×4 = 396 (Kraitchik 1927 found only 376). My method of counting the tours was to classify them by separation of end-points. There are nine classes: {0,1} 29, {0,3} 13, {2,3} 9, {1,4} 7, {0,5} 3, {2,5} 4, {1,6} 18, {0,7} 11, {2,7} 10. I give diagrams of all 104 tours beginning with the ten symmetric, and six related tours. There are 9 tours occurring in sets of three, which are of special interest since they are formed of three components, but give only three geometrical forms, not four, due to the rotational symmetry of the central component (shown darker in the diagrams). This curious feature is evidently one of the causes of the difficulty of the enumeration. There are six symmetric tours of this type. There are three compartmental tours (i.e. separable into two rectangles with a tour in each part and no more than two links across the partition line), these are formed by joining two 3×4 tours; two of them are symmetric. Two more symmetric tours occur in a set of four tours with ends in the middle of the first and last files, thus belonging to the {0,7} class.
There are 16 semi-compartmental tours in which the asymmetric 3×4 tour occurs at one end, extending two tendrils to cover the other half of the board.
There are 48 tours that have a 9-move comet at one end. They are shown here with the comet on the left and in the same orientation throughout. They occur in pairs, the right-hand part of the tour being reflected top to bottom. In 28 of the tours the right-hand part is formed of two separate components; in these cases four similar tours are formed by twiddling the components.
Six tours in the above class contain three two-move lines.
The following eight tours are formed by twiddling the same four components:
There remain 16 other 3×8 tours:
There are 146 open tours. In terms of separation of ends the numbers are: {0,2} 19, {0,4} 10, {0,6} 3, {0,8} 20, {1,1} 29 {1,3} 8, {1,5} 8, {1,7} 12, {2,2} 4, {2,4} 10, {2,8} 24. There are no {2,6} tours since if we take the ends to be at say a3, g1 the moves through the cells a2, i1, i2, i3 are fixed; since g1 is an end-point h3 must connect to f2; to avoid a 6-move circuit h1 must connect to g3; but now e2 can only connect to c1, c3, forming a 4-move circuit. The 20 {0,8} tours and 8 of the {0,2} tours have ends on adjacent corners. Only 12 of these tours are symmetric; they were given by Kraitchik (1927), though he counted 16. The {0,6} examples provide the b2-y2 tour required by Theorem 3.4.
This and the 5×6 board are the smallest rectangles on which closed knight's tours are possible. There are 22 symmetric open tours (4 reentrant, derived from the bergholtian closed tours); the 18 non-rentrant are shown below (note the two b2-y2 examples for Theorem 3.4). To fit in more we leave out the board lines.
The enumeration of the symmetric open tours on this board has proved to be another difficult case. The correct total is 60. (Kraitchik 1927 reported 58, Murray 1942 counted only 56, computer work by D.E.Knuth 1994 confirms the total 60). By end-point separation: {0,4} 2, {0,8} 12, {2,2} 12, {2,6} 4, {2,10} 30. The first four diagrams below each represent 2 tours. The next 11 diagrams each represent 4 tours. Where two moves of the central lozenge are used the other two can be taken instead (this is a case of a disconnected component). The last diagram generates 8 tours: 4 tours of {2,6} type and 4 of {2,10} type, since the 7-move stars at the ends can be twiddled about b1 and j3. Note the existence of b2-y2 tours as required by Theorem 3.4.
There are 76 symmetric open tours. Classified by end-point separation: {0,1} 4, {0,3} 6, {0,5} 5, {0,9} 6, {0,11} 10, {2,3} 10, {2,5} 4, {2,9} 4, {2,11} 27. One of each case is shown below (including the b2-y2 example for Theorem 3.4). There are two compartmental tours 3×(3×4), not diagrammed.
There are 160 symmetric open tours. Classified by end separation: {0,2} 24, {0,6} 8, {0,10} 16, {2,4} 16, {2,12} 96. Thus 60% are corner to corner tours. The {2,8} case is impossible: if the ends are taken as c3, k1, then moves through a1, a2, a3, b2, l2, m1, m2 m3 are fixed; now b1 must go to d2 and l3 to to j2 because of the ends; now we must connect b3-c1 and l1-k3, since b3-d2 or l1-j2 form 6-move circuits; but now the paths through e2, i2 form a 4-move circuit. Many of the tours occur in pairs according to which way the moves of this central lozenge are taken. We give a few examples, including each possible position of the end-points (one of which is a b2-y2 example for Theorem 3.4).
D.E.Knuth reports 292 symmetric open tours 3×14. The two examples illustrate general designs I found, which I call barbed wire and brickwork, that can provide symmetric open tours on most 3-rank boards of greater length by extending the repetitive scheme. The latter provides the last b2-y2 example for Theorem 3.4.
Table of numbers of open knight tours on 3-rank boards
n 3 5 7 9 11 13 15 17 19 S 0 0 2 12 60 160 652 2600 9152 G 0 0 14 146 2698 32296 460022 5851548 >10M n 4 6 8 10 12 14 16 18 20 S 2 0 10 22 76 292 1148 3870 13710 G 3 0 104 773 14350 161714 2159232 >10M >10M
G = number of geometrically distinct tours, S = number of geometrically distinct symmetric tours. M = million. There are thus G – S asymmetric tours and each of these can be viewed in 4 different orientations (within the given rectangular outline) while each symmetric tour has 2 distinct orientations. Thus the total of tour diagrams possible is T = 4(G – S) + 2S = 4G – 2S, for those who wish to calculate this quantity.
The above totals for open tours on 3-rank boards of length 14 or more are calculated from figures reported to me by Prof. D.E.Knuth in 1994. He has further results that he will no doubt be publishing himself, but totals not exceeding 10 million, are probably more than sufficient for those with a recreational interest in the subject, to whom these notes are directed.