King Tours

© by George Jelliss (April 2011)
Queen paths moved to Rider Tours section November 2012

Sections on this page: — Knots and InterlacingsKing ToursAlternating King ToursMagic King Tours


Knots and Interlacings

A version of this article appeared in The Games and Puzzles Journal #15, 1997, pp.249, 262-3.


Celtic Art

One of the main characteristics of 'Celtic Art' during its later period is the use of interlace patterns depicting a ribbon passing alternately over and under itself. No doubt such patterns derived originally from depictions of real interlacings, as in the plaiting of hair, rope-making (where several strands are woven together to give greater strength), lace fastenings for boots, leggings or coats, or in the passes and stitches used in weaving, tapestry and embroidery.

Many interlacings can be represented graphically by a path of king moves on a lattice of squares, the cross-overs being made by diagonal moves of the king, though this does not necessarily imply that they were designed this way. Diagrams follow of several examples in which these underlying king paths are in fact tours or pseudotours. It may be noted that these king tours avoid sharp turns (of 45°) since this would result in small interstitial areas, not allowing room for the definite width of the ribbon.

These are found in books and artefacts produced in monasteries of Ireland, Scotland and Northern England. We consider them here in order of increasing complexity, not necessarily chronologically.

The cover of "A strange object known as the soiscél Molaise … made around year 1000 as a cumdach or book-shrine for the Gospel of St Molaise, using pieces of a house-shaped shrine of the early eighth century" [Laing] uses various interlacing patterns to fill gaps in the design. Among these are patterns that may be represented by king paths on 2×6, 6×6 and 6×14 boards. Obviously the first is a simple plait. The second is a 'prime knot' in the modern topological theory of knots. The third is a pseudotour, consisting of two linked circuits.

Similar but more elaborate designs are used in the upper and lower borders on a page illustrating an Eagle symbol in the Book of Dimma, late 8th century, and in the left and right borders on the Lion symbol page of the Book of Durrow of the mid 7th century. These can be simplified to pseudotours 4×28 and 4×34, which may have been the basis for the designs.

A nearly square king tour underlies the design of a panel from the Saint Madoes stone, Perthshire.

This is a 20×24 king tour, which can be formed by 'doubling' a simpler king tour 10×12 and altering some links to turn the pseudotour into a true tour.

The 'binding knot' from the Book of Kells, late 8th or early 9th century is possibly the most elaborate of these designs. [For full reproductions of the Book of Kells knot see Pennick (1990, p.45) and Bain (1951, p.46). By redrawing the design on squared paper, I found that this knot becomes two circuits of king moves, on a board in the shape of a quadrate cross (formed of thirteen 8×8 squares).

The following quotation from Alcuin (735-804) is perhaps what the design illustrates: "the four rivers of the virtues flowing out of one bright and health-giving paradise, irrigating the whole breadth of the christian church". Examination of the knot shows that the two threads of which it is constructed follow each other in parallel throughout, thus the pair of threads define a single path. Replacing the two king paths by one line midway between them results in a single king tour of a quadrate cross formed of thirteen 4×4 squares, as shown in the smaller diagram. This cross tour explains why the threads come to a point at the four cardinal points instead of just curving round: they correspond to the corners of the square part of the quadrate cross. It seems evident to me that in this case at least the king tour was consciously the basis of the design of the Kells knot.

[References: George Bain Celtic Art: The Methods of Construction, 1951, p.46. Nigel Pennick, 1990. Lloyd and Jennifer Laing, Art of the Celts, 1992, pp. 142, 146, 174, 181 (quote from Alcuin).]


Change Ringing

Another context in which interlacings like king tours can be seen is that of change-ringing. This is a method of ringing four or more bells, each tuned to a different pitch, so that a different sequence of notes is followed each time the full set of bells is rung. The simplest pattern in which four bells can be played, known as 'plain bob minimus', is shown in the diagram. The highest pitched bell 1 'hunts' through the other bells to the back, stays there one more change, then hunts forward again to the front. Eight different sequences are thereby rung. (Joining 1-2 and 3-4 in the final column and 2-3 in the first column gives a king tour.)

More elaborate change-ringing schemes were designed by Fabian Stedman (b. 1631) who wrote two books, Tintinnologia and Campanologia. [Reference: M. Darton and J. Clark, The Dent Dictionary of Measurement, 1994, pp. 67-8.]


Prime Knots

A 'knot' in mathematical terms is a closed curve in three-dimensional space. If one knot can be deformed so that it is congruent to another without passing through itself anywhere, the two knots are of the same type. In particular a knot that can be simplified into a circle is a 'trivial knot' (or an 'unknot'). It is by no means always obvious that a given knot is an unknot, as example (A) shows. I show the knots as king paths, with the intersections arranged diagonally, the heavy line passing over the lighter line. Presenting the knots in this formalised way may perhaps give clues to classifying them or analysing their structure. They are not all complete tours.

A 'compound' knot is one formed from two knots by deleting a small part of each knot and joining the ends in such a way that the joining lines do not cross each other or any parts of the existing knots. A 'prime' knot is one that is not formed by joining two knots in this way. A knot can be classified by the minimum number of crossovers in a representation of it. The numbers of prime knots P(n) of 0 to 13 crossings are: P(0) = 1, P(1) = 0, P(2) = 0, P(3) = 1, P(4) = 1, P(5) = 2, P(6) = 3, P(7) = 7: These cases are illustrated above. [The series continues: P(8) = 21, P(9) = 49, P(10) = 165, P(11) = 552, P(12) = 2176, P(13) = 9988. The totals do not count reflected knots as different. P(11) is due to Alain Caudron 1978, P(12) and P(13) to Morwen Thistlethwaite, 1981 and 1982. Reference: Colin C. Adams The Knot Book subtitled An Elementary Introduction to the Mathematical Theory of Knots (W. H. Freeman and Co, New York, 1994), pp.24, 281.]


King Tours

Since the king, a {0, 1} + {1, 1} mover, can make wazir moves, all wazir tours are also king tours. A conscious study of king tours does not seem to have begun until the early years of the twentieth century. In Chess Amateur in 1908, T. H. Neal published some enumeration results for king tours on two ranks of the chessboard, showing that the numbers were related to the Fibonacci series. T. R. Dawson enumerated king tours of the 3×3 board, open and closed, in British Chess Magazine, January 1949. The following, as far as I am aware, is the first thorough treatment of these enumeration problems in print.


Board 2×n

Closed Tours: On the 2×n board (n > 2) the link between two adjacent files in a diagram of a king's closed tour is either a pair of lengthwise moves (=) or a pair of diagonal moves (×}; two choices in each of n−1 cases, hence the total number of oriented tour diagrams is T(n) = 2^(n−1). This formula breaks down for n = 2 since the board is then square and there is an extra diagram because the bow-tie shaped tour can be rotated to figure-of-eight shape.

All these tours are symmetrical about the horizontal axis. Under H(n) we count those that are symmetric about the vertical axis also (shown by heavier lines in the diagrams above). We have two choices at each pair of files in one half, and in the centre pair when n is even, so the number of these biaxial tours is H(n) = 2^h, where h is n/2 when n is even, (n−1)/2 when n is odd. The total T is made up of 1 from each biaxial tour, 2 from each axial tour, so the number of geometrically distinct tours, for n > 2, is G = H + A/2 = H + (T − H)/2 = (T + H)/2 = 2^(n−2) + 2^(h−1).

Table of results:

        n = 2 3  4  5   6   7   8    9   10   11    12
        T = 3 4  8 16  32  64 128  256  512 1024  2048
        h = 1 1  2  2   3   3   4    4    5    5     6
        H = 2 2  4  4   8   8  16   16   32   32    64
        A = 0 1  2  6  12  28  56  120  240  496   992
        G = 2 3  6 10  20  36  72  136  272  528  1056
        R = 3 8 22 48 116 256 584 1280 2832 6144 13344

Open Tours: The last line of the table above counts the number of geometrically distinct reentrant tours, that is open tours where the ends are a king move apart. Since each 2×n closed king tour is symmetric about the horizontal axis we can derive only n+1 geometrically distinct reentrant tours from an axial tour by deleting a move: n−1 from the (=) or (×) moves and 2 from the end moves, while from a biaxial tour we can derive h+1. So the number of geometrically distinct reentrant tours is R = (n+1)A + (h+1)H, though n=2 is again an exceptional case.

The following diagrams list all the geometrically different open tours for n = 1 to 4:

and the 2×5 open tours, in smaller scale, classified by separation of end points:

We now look at recursion relations and formulae to calculate the numbers of open tours for longer boards. An open king tour with both ends in the same file is only possible if the file is an end-file of the board and, since joining the ends produces a closed tour, the number of such tours on a board 2×n is the same as the number of closed tours, 2^(n−1).

Any 2×n open king tour with ends on files p and q (p < q) consists (except when p = 1 or q = n) of reentrant tours of the end sections (with both their terminals on the p and q files) joined by an end-to-end tour of the middle section (with terminals on the p+1 and q−1 files). The reentrant sections total 2^(p−1) and 2^(n−q), from the formula for closed tours.

To complete the enumeration we need to know the number L(n) of tour-diagrams on a 2×n board, with one end at the top of the first file and the other end in the last file. The sequence L(n) has the initial values L(1) = 1 and L(2) = 4 and obeys the recurrence relation L(n) = 2L(n−1) + 4 L(n−2), since the initial section can be either of the two forms (a) or (b), derived from a tour of length n−1, or any of the four forms (c), ..., (f), derived from a tour of length n−2.

It is possible to express L(n) in terms of the Fibonacci numbers as L(n) = 2^(n−1).F(n+1), where F(1) = F(2) = 1 and F(n) = F(n−1) + F(n−2), giving the familiar series 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

Half of these L-type diagrams end at the top right and half at the bottom right, but when counted geometrically it appears that the numbers are equal in the even cases but differ in the odd cases since the number of symmetric tours are different, e.g. in case 3 there are 6 diagrams in each class, but the first consists of 3 asymmetric tours, the second of 2 symmetric and 2 asymmetric (2×3 = 6 and 2 + 2×2 = 6); and in case 5 there are 64 diagrams in each class, 32 asymmetric in the first class, 8 symmetric plus 28 asymmetric in the second class (2×32 = 64 and 8 + 2×28 = 64).

The number of king open tours from a given corner of a 2×n board, K(n), follows the similar recurrence: K(1) = 1, K(2) = 6 and K(n) = 2^(n−1) + 2K(n−1) + 4K(n−2), since diagrams (a) to (f) still apply, the additional term being the number of reentrant tours with both ends in the initial file. From this recurrence we calculate K(3) = 20, K(4) = 72, K(5) = 240, agreeing with the totals found by construction. This is also solved in Fibonacci numbers as: K(n) = 2^n.F(n+1) − 2^(n−1), a formula given by T. H. Neal (1908).

We can now determine the number of geometrically distinct symmetric tours. For axial tours: the number with horizontal axis for n>2 is 2^(n−1) to which must be added K(n/2) + 2K((n−2)/2) with vertical axis when n is even. For rotary tours: 2K((n−1)/2) when n is odd, K(n/2) + 2K((n−2)/2) when n is even. So the total of symmetric tours is S = A + Z.

The open tours with one end at the top of the pth file (p not 1 or n) consist of either a reentrant tour of the files p to n, followed by a tour from a corner of the files p−1 to 1, or a reentrant tour of the files p to 1 and a tour from a corner of the files p+1 to n. Denoting the total by K(p,n) we have, from the above results: K(p,n) = 2^(n−p).2.K(p−1) + 2^(p−1).2.K(n−p), where the K-value is doubled since there are two possible links from the reentrant section to the other part. This simplifies, in another formula due to T. H. Neal (1908), to: K(p,n) = 2^n.[F(p) + F(n+1−p) − 1]. Of course K(1,n) = K(n,n) = K(n) and K(p,n) = K(n+1−p,n).

We can now calculate the total number of 2×n king open tours, T(n), by summing the K(1,n) from 1 to n, with the help of the Fibonacci property that the sum of F(m) over m from 1 to n is F(n+2) − 1. This gives T(n) = 2^n.[4F(n+1) − (n+3)]. The number of geometrically distinct tours can then be calculated for each n (>2) by G = (T + 2S)/4.

Table of results for open tours:

         n = 1  2  3   4   5    6    7     8      9 
         F = 1  1  2   3   5    8   13    21     34 
         L = 1  4 12  40 128  416 1344  4352  14080 
         K = 1  6 20  72 240  800 2624  8576  27904 
         A = 0  2  4  16  16   64   64   240    256 
         Z = 0  1  2   8  12   32   40   112    144 
         S = 1  3  6  24  28   96  104   352    400 
         T = 1 12 48 208 768 2752 9472 32000 106496 
         G = 1  3 15  64 206  736 2420  8176  26824 

Here F = Fibonacci numbers, L = Tour diagrams from given corner to board end, K = Tour diagrams from given corner, A = axial, Z = rotary, S = symmetric, T = Total of tour diagrams and G = geometrically distinct. The figures in the first five columns of the table have been enumerated by construction as above, the other figures have been calculated from the recursions or formulae, but have not been independently checked.


Boards 3×n

.

The 3×3 tours, open and closed, were enumerated by T. R. Dawson (1949). There are 2 closed tours 3×3; one polygonal, the other with one self-intersection.

On the 3×3 board Dawson reported 51 geometrically distinct open king tours (3 of wazir type), of which 4 are symmetric (1 of wazir type) and 18 are reentrant (1 of wazir type: the reentering move being a non-wazir move).

On the 3×4 board I find 37 closed king tours; 13 polygonal, 16 with one intersection, 7 with two intersections, and 1 with three intersections. Of these 14 are symmetric; 5 centrally and 9 (including the wazir tour) axially.

The closed 3×4 tours give rise to 366 reentrant open tours, so the full number of open tours is likely to be very large, but among these there are 40 with axial symmetry: 14 reentrant, derived from the seven axially symmetric closed tours, including the wazir case, that cross the axis twice at right angles. Of the 26 others, 23 differ from 4×4 closed tours only by omission of a straight base line, the 3 other cases are shown.


Boards 4×n

.

On the 4×4 board I find 368 closed king tours, of which 63, shown here, are symmetric.


Alternating King Tours

The Kashmir poet Rudrata (c.900ad) gave an 'elephant' tour of a two-rank board in the form of a saw-tooth pattern of alternating wazir and fers moves, and as-Suli, working about the same time but in Baghdad, gave complete 8×8 tours of alternating moves of knight with fers and alfil but surprisingly, considering that the alternating wazir-fers tour is a type of king tour, no further example seems to have appeared until my quaternary example (found in the 1970s) was published in Chessics #18, 1984. Clive Grimstone, working independently sent me 20 examples on the 8×8 board at about the same time (30 April 1983), calling them 'ant' tours.

Theorem: A closed alternating king tour requires a board even by even, and the fers moves must form a fixed arrangement of crosses in the 2×2 blocks.

Proof: At the corner a1 the only fers move is a1-b2. At c1 the only fers move now available is c1-d2, since c1-b2 would give two successive fers moves. Similarly e1-f2 is forced. Continuing along the first rank we conclude that it must contain an even number of cells, since each fers move uses two files. A similar construction from the last cell back to a1 produces a pattern of n/2 crosses along the first two ranks. Now apply the same argument to the third rank. No fers moves are possible from rank 3 to rank 2 since all cells in rank 2 have fers moves assigned. So again we get the pattern of crosses. And the same for all other pairs of ranks.

There is one alternating king tour on any board 2×2.h and it has biaxial symmetry. On four-rank boards I find 1 tour 4×4, 3 tours 4×6, 6 tours 4×8. On the 6×6 board I find 5 solutions, all with diferent types of symmetry, including the first asymmetric example. I also have a note of 39 tours 6×8, not checked (4 biaxial, 9 with short axis, 3 with long axis, 4 centrosymmetric, and 19 asymmetric).

Observation: In closed tours, the moves along one pair of opposite edges must consist of fers-wazir-fers triangles. In the square diagrams below these are taken to be the vertical edges. This property is not true in open tours, as the examples show.

On the 8×8 there are over a hundred tours, but there are only 6 with biaxial symmetry. The first is the first one I found and published in Chessics (1984). The last three shown here were among those by Clive Grimstone.


Magic King Tours

There are very simple magic king tours on rectangular boards 2×2n. The columns consist of pairs of complements, adding to 4n+1, the first and last entries, 1 and 4n, being in the first column, and the middle entries, 2n and 2n+1, in the last column.

These tours were diagrammed in Chessics #26 p.117 and #30 p.163, but similar diagrams have long appeared in books on magic squares.


Diagonally Magic 8×8 King Tours

This diagonally magic king's tour on the 8×8 board appeared in Matematica Dilettevole e Curiosa by Ing. Italo Ghersi (published by Ulrico Hoepli, Milan, Italy, 2nd edition, 1921, p.320, figures 261 and 265). It has a single axis of symmetry. We show it here in both arithmetical and geometrical forms. The dark links are where the quarters join (16-17, 32-33, 48-49):

Many other magic king tours are undoubtedly possible on the 8×8 board. However most attention has been given to diagonally magic king tours with biaxial symmetry, which we now turn to.


Diagonally Magic 8×8 King Tours with Biaxial Symmetry

We give a catalogue here of all known examples. Thanks to work done by T. W. Marlow in July 1995 (reported in The Games and Puzzles Journal, issue 15, p264, December 1997) this is now believed to be the complete list for this type. They are classified here according to the numbers in the diagonals and the positioning of the end-cells of the quarters, where the numbers 1, 16, 17 32, 33, 48, 49, 64 occur.

A-cases. The first of the A-group was given by W. W. Rouse Ball in Mathematical Recreations and Essays, 7th edition, 1917, p133 [information from T. H. Willcocks]. The others are formed from it by interchanges of non-diagonal elements, as was indicated by M. B. Lehmann in Neue Mathematische Spiele: Der Geometrische Aufbau Gleichsummiger Zahlenfiguren, 1932, pp.360-362. The diagonal with the smallest number in it is: 4, 54, 55, 49, 17, 23, 22, 36. To find the entries in the other diagonal subtract from 65. Many other biaxially symmetric magic tours can be formed by slight variation, for instance by transposing 16-17 and 48-49 in A1, but these changes result in the diagonals no longer being magic.

B, C, D cases. The first B case is due to J.Brügge, Die Schwalbe, August 1985, pp505-509, and from this I derived the other, the diagonal is: 4, 51, 52, 55, 23, 20, 19, 36. This and the C and D cases were given by me in Chessics #26, Summer 1986, p.120. The diagonal in C is: 45, 4, 25, 24, 56, 57, 36, 13, and in D: 5, 54, 55, 48, 16, 23, 22, 37.

The E, F and G cases are due to Tom Marlow, as reported in The Games and Puzzles Journal, issue 15, p.264, December 1997. The diagonal in E is the same as for the D cases. The F diagonal is: 60, 12, 57, 1, 33, 25, 44, 28.

The G diagonal is: 60, 58, 11, 1, 33, 43, 26, 28. I keep to the numbering used in G&PJournal, though the diagrams are differently arranged; the cases with the join in the edge being shown first.

The next diagram shows a diagonally magic king tour on a 16×16 board (G.P.Jelliss Chessics #26, p.120, 1986). It is derived from the A1 tour.


Back to top