by George Jelliss
Types of Symmetry
A diagram shows 'n-ary' symmetry if it has n congruent parts that by reflection or rotation can take the place of any other. In the case of a square diagram n can be 2, 4 or 8, and the symmetry is accordingly termed 'binary', 'quaternary', or 'octonary'. In 'direct' symmetry the pattern can be reflected without change of appearance, while in 'oblique' symmetry reflection produces a non-superposable mirror image. These are Ernest Bergholt's terms. Octonary symmetry is direct, but quaternary and binary symmetry can be direct or oblique. The direct symmetries can also be subclassified as 'lateral' or 'diagonal' depending on the directions of the axes of reflection. Here are simple patterns of knight moves on the 4×4 board showing the various types of symmetry that are possible.
A pattern with octonary, quaternary, or binary-oblique symmetry can be rotated to superimpose with itself. The rotation is through 180 degrees in the binary-oblique and quaternary-direct cases, or through 90 (and hence also 180) degrees in the quaternary-oblique and octonary cases.
Tours and Pseudotours
By a knight's 'tour-pattern' I mean a pattern of knight moves on a board, having two moves incident at every cell. A tour-pattern is either a 'tour', that is a single circuit of knight moves that passes through every cell of the board, or a 'pseudotour', consisting of two or more superimposed circuits. (Note that we are only considering here closed tours and circuits, not open paths with end points.)
This is a convenient point to introduce the centre-outwards coding that I use, giving cells in similar positions the same number. It can be extended to apply to boards of any size.
The only possible knight's tour-pattern on the 4×4 board is the pattern of four circuits of four moves known as 'squares and diamonds' which has octonary symmetry. This is easily proved: the only moves available through the corner cells form the diamonds, and once these are in place the only moves remaining through the other cells form the squares. The squares are formed of moves (11) and the diamonds of moves (02) using the above coding.
The next square case, the 6×6 board, is more productive. No octonary tour-pattern is possible (since 36 is not divisible by 8), but there are twenty geometrically distinct quaternary patterns (i.e. not counting rotations and reflections as different).
There are seven oblique, including the five well known quaternary symmetric tours, which have been rediscovered many times, and are shown here in the first row. The other quaternary patterns are all pseudotours. The thirteen direct patterns comprise seven with lateral axes and six with diagonal axes.
The legends below the diagrams indicate the numbers of circuits and their lengths. Six of the lateral patterns consist of two circuits of 18 moves, while two of the diagonal type consist of three circuits of 12 moves. (Binary and asymmetric tour-patterns also occur, but we deal here only with the quaternary case.)
On the 8×8 board tour-patterns with octonary symmetry become possible once more, and there are 33 geometrically distinct cases, all pseudotours, as I showed in Chessics (#22 p.72, 1985 and #25 p.106, 1986). The numerous quaternary patterns formed of two or four equal paths were enumerated by the Abbé Jolivald (under the pen-name of Paul de Hijo) as long ago as 1882, and his results were confirmed by Tom Marlow as reported in Chessics (#24 p.92 1985). These however do not exhaust the cases.
Mixed Quaternary Symmetry
The only symmetry possible in knight's tours on boards of side 4n is the binary oblique type. The idea of constructing tours that show a combination of oblique and direct quaternary symmetries was introduced by Ernest Bergholt in some puzzles published in the British Chess Magazine in 1918, and elaborated in three memoirs that he sent to H. J. R. Murray that year, which are now in the Bodleian Library, Oxford. The memoirs were reproduced in issues 13, 14 and 18 of The Games and Puzzles Journal (1996 - 2001). There is probably further work on this subject among Murray's extensive papers for anyone who has the time to do the research.
The treatment given here expands and clarifies the methods of Bergholt and Murray by taking proper account of the octonary symmetry component, which they tended to regard as part of either the direct or the oblique component, depending on the focus of attention.
A knight's tour is said to show 'mixed quaternary symmetry' (MQS) if its moves can be regarded as forming three classes, one in purely lateral quaternary symmetry, one in purely oblique quaternary symmetry, and the remainder, such as the eight moves through the corner cells, in octonary symmetry. It follows that the tour as a whole is in oblique binary symmetry, since both types of quaternary symmetry include this lesser form of symmetry. It also follows that the cells used by the three sets all form arrays with octonary symmetry. Mixed quaternary symmetry is possible on any square boards of even side greater than 4, but is mainly of interest on boards of side a multiple of 4 on which a tour with quaternary symmetry is impossible, in particular the 8×8 and 12×12.
On a board of side 2m a tour has 4m² moves, so in a tour with MQS if the lateral quaternary class has 4h moves, the octonary class 4j and the oblique quaternary class 4k, then h + j + k = m², with j even. I put the octonary number, j, in the middle since it is counted with h when assessing the direct symmetry, and with k when assessing the oblique symmetry. The tour can then be described as of type h-j-k.
Theorem: The number of purely oblique components, k, must be odd.
In terms of coordinates a knight's move is a {1,2} leap, and can be classified as 'horizontal' or 'vertical' according to the direction of the two-step part of the move. Four moves in lateral symmetry are either all horizontal or all vertical, since reflection in a median does not alter this property. On the other hand, four moves in oblique symmetry consist of two vertical and two horizontal, since 90 degree rotation of a vertical move makes it horizontal, and vice versa. Moves in octonary symmetry can be split up into two lateral or two oblique sets. A tour with oblique symmetry on a board of side 2m consists of two congruent paths each of 2m² moves, from corner to opposite corner. A lateral quartet contributes two vertical or two horizontal moves to this half-tour. An oblique quartet however contributes one of each type. The lateral and octonary moves thus always contribute a displacement of the knight by an even number of ranks or files from the initial corner. But the displacement from corner to corner is a displacement of (2m – 1) ranks and files, an odd number. Thus k must be odd. QED.
Mixed Quaternary Symmetry on the 6×6 Board
Among the 17 tours with binary symmetry on the 6×6 board there are two that show mixed quaternary symmetry. The h, j, k values of these tours are 2-6-1 and 4-4-1, the purely oblique component being in each case the four (02) moves, shown in the middle diagram. The lateral and octonary components are also shown.
Minimal Oblique Moves in MQS
The minimum of purely oblique moves is 4 (k = 1) on boards of side 4n + 2 (i.e. 6×6, 10×10 etc) but is 12 (k = 3) on boards of side 4n (i.e. 8×8, 12×12, etc). I give a proof of this since it is not obvious:
Theorem. The minimum purely oblique moves cannot be k =1 on boards of side 4n.
Consider the possible linkages. The four moves in oblique quaternary symmetry can only be of the type (02), connecting cells on the diagonals in an octonary pattern, as shown or its reflection. Ignoring paths that cross at the centre, there are three geometrically distinct ways in which these cells can be joined to form a tour by paths that are in lateral quaternary symmetry.
The first linkage, which can also be rotated 90 degrees, connects dark to light cells, so must use four paths of two odd lengths; but an odd length path cannot have the required symmetry, since the middle move would have to cross the median at right angles, which is impossible for a knight move. The second and third linkages connect dark to dark and light to light cells, so must use four paths of even lengths adding to 16n² – 4 (i.e. 60 on the 8×8 board). But lateral symmetry requires that all these be of the same length, and (16n² – 4)/4 = 4n² – 1, is an odd number (15 on the 8×8 board). Thus k = 1 is impossible. QED
MQS on the 8×8 Board: the 13:3 case
As proved by the above theorems the minimum purely oblique quaternary moves in a mixed quaternary tour on the 8×8 board is 12 (k = 3), the other 52 moves being in direct quaternary symmetry (h + j = 13). Tours of this 13:3 type were those mainly studied by Bergholt. They can also be described as tours with maximum direct quaternary symmetry.
The cells used by the twelve oblique moves must form an octonary pattern. If the twelve moves are all separate single moves they will use 24 cells, but this will reduce to 20 if a double move is used, or to 16 if they join to form a triple move. In an octonary pattern an off-diagonal cell will contribute 8 and a diagonal cell 4, so the patterns can be classified by the numbers of these cells used. Using all four diagonal cells (0, 2, 5, 9) is impossible since the corner cells necessarily form part of the octonary set of moves. So we must use one, two or three of the diagonal cells. The only triple moves possible using two off-diagonal cells are (6116), (4114), (3113), but four (11)-moves in oblique symmetry cannot be used since they form a circuit. We thus have five cases: 24 = 3×8 = 2×8 + 2×4, and 20 = 2×8 + 1×4 = 1×8 + 3×4, and 16 = 1×8 + 2×4.
In the 3×8 class I find three choices of off-diagonal cells that will connect in the required manner, namely (134), (146), (347). Of these (134) produces no tours on the 8×8, though it can be used for tours on larger boards, (146) gives 19 tours and (347) a single tour. The h-j-k numbers take the values 3-10-3, 5-8-3, 7-6-3. The single (347) example is of maximum octonary type 3-10-3. This and one of the (146) tours are shown, together with the patterns of oblique moves on which they are based.
In the 2×8 + 2×4 class, I find nine possible combinations: (0123) 2 tours, (0126) 33 tours, (0135) 12 tours, (0145) 3 tours, (0156) 28 tours, (0234) 2 tours, (0238) 31 tours, (0456) 20 tours, (1256) 22 tours, total 153 tours. Diagrams of all of these will be shown on my knight's tour notes webpages in due course. There is space here only for one from each case. For a (0156) example see further below.
In the double move 2×8 + 1×4 class there are five possible types: (013) 9 tours, (014) 3 tours, (034) 5 tours, (156) 49 tours, (238) 6 tours, total 72. All of these were identified by Bergholt, except for type (014). (For diagrams see The Games and Puzzles Journal #18.)
In the double move 1×8 + 3×4 class I have found only the one type (0256), with 8 tours. The 3-10-3 case was cited by Murray; there are also three 5-8-3 and four 7-6-3.
In the triple move 1×8 + 2×4 class there are six tours of type (023). Bergholt classified these tours as two different types. They use the same key cells but differently connected. (For diagrams see The Games and Puzzles Journal #18.)
MQS on the 8×8 Board: the 11:5 case
Following on from the above examples, it is natural to consider tours with 5 sets of moves in pure oblique quaternary symmetry. If all 20 moves are separate they will use 40 cells forming an octonary pattern. If all these cells are off-diagonal we have the 40 = 5×8 case. I find that there are two types in this class. The only pattern usuing the next to corner cell, 8, is Type (13478), but this does not generate any tours on the 8×8 board, though it can be used on the 12×12 board. The only other case is Type (13467), it gives four tours:
Minimal Lateral Moves in MQS
The minimum of purely lateral moves is 0 (h = 0) on boards of side 4n + 2, since these are the boards on which tours with oblique quaternary symmetry are possible. On boards of side 4n the minimum is 4 (h = 1). In 2001 I enumerated all tours of this type on the 8×8 board and found 48 in all (as mentioned in The Games and Puzzles Journal #18, p.332). They consist of 12 of 1-10-5 type, 20 of 1-8-7 type, and 16 of 1-6-9 type. The four lateral moves are (11)-moves. Another 1-10-5 example is shown above.
A 1-4-11 tour is impossible. The maximum moves in oblique quaternary symmetry in MQS on the 8×8 board is thus 60 moves (4×15), as in these examples, but the maximum of purely oblique moves is 36 (k = 9). The two 1-6-9 examples shown here both use the same cell-sequence (1656494378203871), and differ only in taking the (20) move in a different direction.
Minimum Octonary Moves in MQS
The minimum number of octonary moves in a tour of mixed quaternary symmetry on a board of any size is 16 (i.e. j = 4), having four moves in each quadrant, consisting of the 2 moves through the corner cell and 2 moves incident with the next-to-corner cells. There are three minimal formations, any other routes through the next-to-corner cells will result in six octonary moves. However it turns out that case C is impossible, at least on the 8×8 board, as other octonary moves are forced.
I have found 20 of type A among the 13:3 cases considered above. Type B tends to require more oblique moves. Here are four examples from the 19 I have found so far, 3 (9-4-3), 11 (7-4-5), 5 (5-4-7).
The maximum octonary moves in a mixed symmetry tour depends of course on the size of the board, for the 6×6 board it is 24 (j = 6) and for the 8×8 board it is 40 (j = 10). (In a binary tour without the mixed quaternary condition 48 can be achieved.)