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. I reproduce the text here, with additions:
Back in 2003 I was able to prove that magic knight's tours were not possible on boards 4n+2 by 4m+2, but a proof for the 4n by 4m+2 case eluded me. I now see that that is because there is no such proof! Thanks to a suggestion by John Beasley, that since there is a simple magic knight+wazir tour on the 2×4 board, a magic knight tour should be possible on a sufficiently large 4n by 4m+2 board, I looked at the subject again and found two 12×14 examples last night, shown below.
They were constructed by the "rolling pin" method that I devised for 12×12 magic tours. It's surprising I hadn't thought of trying this before. It's just a matter of widening the board. The files add to 1014 = 169×6 and the ranks add to 1183 = 169×7. Each file consists of three pairs adding to 127 and three pairs adding to 211. The ranks are made up of pairs of complements adding to 169. They differ only in a few moves.
141 122 143 038 139 124 127 042 045 030 131 026 047 028 144 037 140 123 128 039 044 125 130 041 046 029 132 025 121 142 035 138 119 126 129 040 043 050 031 134 027 048 036 145 120 063 034 137 014 155 032 135 106 049 024 133 011 064 061 118 013 154 033 136 015 156 051 108 105 158 146 117 012 151 062 059 016 153 110 107 018 157 052 023 065 010 115 060 149 152 111 058 017 020 109 054 159 104 116 147 150 009 114 057 094 075 112 055 160 019 022 053 091 066 007 148 093 074 113 056 095 076 021 162 103 078 006 069 092 073 008 003 082 085 168 161 096 077 100 163 067 090 071 004 083 088 167 002 081 086 165 098 079 102 070 005 068 089 072 001 084 087 166 097 080 101 164 099
141 122 143 038 139 124 127 042 045 030 131 026 047 028 144 037 140 123 128 039 044 125 130 041 046 029 132 025 121 142 035 138 119 126 129 040 043 050 031 134 027 048 036 145 120 149 034 137 014 155 032 135 020 049 024 133 011 150 147 118 013 154 033 136 015 156 051 022 019 158 146 117 012 151 148 059 016 153 110 021 018 157 052 023 065 010 115 060 063 152 111 058 017 106 109 054 159 104 116 061 064 009 114 057 094 075 112 055 160 105 108 053 091 066 007 062 093 074 113 056 095 076 107 162 103 078 006 069 092 073 008 003 082 085 168 161 096 077 100 163 067 090 071 004 083 088 167 002 081 086 165 098 079 102 070 005 068 089 072 001 084 087 166 097 080 101 164 099
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.
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.) Although it is known that magic knight's tours are possible on all 4h×4k boards 8×8 and larger (e.g. by braid extension of 8×8 magic tours), the only non-square example that has actually been published as far as I am aware is this one, a simple braid extension of Beverley's tour, that I gave in Variant Chess 1992 (vol.1, issue 8, p.105) just to show it is possible.
01 46 71 76 05 44 67 78 07 42 65 80 72 75 02 45 68 77 06 43 66 79 08 41 47 70 73 04 37 12 83 62 39 10 81 64 74 03 48 69 84 61 38 11 82 63 40 09 49 94 23 28 13 36 59 86 15 34 57 88 24 27 50 93 60 85 14 35 58 87 16 33 95 22 25 52 29 20 91 54 31 18 89 56 26 51 96 21 92 53 30 19 90 55 32 17
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 uv1, 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.