Symmetry in Knight's Tours

by George Jelliss
Sections on this page: — The Significance of SymmetryTranslational SymmetryAmount or Degree of SymmetryReflective and Rotative SymmetryAlternative TerminologySymmetry in Open Knight PathsSymmetry in Closed Knight PathsSymmetry in Rectangular ToursCoding Methods for SymmetryCentral Angle Formations

The Significance of Symmetry

An aesthetic view of symmetry is expressed by Murray in his manuscript on The Knight's Problem (1942):

The graphical diagram of a tour takes the form of a geometrical pattern, and the pattern becomes of special interest when the figure also satisfies the principles of artistic design, that is to say, when the diagram exhibits an orderly or symmetrical repetition of detail. The more evident are these artistic features, the greater is the pleasure afforded by the tour.

It can however also be argued to the contrary, as has been done in other fields of art such as chess problem composition and in music, that repetition and formal structure are indicative of shortage of original content, or of a mechanistic rather than a naturalistic approach, and conducive to boredom. My own experience is that the pleasure given by a tour comes from appreciation of the uniqueness of the properties fulfilled by the tour, and symmetric properties are but one type of property, but nevertheless an important type.

Translational Symmetry

Knight's tours are usually constructed within a circumscribed area. However, knight-move patterns can also be constructed that can be repeated at regular intervals so as to cover an area of any size. This type of design is said to exhibit translational symmetry of the type seen in wallpaper patterns. The simplest such patterns are those consisting solely of straight lines of knight moves, and according to a study I made in 1985, reported in a Christmas and New Year card I sent that year, there are eight possible patterns of this type, as shown below.

Pattern 1 is the basic pattern formed of one set of close-packed parallels all in the same direction. Patterns 2, 3, 4 and 5 are formed from pattern 1 by rotating every second, third, fourth or fifth line through a suitable angle. Patterns 34, 35 and 45 are similarly formed from pattern 1 by rotating every third and fourth, third and fifth or fourth and fifth pairs of lines. These, and more complex patterns involving non-straight arrangements of knight moves, can often be used for filling the central area in large tours.

Amount or Degree of Symmetry

In counting patterns a clear distinction must be made between the pattern considered as a geometrical object, and a diagram of the pattern. Assuming that a rectangular diagram is printed with its sides in a given orientation, one pattern may nevertheless have eight different appearances:

From diagram (a), (b) is formed by a half-turn, or 180° rotation, (c) and (d) by reflection in the horizontal and vertical medians, (e) and (f) by a quarter turn, or 90° rotation, clockwise and anticlockwise respectively, (g) and (h) by reflection in the principal and secondary diagonals.

In the case of a symmetric pattern some of the diagrams will look the same. If all eight diagrams are the same we call the symmetry octonary since lines through the centre will divide such a pattern into eight congruent components. If the diagrams occur in two sets of four alike the symmetry is quaternary and lines can be drawn through the centre to divide the pattern into four congruent components. If the diagrams occur in pairs alike the symmetry is binary and the pattern can be divided into two congruent components. If all eight diagrams are different, as in the example above, the pattern can be called unary, since it is formed of one component, but the more usual term is asymmetric.

Instead of measuring the amount of symmetry in a pattern by counting the number n of congruent components we could use d = log2 n (i.e. n = 2^d) which is the degree of symmetry. Patterns with degrees of symmetry 0, 1, 2 and 3 may then be referred to as nully, singly (or simply), doubly and triply symmetric, corresponding to unary, binary, quaternary and octonary. (Terminology like this was used by Archibald Sharp Linaludo 1925.) In cases where n is not a power of 2, d becomes fractional. For example when n = 3, as in an equilateral triangle, then d = 1.585 approximately.

Reflective and Rotative Symmetry

A line in which a pattern may be reflected without alteration is called an axis of symmetry (plural axes). Axes on rectangular boards must either be lateral, through cell centres (odd side) or along the sides of cells (even side), or when the rectangle is a square the axis can be diagonal. A point about which a pattern may be rotated (other than a multiple of 360°) without alteration is called a centre of symmetry; if one exists it is unique. Centres of symmetry of rectangular boards are either at the centre of a cell (odd×odd boards), at the corner of a cell (even×even boards) or at the mid-point of a side of a cell (odd×even boards). A pattern can have both an axis and a centre of symmetry; in fact any pattern that has two axes is necessarily symmetric by rotation about the point of intersection of the axes, the minimum angle of rotation being twice that between the two axes.

Following Bergholt (1917) we call a pattern direct if it has at least one axis of symmetry and oblique if it has a centre of symmetry but no axis of symmetry. These two classes of symmetry are thus mutually exclusive.

In the case of patterns of knight moves on square boards eight types of symmetry can be distinguished as illustrated here. On rectangular boards we call lines parallel to the edges lateral (in preference to orthogonal used by Murray and others), lines at 45 degrees to the edges diagonal, and other lines skew. In direct symmetries the axes can be lateral or diagonal. The octonary symmetry is necessarily direct, since oblique octonary symmetry requires a 45° rotation and the lattice of squares is not invariant to 45° rotation.

Patterns of knight moves, considered apart from the board on which they are drawn, can have skew axes. This can be termed intrinsic symmetry. For example a single knight move has direct quaternary symmetry, but the cells it links form a pattern that does not reflect in the skew axes (the line of the move itself, and its perpendicular bisector), so the knight move and board together do not have this symmetry.

Alternative Terminology

The terms used to describe symmetry vary widely, even among mathematicians. Some common alternative terms are listed here. Bergholt's terms ‘direct’ and ‘oblique’, adopted by Murray, and which I find useful, are not universally approved. For example, direct is used by H. S. M. Coxeter, Introduction to Geometry (1969), to describe any transformation that does not alter the direction of description of curves (i.e. rotations and translations, as opposed to reflections) which is the opposite of Bergholt's sense, and oblique has a long-established dictionary sense of ‘non-lateral’ (i.e. diagonal or skew). On the other hand, the alternative axial or axi- symmetry is sometimes taken to imply exactly one axis rather than at least one axis, and central or centro- symmetry strictly means having a centre, which does not exclude also having an axis, while rotary or rotational symmetry means unchanged by rotation which does not exclude also being unchanged by reflection.
Binary direct symmetry is sometimes called bilateral symmetry, though this may exclude the case with a diagonal axis. Another term for this type is monaxial (Sharp 1925) since it has only one axis.
Binary oblique symmetry, is often called diametral (Jaenisch 1862) referring to the fact that corresponding cells are diametrically opposite, i.e. on the same line through the centre of symmetry. This type can also be described as 180° rotational or monorotary or perhaps spiral symmetry.

There is (or has been) a tendency for direct symmetry to be regarded as ‘true’ symmetry and oblique symmetry as pseudosymmetry (a term used by T. R. Dawson in the 1940s, though in crystallography it has a different meaning). For example, when Ernest Bergholt published some knight's tours with binary oblique symmetry in Queen in 1915 (confusingly calling it ‘bilateral’) he wrote in the following issue (1 January 1916):

Mr Henry E. Dudeney, who is a great authority on puzzles, but by no means an authority on the meaning and use of words ... writes: ‘I cannot agree with you that your bilateral symmetry is symmetrical at all. Symmetry is a matter for the eye; this is a sort of intellectual symmetry.’ It would appear that Mr Dudeney's eye is differently constituted from the eye of the ordinary person. To me, indeed, these tours convey a most pleasingly symmetrical effect, and I have little doubt that the vast majority of my readers will take equal delight in contemplating them. To Mr Dudeney, Hogarth's well-known line of beauty would be quite devoid of symmetry; he would admit that a capital X might be drawn symmetrically, but not a capital S. Such are the eccentricities of genius.

The reference is to the painter William Hogarth's book The Analysis of Beauty (1753) in which he argued that the eye should be led along a serpentine ‘line of beauty’, though how serpentine it could be was not clear.

Quaternary direct symmetry is described more briefly as biaxial symmetry since it has two axes crossing at right angles.
Quaternary oblique symmetry can be described as 90° rotational or birotary symmetry, and might also be called, more graphically, swastika or windmill symmetry.
Octonary symmetry, although a systematic term along with binary and quaternary, is more often called square or perfect square symmetry, since a square has this type of symmetry, though patterns with this symmetry often bear very little resemblance to a square.

Symmetry in Open Knight Paths

A pattern formed by an open knight path on a rectangular board can exhibit the first four of the above types of symmetry: asymmetric, binary oblique, binary lateral or binary diagonal.
— For oblique symmetry the mid-point of the path must be at the centre point of the board. Two cases can be distinguished: (a) The centre of the board is the mid-point of the edge of a cell, and the mid-point of the middle move of the path. The path therefore has an odd number of moves (even number of cells) and uses a board of odd×even dimensions. (b) The centre of the board is the centre of a cell, and the two middle moves of the path meet there, making a two-move straight line. The path therefore has an even number of moves (odd number of cells) and uses a board odd×odd.
— For direct symmetry the mid-point of the path must lie on the axis, i.e. on a lateral or diagonal line through the board centre. Since a knight move is always skew it cannot cross a lateral or diagonal axis at right angles, so a knight path in direct symmetry must have an even number of moves (odd number of cells), the mid-point of the path being the centre of a cell on the axis. There are two cases: (c) lateral axis, board odd×any, (d) diagonal axis, board square. Only case (d) can occur on a board even×even.

Numbering of symmetric open paths: If the cells in an open path are numbered 1 to E then the numbers in the end cells add to E + 1, and in the case of a symmetric open path the numbers in any pair of cells related by the rotation or reflection (i.e. cells x moves from one end, numbered x + 1, and x moves from the other end, numbered Ex) also add to the constant value E + 1. When the number of cells E is odd (or the number of moves E – 1 is even) there is a middle cell in the path, and the number on it is (E + 1)/2, which is the average of all the numbers 1 to E.

Symmetry in Closed Knight Paths

All eight of the types of symmetry (1 – 8) listed above can occur in patterns formed by closed knight paths on rectangular boards. If A and A' are a pair of corresponding cells in a closed path with binary symmetry then the closed path consists of two joined open paths A—A'. For binary symmetry these two paths must either be congruent, one being the rotation or reflection of the other (we call this positive symmetry), or each must itself be symmetric, with the same type of symmetry (we call this negative symmetry). If B and B' are another pair of corresponding cells then in the positive case the points occur in the cyclic sequence ABAB... along the path, but in the negative case in the sequence ABBA... (or AABB... which is the same).

We thus have four types of binary symmetry in closed paths. Namely: positive oblique = Eulerian, negative oblique = Bergholtian, positive direct = Sulian and negative direct = Murraian, so-called since examples were shown by Euler, Bergholt, Suli and Murray.

These can be further subclassified according to whether the number of moves in the connecting paths A—A' are even or odd, or equivalently, whether the centre is on a cell corner, centre or edge or whether the axis is through cell centres or edges. Eulerian and Sulian paths can be even or odd, but Bergholtian must be odd and Murraian must be even.

Numbering of symmetric closed paths: If we number the cells of a closed path 1, 2, ..., E (beginning at any cell and proceeding in either of the two directions) and the cell corresponding to cell a under binary symmetry is the cell numbered a' then the cell corresponding to a + 1 will be either a' + 1 or a' – 1. These correspond to the cases of positive and negative symmetry defined geometrically above. In the positive case numbers in corresponding cells have constant difference a' – a, while in the negative case they have constant sum a' + a. In the positive case we always have |a' – a| = E/2 throughout. In the negative case, when the move 1 to E passes through the centre we have a' + a = E + 1 throughout, but if the origin of numbering is differently placed there will be two different values for the constant a' + a along different sections of the tour.

In cases of quaternary and octonary symmetry the paths A—A' (where A' is the cell related to A by 180° rotation) will be congruent and formed of two congruent parts. Quaternary paths with lateral axes can be either Eulerian or Bergholtian, but all those with diagonal axes or oblique can only be Eulerian and square. The simplest examples are shown:

Symmetry in Rectangular Tours

The arguments in the following theorems were sketched in my article in Chessics 22 (1985) but are given here in more detail.

Theorem 1. An open knight's tour of a rectangular board can only have oblique binary symmetry, and at least one side of the board must be odd.

Proof: (a) For reflective symmetry of an open path with an odd number of moves the middle move would have to cross the lateral or diagonal axis at right angles, which is impossible for a knight's move, which is skew. (b) For reflective symmetry of an open path with an even number of moves the mid-point of the path must be the centre of a cell on the axis. The path cannot enter any other cell on the axis since the other half of the path would by symmetry also enter the same cell, thus making a closed path. For the path to be a tour all cells on the axis must be entered; thus there can only be one cell on the axis, so the board must be 1×n, but no knight moves are possible on such a board. (c) For rotative symmetry of an open path the mid-point of the tour must be either the end-point or the mid-point of a knight's move, i.e. a cell centre (even number of moves) or the mid-point of the side of a cell (odd number of moves). Thus the board cannot be even×even, since at the centre of such a board the corners of four cells meet, so the board must have at least one side odd. (d) The rotative symmetry cannot be quaternary since that would require four end-points.

Theorem 2. A rectangular closed knight's tour requires a board with at least one side even.

Proof: On a chequered board each move is to a different colour, so an even number of moves is needed to bring the knight back to the cell on which it started; and this number of moves is also the number of cells, one as the destination of each move. So at least one side of the board must be even, since on an odd×odd board the number of cells is odd.

Theorem 3. A rectangular closed knight's tour with direct symmetry requires a board with one side odd and the other singly-even, and cannot show quaternary symmetry.

Proof: (a) If A and A' are corresponding cells, not on an axis of symmetry, in a tour with reflective symmetry, then it consists of two paths A-A'. (b) The two paths cannot be themselves symmetric, with their mid-points on the axis, since there would then only be two cells on the axis and the board would be 2×n on which no knight's tours are possible. In other words the symmetry must be Sulian and not Murraian. (c) The two paths A-A' must be reflections of each other in the axis and there must be no cells on the axis. The axes are therefore lateral, not diagonal, and the cells A and A', being equidistant from the axis and on opposite sides of it, must be of opposite colour when chequered. (d) The paths A-A', connecting cells of opposite colour, are therefore of an odd number of moves. The tour therefore occupies twice an odd number of cells. The board must therefore be odd×singly even, i.e. (2m+1)×2(2n+1), that is (2m+1)×(4n+2). The axis is the bisector of the even side. (e) It follows that direct quaternary symmetry is impossible in a rectangular knight's tour since the side parallel to an axis must be odd and the side perpendicular to it even, and if this is true for one axis it cannot be true for the perpendicular axis.

Theorem 4. A symmetric rectangular closed tour on a board even×even can only be Eulerian, while on a board with one side a multiple of four and the other odd it can only be Bergholtian. On a board singly-even×odd all three types, Sulian, Eulerian and Bergholtian may be possible.

Proof: (a) As proved above direct symmetry requires singly-even×odd and so is impossible on both types of board mentioned. (b) Bergholtian symmetry requires a board odd×even since the centre point must be the mid-point of a knight's move and therefore the mid-point of the side of a cell, so on the even×even board only Eulerian symmetry remains (it can be binary or quaternary). In Eulerian symmetry on an odd×even board the corresponding cells A and A' (on a line bisected by the centre point of the board) are of opposite colour, so the number of moves in A-A' is odd and the number of moves in the tour is twice this, i.e. singly even. Therefore if the even side is not singly-even, i.e. if it is a multiple of 4, only Bergholtian symmetry remains feasible.

Theorem 5. A rectangular closed knight's tour with oblique quaternary symmetry requires a square board with singly-even side.

Proof: Such a tour consists of four equal paths, the board must be square, for the 90° rotations to leave it invariant, and even-sided, for closure. On an even-sided square the 90° rotation of a cell is of opposite colour to the original cell, and so the path joining them is of an odd number of moves. The whole tour is thus 4 times an odd number of moves, i.e. it contains 2 as a factor only twice. The square boards on which quaternary tours are possible therefore have side: 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50 and so on.

Coding Methods for Symmetry

Historical Schemes

For purposes of studying symmetry various authors, in particular de Hijo (1882) and Bergholt (1918) proposed the adoption of methods of numbering the cells of the particular board being considered in a manner related to the symmetry under consideration. The numbering employed by de Hijo for his listings of circuits in oblique quaternary symmetry is shown. For direct quaternary symmetry his numbering in the second and fourth quarters reflects that in the first instead of being a rotation of it. Bergholt used a similar scheme but using only the odd numbers, so arranged that successive odd numbers are connected by knight moves. For binary symmetry he replaced the numbers in the second and fourth quadrants by the corresponding even numbers.

On a square board of side 2k or 2k + 1 there are k(k + 1)/2 ‘differently placed’ squares. This is the kth triangular number, 1 + 2 + ... + k, and is the number of cells within or on the edges of the 8 triangles formed by the diagonal and lateral axes of symmetry of the square. By rotation or reflection of the board any cell in one triangle can be brought to coincide with a similarly placed cell in any of the other triangles. In the case of the 8×8 board there are ten differently placed cells, and for purposes of studying symmetry it is convenient to label them with the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Murray (1942) used the arrangement shown in the third diagram above in which the diagonal cells are numbered inwards 0, 1, 2, 3 and the other cells are numbered 4, 5, 6, 7, 8, 9 row by row. This method of numbering has the disadvantage that sequences of cells that indicate moves on smaller boards do not also indicate similar moves on larger boards. To apply his method to quaternary symmetries Murray marked the numbers below the diagonal in the first quarter with primes, and also the numbers in the corresponding cells, related by rotation or reflection as appropriate.

Centrifugal Numbering

In the alternative scheme proposed here, which I call centrifugal, and which is applicable to odd and even boards of any sizes, the numbering is row by row from the centre cell or cells outwards, beginning with 0. The numbers in the cells laterally outwards from the centre are the succcessive triangular numbers (n–1)n/2, i.e. the sequence 0, 1, 3, 6, 10, 15 ... and the numbers in the cells diagonally out from the centre are one less than the triangular numbers, i.e. the sequence 0, 2, 5, 9, 14, ....

This scheme has the advantage that any sequence of numbers that represents a path of knight moves on a small square board also represents a path of knight moves on any larger square board of the same parity. For example on any odd square board the eight moves 1–2 form a circuit round the centre cell, while on an even square board the eight moves 1–1 and the eight moves 2–0 form the two squares and two diamonds in the central 4×4 area. I find that it is not really necessary to mark the numbers with primes to distinguish the two cases; it is sufficient to note that the diagonal cell numbers are used once and the others twice, and that the two occurrences of each off-diagonal number must have a diagonal number somewhere between them.

Table of possible moves: Using the centre-outwards coding the possible knight moves on the 8×8 board are:
0 ® 1², 2², 3², 4²
1 ® 0, 1², 3, 4, 5, 6, 7
2 ® 0², 3², 6², 8²
3 ® 0, 1, 2, 4, 7, 8
4 ® 0, 1, 3, 6, 7, 9
5 ® 1², 6²
6 ® 1, 2, 4, 5
7 ® 1, 3, 4, 8
8 ® 2, 3, 7
9 ®
where ² indicates a choice of two moves to cells with the same number.

A pair of numbers in most cases indicates a single unambiguous move from any of the cells with the first number. Ambiguity occurs only in the case of the diagonal cells 0, 2, 5, 9 and the special moves 1-1 which form four-move circuits round the centre. In paths and tours sequences of the form xyx are possible only when y is a diagonal cell (e.g. 494 through the corner cell of the 8×8 board): if y is not a diagonal cell xyx (e.g. 949) represents a ‘switchback’, using the same cell x twice, which by definition is not allowed in a tour.

On the 7×7 and larger odd boards the cells numbered 4 and 7 have the peculiarity of defining 16 knight's moves instead of 8. To distinguish the two cases we write 4;7 for the move across a diagonal and 4:7 for the move across a median. Thus where 4.7 occurs there are two cases, 4;7 and 4:7 which, though represented by the same formula, are often strikingly different.

Central Angle Formations

The formation of a pattern in the central area of an even-sided board, to present the effect of a ‘picture’ within a frame is a common scheme for tours. The coding scheme described above can be employed to name the 16 different ways in which a pair of moves may pass through a central cell on an even-sided square board. Moves of type a0a are symmetric about a diagonal through the centre cell used. On the 8×8 board angle 404 cannot occur in a closed tour since it forms a circuit with the pair of moves through the nearest corner. On the 6×6 board the angle 101 cannot occur for the same reason. On larger boards either can be used. The four angles 101, 202, 303, 404, correspond to four octonary patterns that can be made with four equal angles. A pair of the angles 202 cannot occur in a centrosymmetric tour since diametral pairs of them form a diamond circuit.

Moves of type a0b can be taken from one given 'a' to two different 'b's. We take a0b (underlined) and a0b (plain), to represent the moves which keep to one side of or cross the diagonal respectively. For example 102 is an acute angle with lateral bisector, while 102 is a right angle.

The following are charts of all the central patterns that can occur with four equal angles. In each case quaternary oblique, quaternary direct, binary direct and asymmetric formations are possible.

Diagrams of the quaternary cases were given by Paul de Hijo (1882).

Most of the above notes first appeared in The Games and Puzzles Journal, issue 16 (1999).

Back to top