[Revised March 2018]
This page is devoted to explaining methods of construction of magic knight's tours on boards of any size. There are separate pages on the historical development, and on the results achieved on particular boards.
By a magic rectangle we mean a numbering 1, 2, ..., rs of the cells of a rectangular board of r ranks and s files in such a way that the rank sums are all the same and the file sums are all the same. The average value of the rs numbers is A = (rs + 1)/2, that is half the sum of the first and last numbers. The rank-sum is R = sA = s(rs + 1)/2, since there are s cells in a rank, and the file sum is S = rA = r(rs+1)/2, since there are r cells in a file. These are called the magic constants for the r×s board. In the case of a square board r = s and so R = S = r(r^2 + 1)/2.
Theorem 1: A magic rectangle is impossible on a board odd by even.
If rs is even then rs + 1 is odd, and so for the rank sum s(rs + 1)/2 to be a whole number s must
be even, and similarly for the file sum r(rs + 1)/2 to be a whole number r must be even.
On the other hand, if rs is odd then both r and s must be odd by simple arithmetic.
By a magic knight's tour (in arithmetical form) we mean a magic rectangle in which the numbers 1, 2, ..., rs follow the path of a knight. We also apply the term ‘magic knight's tour’ (in geometrical form) to the pattern formed by the moves. One magic knight's tour in geometrical form can correspond to two or more of arithmetical type depending on where the numbering is started and in which direction it proceeds.
Theorem 2: A magic knight's tour is only possible on a board with both sides even.
Chequering the cells of the board white and black, it is a property of the knight that it always moves
to a cell of different colour to that on which it stands. All the cells of one colour will be odd numbered
and all the other cells even numbered. In a board with an odd number of files, adjacent ranks contain an odd
and an even number of odd-numbered cells. The rank sums would therefore be alternately odd and even.
[This proof is due to Maurice Kraitchik, L'Echiquier 1926.]
Theorem 3: In a magic knight's tour the number of entries of the forms 4x + 2 or 4x + 3 in a magic
rank or file, counted together, must be even.
We have shown that the board must have both sides even, so let r = 2h, s = 2k then
R = s(sr + 1)/2 = k(4hk + 1) = 4h(k^2) + k.
Thus if we write R and k in binary numeration the last two digits of R and k will be the same (since multiples
of 4 affect only the higher digits). Each rank contains k odd numbers, so the sum of their 1-digits is k
(which provides the required last two digits). Therefore the sum of the 2-digits of the 2k numbers must
contribute 0 to the 2-digit position in R. The 2-digits of numbers of the form 4x or 4x + 1 are 0 already.
The 2-digits of numbers of the form 4x + 2 and 4x + 3 are 1, so to give 0 in this position when added there
must be an even number of them. The same argument applies with regard to the file sums.
[As far as I know this is a new discovery, though clearly related to the importance traditionally placed on
"quartes" in the structure of knight's tours. The proof was first published (March 2003) in our companion site
The Games and Puzzles Journal, issue 25.]
Theorem 4: A magic knight's tour is impossible on a board with singly-even sides.
The term singly-even refers to a number that is twice an odd number, that is of the form 2(2x + 1)
= 4x + 2, where x is any whole number (0, 1, 2, ...). Suppose r = 2h and s = 2k, where h and k are odd numbers.
Now label the cells of the board according to the super-chequering scheme:
A B A B A B ...
C D C D C D ...
A B A B A B ...
C D C D C D ...
...............
It will be seen that the As and Ds are of one colour in the usual chequering and the Bs and Cs are the other colour. Since the board is even by even we can rotate or reflect it if necessary to ensure that the odd numbers are on the A and D cells. There are hk occurrences of each label (this number being odd, since it is the product of two odd numbers). This is also the number of entries of each of the four types 4n, 4n + 1, 4n + 2 and 4n + 3. Note that each rank and each file contains only two different letters.
Now consider how the numbers of the forms 4x + 2 and 4x + 3 are distributed. The (4x + 3)s, being odd, are on the A and D cells, while the (4x + 2)s are on the B and C cells. Since the number of each is odd, when split into two groups one of the groups must be odd and the other even (possibly zero). Suppose there is an odd number of (4x + 3)s on the As and an odd number of (4x + 2)s on the Bs, then there will be an even number of (4x + 2)s on the Cs. This means that the total number of (4x + 2)s and (4x + 3)s on the A and C quarters is odd + even = odd. But for each AC file to be magic it must contain an even number of this class. All other possible distributions lead to the same contradiction, proving the theorem. [This is also a new result, first published (March 2003) in our companion site The Games and Puzzles Journal, issue 25.]
A Challenge: Unfinished Work.
The above theorems account for all cases except boards 4m × (4n + 2). The question remains, whether
a magic knight tour on such a rectangle is possible. I have eliminated the smallest case 4×6 by looking at
all the (36) half-tours. The next cases are: 4×10, 4×14, 8×6, 8×10, 8×14, 12×6,
12×10, 12×14, ... Is there an argument to prove the impossibility (if so we can conclude that magic
knight's tours are only possible on boards whose sides are both a multiple of 4), or can someone come up with
a counter-example?
Update: In 2011 I found such a counter-example, 12×14, published on my Diary blog, headed A Magic Knight Rectangle: Jeepyjay Diary 8 March 2011. The details and diagrams have now been transferred to the new page on Oblong Magic Knight Tours.
A semi-magic tour is a numbered rectangle which is magic in the ranks but not in the files (or vice versa). It is natural to construct examples (see the Semi-Magic Tours page) on those boards on which magic tours are impossible or have not been found. Special types of semi-magic tour include quasi-magic in which the files add to two different values and near-magic in which they add to the magic constant and two other values.
In the previous edition of this page I wrote: Magic knight's tours can be constructed on all boards 4h×4k for h and k greater than 1. (None is possible on the 4×4 or 4×8, but I'm not sure about larger cases 4×4k with k greater than 2.)
Thanks to the work of Awani Kumar we now know that magic tours exist on boards 4×18 and 4×20, and it seems clear that they exist for all boards 4×2k with k greater tnan 8. See the new page on Oblong Magic Knight Tours.
That page now includes the example tour on the 8×12 board that was previously shown here.
A diagonally magic tour is a magic tour on a square board in which the entries on the two long diagonals add to the same magic constant as the ranks and files.
Diagonally magic tours on all square boards of side 4k with k > 2 are possible. Four examples 12×12 were discovered by Awani Kumar recently, see: The Games and Puzzles Journal, issue 26. It is now known, thanks to the work of G. Stertenbrink, J-C. Meyrignac and H. Mackay in searching out the last missing magic tours on the 8×8 board that none is diagonally magic.
The larger the board of course the easier it is to construct magic tours and the more there are, so we do not aim to make a complete catalogue or enumeration of tours on boards larger than 8 by 8; instead we look for tours with extra structural properties, such as having symmetry, or containing smaller magic tours as components, or being formed by particular construction methods.
Two chains of knight's moves (a, b, ...) and (a', b', ...) of equal length and forming parts of a single complete tour, were termed by H. J. R. Murray contraparallel if a and a', b and b', ... each lie on the same rank (or file) of the board, and if the knight traverses the two chains in opposite directions. A pair of contraparallel chains thus contribute a constant sum to each column (or row) concerned. This idea expresses a general principle, but has not in itself led to many results on the 8 by 8 board, though it can be seen to underly the more specialised methods of quartes and braids and half-braids described below.
Any knight's tour on a board 2u×2v may be regarded as composed of uv 4-cell chains, and every number of move can be expressed in the form 4x + n, where x may have any integral value from 0 to uv–1, and n is one or other of the four numbers 1, 2, 3 and 4. In other words x gives the number of 4-cell chains which the knight has already completed, and n gives the position of the knight on the current chain. These 4-cell chains we call quartes (a term introduced by C. Wenzelides 1849, in a more restricted sense).
By a regular quarte on a board 4h × 4k we mean a quarte confined to a single 4×4 block, which I call a quad, and with the special property that it uses one cell on each rank and one cell on each file of the quad. It is either a square or a diamond or a beverley quarte.
It may be noted that the number of cells in each diagonal of the quad is 0 for a square, 1 for a beverley quarte and 2 for a diamond. [Note: this terminology differs considerably from Murray: he uses "quarte" to mean what we here call "regular quarte". He also "indexes" the cells, ABDC in a manner similar to Roget's LEAP scheme, and refers to square and diamond quartes as "single-indexed" and beverley quartes as "double-indexed".]
By a regular tour we mean one in which all the quartes are regular and each quad therefore contains four quartes. Three general types of regular quad are possible; they can be denoted 0022 (two squares and two diamonds), 0112 (square, diamond and two beverley quartes) or 1111 (four beverley quartes).
There are 36 geometrically distinct ways of deleting one move from each of the four circuits in the 0022 squares and diamonds quad; in addition there are 8 ways of deleting the moves from the two circuits in the 0112 quad; so there are 45 regular quads in all. These consist of 36 asymmetric, 8 symmetric with one axis and 1 (the double beverley) symmetric with two axes, so that the total of oriented patterns is 8×36 + 4×8 + 2×1 = 322. (Murray gave the total as 289, omitting 33 cases with the beverley quartes in N instead of Z orientation.)
Here are diagrams of all 45 quads. In these diagrams the signs above each file and beside each rank indicate the excess or defect (variance) of its n-sum from 10. Zero variance is of course shown by 0 (the line will be found to contain the same number of black and white dots). The signs + and – indicate variances of ±2 (the line will be found to contain one more white than black or one more black than white dots respectively). The signs # and = indicate variances of ±4 (the line contains an excess of two white or two black dots). This interpretation assumes that the first number, 4x + 1, in each quarte is placed on the black dot and the last, 4x + 4, on the white dot. If the numbering is reversed then the negative and positive signs must be interchanged (– for + and = for #).
Numbers 1 to 8 of the squares and diamonds type are symmetric.
Numbers 9 to 20 of the squares and diamonds type are formed by combining a symmetric pair of diamonds with a pair of squares (which are always symmetric) resulting in an asymmetric quad, since the axes of symmetry do not coincide.
Numbers 21 to 36 of the squares and diamonds type all contain the asymmetric pair of diamonds and are therefore asymmetric.
Finally, numbers 37 to 45 are the quads with pairs of beverley quartes. Number 45 has two pairs of beverley quartes.
There are four quads in which all the ranks and files have zero variance, namely 1, 8, 44, 45. There are 12 further quads in which either all ranks or all files have zero variance, namely 2, 3, 4, 5, 6, 7, 25, 26, 35, 36, 37, 38. If the 45 quad is used on the 8 by 8 board or in the corner of any larger board then the two loose ends in the corner of the board must be the ends of the tour.
Surprisingly, only 15 quads are used in regular 8 by 8 magic tours, namely 1, 8, 9, 13, 15, 17, 21, 24, 27, 28, 33, 35, 37, 41, 44, and only five of these are in the classes with zero variance in all ranks or files. (Ways of forming magic tours with these quads are described in the page about 8 by 8 tours.)
The quartes that are not regular are of course irregular. They differ from regular quartes either (a) by occupying a quad but not using one cell in each rank and file, or (b) by spreading over more than one quad.
This is a method which includes, as particular cases, the methods devised by Wihnyk (based on magic quads) and Lange (based on borders) and by Murray (based on gnomons), all of which are exemplified in the page devoted to 12 by 12 magic tours.
A braid consists of a series of elements each made of four knight's moves connecting cells in one 2×2 block to cells in an adjacent block. Braid elements occur in all but three of the 108 magic knight tours on the 8×8 board (and even in the three exceptions 00k, 12k, 12l, all due to Francony 1883, there are "pseudo-braids" formed of four slant moves). However, braids longer than three elements occur only in ten of these tours: 14a, 14b, 14e, 14f, 27a, 27b, 27g, 27h, 27o, 27t.
Braids either have all four strands going in the same direction, or one opposed to the other three, or else two going one way and two the other. The two-and-two braid elements can be subclassified into three types according as the two pairs of like-moving strands start in cells in the same rank, file or diagonal of the first block of the 2×4 element. I denote the five types by the codes 4, 3, 2, 1, 0.
If one braid element follows on from another in a straight line then it is obviously of the same type. If it follows on at right angles this remains true for types 4, 3 and 0, but type 2 becomes type 1 and vice versa. Braids of type 0 are especially useful for forming magic tours since the two ranks of an element always add to a + b + c + d, while two of the files add to a + c and two add to b + d, and these values remain the same if a series of such elements are connected, the +1 and –1 cancelling out both in ranks and files.
All five types of braid element occur in the 8×8 magic tours. Those in which braid elements of type 0 occur, with a + b + c + d = 130, are 00b, 00c, 03b, 05b, 05g, 14a, 14b, 14e, 23a, 27a, 27b, 27c, 27d, 27e, 27f, 27g, 27h, 27k, 34c. Thus starting from one of these 8×8 magic tours with one or more conveniently placed braid elements, tours on larger boards can readily be constructed by simply extending these braids to fill the extra blocks of cells, and the resulting tour is guaranteed to be magic. The only requirement is that each braid element be matched by another contraparallel braid element of the same type (so that each a + c is opposite a b + d to ensure the right sum). [I may have overstated this case, other precautions may be necessary. For instance in the new tour 14e it seems essential not to disrupt the irregular quartes. This needs further investigation.]
If we represent each 2×2 block on a 2n×2n board by a single cell on an n×n board then a braid of four knight paths on the larger board can be represented on the smaller board by a single wazir path. I call this the braid plan of the tour. Thus, since wazir paths are easy to construct and visualise, it is possible to construct a whole family of magic knight's tours based on the same 8×8 tour (or parts of such a tour) as kernel.
In the analysis of tours on 4-rank boards carried out by C. Flye Sainte-Marie (1877), tours on these boards are shown to consist of two half-tours connected by a single move on the inner ranks. Each half-tour occupies a pattern of pairs of adjacent cells (dominoes) consisting of the white cells on the outer ranks combined with the black cells on the inner ranks (wobi), and the black cells on the outer ranks combined with the white cells on the inner ranks (bowi). This division of the board into two sets of dominoes is a useful method of constructing tours on any rectangle with an even number of cells.
Two contraparallel chains are said to be contiguous if a and a', b and b', ... are adjacent cells (i.e. dominoes). This term was introduced by H. J. R. Murray in his analysis of the structure of Beverley's magic tour, and led him to find four others of similar structure. (For details of his work see the page on 8 by 8 magic tours.) The four diagonally magic 12×12 tours constructed by A. Kumar are also of this contiguous type: the four strands numbered 1 - 36, 37 - 72, 73 - 108, 109 - 144 form two pairs of contiguous paths, one pair adding to 109 and the other to 181, together making 290 which is one third of the magic constant for this board.