There are indications in some of the mediaeval manuscripts (see the Early History page) of an understanding of the structure of knight's tours on the 4×8 board, and numerous examples on that board were constructed. Euler (1759) was aware that a closed knight tour is impossible on any 4-rank board and that the tour must start and finish in the outer ranks. However, a proof of these points and a full and sound analysis of the problem was first presented by C. Flye Sainte-Marie at the 18 April 1877 meeting of the French Mathematical Society. He arrived at the correct total of 7772 for the 4×8 tours and indicated how to calculate the results for all boards 4×n.
In a knight's tour of a 4×n board a closed tour is impossible, the ends of the tour must lie in the outer ranks, and the tour must consist of separate tours of two fixed groups of 2n cells (the white outer and black inner or the white inner and black outer cells), which are linked by a single move on the inner ranks.
Proof: (a) Number the files 1 to n from one end of the board and divide the cells into two sets: (1) the upper cells in the odd-numbered files and the lower cells in the even-numbered files, marked X below; (2) all the other cells. Then a knight on an outer cell can move only to an inner cell in the same set. Thus a passage from one set to the other is only possible by a move on the inner ranks. (b) An open tour consists of 4n – 1 moves, and at least one of these must join inner cells, so we cannot have more than 4n – 2 moves that link to an outer cell, but on the other hand it is not possible to have less than this number, since there are 2n outer cells, and of these at least 2n – 2 must have two knight's moves linked to them, there being only two cells (the ends of the tour) linked to one knight's move, and (2n – 2)×2 + (2)×1 = 4n – 2. Thus there can only be the one inner-to-inner move.
An alternative argument by contradiction, attributed to Louis Posa, to prove the impossibility of a closed tour, runs: The numbers of inner and outer cells are equal and outer cells link only to inner cells, therefore in a closed tour inner and outer cells must alternate, but we know that white and black cells must also alternate, so the outer cells must all be of one colour and the inner cells the other colour, which we know is untrue.
Sainte-Marie's analysis shows that to enumerate the tours on a 4×n board we need to enumerate the partial tours of the two sets of cells and then calculate the number of ways they can be joined together to make complete tours. It should be noted that the two sets are always the same shape (an alternating array of "dominoes"), and one set is the reflection of the other in the horizontal median, so that we only need to enumerate the partial tours on one set.
Open knight's tours exist on all 4×n boards, with n > 2, except the 4×4.
Proof: (a) Tours on the 4×3 board were given in the page on 3×n open tours. (b) On the 4×4 board there are four half-tours, as shown below, but since their inner ends are all on the a-file, or after 180° rotation on the d-file, no two can be linked by a knight move to complete a tour. (c) A tour on a 4×n board that has a braid in the two files at one end can be extended to form a tour of a 4×(n+2) board, as shown below, where 4×3 is extended to 4×5 and then to 4×7, by replacing each move in the braid by the other three moves of the square or diamond to which it belongs. From this tour and a 4×6 tour (see the following catalogue) tours of all other sizes can be formed.
Each half-tour on the 4×n board with one end on the inner cell of the r file and the other end on the outer cell of the s file has a 'dual' half-tour that has one end on the outer cell of the r file and the other end on the inner cell of the s file, and visits all the files in the same sequence reversed.
Proof: The domino pattern of the cells covered by a half-tour has two cells in each file. From the cells in file a, say a1 and a2, there are two moves a1-b3, a1-c2 and a2-b1, a2-c1. If we omit the rank numbers from these moves they remain fully determinate by specifying the file names alone, and become a-b and a-c in each case. This feature remains true on the other files. Thus a half-tour can be specified by a sequence of file-names, and the same sequence of file-names will still specify a half-tour no matter at which of the two cells in the file it starts. (This result was noted by Murray 1942, though he did not use the term 'dual').
This 'duality' is a result of the bipartite and regular nature of the knight-move network on the domino set: there are four knight's moves attached to every cell except the cells in the end files, which are of degree two, and there are no links between outer cells or between inner cells.
If H(r,s) denotes the number of 4×n half-tours beginning on the outer cell of the r-file and ending on the inner cell of the s-file then the the array H(r,s) is symmetric about both its diagonals.
Proof: (a) The relation H(r,s) = H(s,r) follows from the previous theorem, since to each (r,s) half tour corresponds its dual which is an (s,r) half-tour. Thus the array H(r,s) is symmetric about its principal diagonal. (b) The domino set is symmetric. When n is even the group has 180° rotary symmetry, while when n is odd it has a vertical axis of symmetry. Thus a partial tour connecting files r and s is converted into one connecting files r* and s* by 180° rotation or by reflection in the vertical median, where i* denotes the i-th file from the other end of the board, i.e. i* = (n + 1) – i. Thus, H(r,s) = H(n + 1–r, n + 1–s), which means that the array H(r,s) is unaltered by a 180° rotation. (c) Combining these results H(r,s) = H(n + 1 – s, n + 1 – r), i.e. it is symmetric about its secondary diagonal.
Denoting the numbers of geometrically distinct complete tours from file i to file j by G(i,j) we have the same symmetry properties as for H(i,j), though for a simpler reason in case (a), since any tour can be reversed. When i and j are of the same parity (both even or both odd) the end-points are in opposite edges of the rectangle, while when they are of opposite parity (even and odd) they are in the same edge.
The following relations hold for H(r,s) on any 4×n board: (1) H(1,3) = H(1,2), (2) H(2,4) = H(1,2) – H(2,3), (3) H(3,4) = H(3,3), (4) H(3,5) = H(2,4) – H(3,4).
Proof: These relations express numbers of (r,s) half-tours in terms of numbers of (h,k) half tours, where h < r and k < s. To prove (1): every closed half-tour through a2 must use the moves a2-b4 and a2-c1, and deletion of a2-b4 converts it into a reentrant half-tour of type (1,2) while deletion of a2-c1 converts it into a reentrant half tour of type (1,3); conversely any half-tours of types (1,2) and (1,3) are reentrant and determine a unique closed half-tour, hence the equality. To prove (2): the half-tours of type (2,4) are reentrant and are equal in number to those closed half-tours that do not include the move 2-3. To prove (3): tours from c2 to d4 must follow the routes c2-a1-b3-c1-a2-b4-d3, while tours from c2 to c1 must follow the routes c2-a1-b3-d4 and d3-b4-a2-c1, leaving the rest of the half-tour to connect d3 to d4 in each case. To prove (4): the half-tours of type (3,5) are reentrant and are equal in number to those closed half-tours that include 2-4 but do not include 3-4.
The number of partial tours with inner terminal on file i is H(i) = H(i,1) + H(i,2) + ... + H(i,n) = S(j)H(i,j), that is the summation of the i-th rank or file of the H(i,j) matrix. From the double symmetrry of H(i,j) we deduce that H(i) = H(n + 1 – i) = H(i*). For purposes of counting 4-rank tours it is helpful to always orient them so that the middle link is in a standard position. A simple rule is to have it as far to the left as possible and sloping upwards, that is a2-c3, b2-d3, c3-e3, d2-f3, ... Thus we only need to count the numbers of half-tours with inner end on the files 1 to n/2 when n is even, or 1 to (n + 1)/2 when n is odd.
If there are H(i) half-tours with inner end on the i-th file then (a) the number of geometrically distinct tours with internal connection i to i + 2 is normally H(i)×H(i + 2), but on a board of odd length there are two special cases: (b) when i is the middle file then the total must be doubled and (c) if i + 1 is the middle file then the total is H(i)[H(i) + 1]/2.
Proof: (a) If there are two independent choices that can be made in H and J ways respectively, then the number of ways of making the pair of choices is H×J. This is a basic combinatorial result. In case (b), when i is the middle file of the odd board the H(i) geometrically distinct half-tours have their inner end on the middle file so they can occur in two orientations, one the reflection of the other left-to-right, thus each gives rise to two tours, hence the total 2H(i)×H(i+2). [This anomaly in the rule could be avoided if we waived our general convention of counting geometrically distinct paths and chose in this case to count the number of oriented half-tours with inner end at i2; this doubles the total when i is the middle file.] In case (c) the choices are not independent since the same H(i) half-tours are available for each half, and we can choose two the same to form H(i) symmetric tours, or two different to form H(i)C2 = H(i)[H(i) – 1]/2 asymmetric tours [the number of ways of choosing two different things from a set of H(i)], thus the total is the sum of these, that is H(H – 1)/2 + H = H(H + 1)/2. This can also be expressed as H² – H(H – 1)/2 which indicates that by using the normal product formula for this case, giving H², we make the mistake of counting the asymmetric tours twice.
Symmetric 4×n knight's tours exist on all boards of odd length, but all tours on boards of even length are asymmetric.
Proof: On any board the two domino sets are related by reflection top to bottom. On an even-length board the two sets are also related by a reflection left to right, while on an odd-length board they are related by a 180° rotation. The latter case allows for the formation of centrosymmetric tours, but axisymmetric tours are not possible in the even case because the middle move in such a tour would have to cross the axis at right angles and the knight's move does not permit this. For a symmetrical tour to be possible the middle move of the tour must pass through the centre point of the board. This is possible only when n is odd.
The diagrams below show a systematic, centre-circling, method of constructing centrosymmetric tours on odd four-rank boards of any length. Note that the end-points are always a knight's move from the end-points of the middle move. The tours in the upper row proceed clockwise and those in the second row anticlockwise.
The diagrams above are examples of edge-hugging tours. On the 4×n board (n > 4) if we draw a barrier along the horizontal centre-line, apart from the first two and last two files, then the knight's moves that do not cross this barrier form an edge-hugging, or centre-circling, braid.
On an odd board, since the braid consists only of two circuits, the single middle move of the tour is the only link needed, as illustrated above. Each position of the middle move gives four geometrically distinct tours, except when the move is in the middle of the board in which case the number reduces to three. The number of edge-hugging tours 4×n with n odd is 2n – 3, two of which are symmetric.
On an even board, since the braid is of four circuits, three links are needed. No tour is possible on the 4×4. There are 12 tours 4×6, 24 tours 4×8, 40 tours 4×10, 56 tours 4×12 (the linkage polygons for these are shown in diagrams in the following catalogue. In each diagram there are two choices for each end point, i.e. four tours for each diagram). The number of tours of this type on a 4×n board (n even and > 6) is 8(n – 5). Thus 40 on the 4×10 and 56 on the 4×12.
This board was studied in the page on 3×n tours but the above theory appies to it and confirms the three tours found. There are three geometrically distinct partial tours, but one (0) cannot be used to form a tour since there is no internal link from the middle file. The three complete tours can be represented as 1-1, 1-2 and 2-2, the mixed one being asymmetric.
No complete 4×4 tour is possible. There are four half-tours, but no two can be combined to give a full tour since their inner ends are on the 1st and 4th files which have no connecting move. Each is composed of one 'square' and one 'diamond'.
Here there are 12 partial tours: H(1) = 8, H(2) = 3, H(3) = 1. Both the special cases mentioned above apply to the calculation of the number of tours. File 3 being central, with inner link 1-3 the total is 2H(1)×H(3) = 2×8×1 = 16, and with inner link 2-4 the total is H(2)[H(2)+1]/2 = 3×4/2 = 6, thus giving 16 + 6 = 22 geometrically distinct tours. The three symmetric tours were noted by Colonel Ugo Papa in an article in La Scienza Per Tutti, 15 August 1920. All the tours except the last symmetric case have one end at a corner.
The partial tours number H(1) = 20, H(2) = 11, H(3) = 6, total 37. This gives 20×6 = 120 tours with middle move 1-3, and 11×6 =66 with middle move 2-4. Thus the total of geometrically distinct tours is 120 + 66 = 186, all asymmetric since the board-length is even. Thus there are 186×4 = 744 tour diagrams. In the example tour below, the first 20 tours show all the half-tours from the first file, and the next 11 show all those from the second file. These are combined with the 6 from the third file, repeated sequentially. 4×6 Edge-hugging tours, total 12.
The partial tour numbers are: H(1) = 54, H(2) = 19, H(3) = 17, H(4) = 14, (total 104). So there are 54×17 = 918 tours with middle move 1-3, 2×19×14 = 532 of type 2-4, and 17×(17 + 1)/2 = 153 of type 3-5. The total of tours is 918 + 532 + 153 = 1603. There are 17 symmetric tours, shown below (apart from the two edge-hugging cases). So the total of 4×7 tour diagrams is 17×2 + (1603 – 17)×4 = 6378.
The partial tour numbers are: H(1) = 118, H(2) = 42, H(3) = 32, H(4) = 54, total 246. Thus the number of geometrically distinct complete tours is 188×32 (1-3 central move) + 42×54 (2-4 centre) + 32×54 (3-5 centre) = 3776 + 2268 + 1728 = 7772. This total was first given by Sainte-Marie (1877). Since all the tours are asymmetric the number of diagrams is 7772×4 = 31088. This board is half the standard chessboard, and various examples of historical interest are given in the Early History page. The following is a tabulation of H(i,j) and G(i,j).
| H(i,j) | G(i,j) | ||||||||||||||||
| 22 | 8 | 8 | 16 | 13 | 8 | 10 | 33 | 930 | 672 | 518 | 772 | 752 | 502 | 682 | 936 | ||
| 8 | 4 | 3 | 5 | 3 | 3 | 6 | 10 | 672 | 116 | 180 | 284 | 276 | 174 | 120 | 682 | ||
| 8 | 3 | 2 | 2 | 3 | 3 | 8 | 518 | 180 | 67 | 208 | 214 | 68 | 174 | 502 | |||
| 16 | 5 | 2 | 6 | 6 | 3 | 3 | 13 | 772 | 284 | 208 | 149 | 152 | 214 | 276 | 752 | ||
4×8 Edge-hugging tours, total 24. The tour given by Gianutio (1597) is of this type. Six of these 4×8 centre-circling tours have their end-points in a suitable relative position to form an 8×8 symmetric closed tour by linking to a rotation of itself.
There are 112 symmetric open tours. One example, chosen at random, of each end position is shown with the central move oriented d2-f3. [These were counted by Kraitchik (1927) who gave the total as 448, counting numerical arrays, and in L`Echiquier April 1927, problem 189, as 224, counting diagrams.]
Edge-hugging circuits: total 40.
Number of tours not determined. The following two examples are formed by linking together circuits forming pseudotours of 4×3, 4×4 and 4×5 boards.
Tours of squares and diamonds type are possible on this board. Examination of the half-tours of squares and diamonds type shows that there are 40 from a and d, 12 from c and b, 16 from e and f. Thus the number of S&D tours with middle moves a-c, b-d, c-e, d-f, e-g are respectively 40×12 = 480, 40×12 = 480, 12×16 = 192, 16×40 = 640 and 16×16 = 256, totalling 2048. It is necessary for a half-tour to complete two circuits in an end quad before making a second circuit in the middle quad, otherwise the middle quad acts as a barrier to completion of the path. Examples:
4×12 edge-hugging circuits, total 56. Ten cases as for 4×10 plus four extra cases:
Puzzle: To arrange the 52 cards of a standard pack in a knight's tour in the sequence Ace to King in each of the four suits so that each file contains four cards of the same rank.
To see the solution run the cursor over the space below:
The sequence of the cards along the ranks runs: 4 3 5 2 6 A 7 K 8 Q 9 J X (where X is 10).
click here for diagram of solution