The Games and Puzzles Journal — Issue 25, January-February 2003

This issue reports new work on magic knight's tours: a semimagic 10×10 tour, two new magic 8×8 tours (the first discovered for 15 years), methods of search for tours, and some proofs of impossibility of magic tours on certain boards.


Back to: GPJ Index Page
Sections on this page: — (31) A Semimagic 10×10 Knight Tour with Quaternary Symmetry — (32) A New 8×8 Magic Knight Tour — (33) Another New 8×8 Magic Knight Tour — (34) Methods of Computer Search for Magic Tours — (35) Existence Proofs for Magic Knight's Tours — Obituaries
The following articles on magic knight tours have been composed largely from e-mail exchanges since the last issue was published. The tabular and diagrammatic presentation of the magic tours is of course much enhanced from the original e-mail versions. The main proof in the last section only came to the editor as he was setting up the page, on the appropriately numerological date of 3rd March 2003. The patterns of yellow cells in the numerical tour diagrams are those numbered 4n+2 or 4n+3. The significance of these patterns is made clear in Theorems 3 and 4 in item 35 below.
A Semimagic 10×10 Knight Tour with Quaternary Symmetry
by T. W. Marlow
é

From Awani Kumar 26 August 2002: Thank you very much for publishing my article in Games and Puzzles Journal. Its get-up and lay-out are nice and my friends have also appreciated it. You are aware that no magic knight's tours have been discovered on higher order singly-even boards (that is, 10×10, 14×14 etc). Mr T. W. Marlow has found exactly 415,902 quaternary symmetric tours on the 10×10 board. [This was reported in our Issue 16, p.288 (1999).] Based on experience of the 6×6 board, I strongly feel that many semi-magic tours and, may be, a few magic tours are there. [The editor (GPJ) has now proved (see section 35 below) that magic tours on this board are impossible.] Please ask Mr. Marlow to look into it. [This was done and elicited the following replies:]

From T. W. Marlow 13 September 2003: Thanks for your note of 28/8/02. I have only recently got to read it due to computer problems. I had to re-install everything! I think that I mentioned to you that I checked but found no magic tours among the 4-fold 10×10 tours. [This is now seen to have been a chimaeric task, a search for the nonexistent.] However I did not check for semi-magic at that time. It should not be difficult to revise the programme to do that and I will try it shortly. I will keep you posted and also Mr Kumar.

From Tom Marlow 18 September 2002: It proved to be quite easy to set my 10×10 symmetric tours programme to look for semi-magic tours. There appears to be only one, as shown in the attachment, where the rows all total to 505. And the column totals are also regular though not magic. Columns a-d all total 655, g-j are 355, e is 455 and f is 555. I guess that this arises from the symmetry of the tour.

Knight tour on the 10×10 board. Four-fold symmetric. Semi-magic. [The yellow cells mark those that contain numbers of the form 4n+2 or 4n+3; it will be seen that there is an even number of these in every rank and an odd number (5) in every file, and that the grey cells form the same pattern rotated 180 degrees. This information relates to the theorems in section 35 below.]

77 58 45 56 41 60 47 50 19 52
44 73 76 59 46 55 18 53 48 33
75 78 57 42 61 40 49 32 51 20
72 43 74 79 64 37 54 17 34 31
85 80 65 62 13 88 39 36 21 16
66 71 86 89 38 63 12 15 30 35
81 84 67 4 87 14 29 24 93 22
70 1 82 99 90 11 92 7 28 25
83 98 3 68 5 96 9 26 23 94
2 69 100 97 10 91 6 95 8 27

GPJ to TWM 28th September 2002: Sorry for delay in responding to your e-mail. I filed it away and then must have got sidetracked onto something else. It seems surprising that there should be only the one semi-magic tour among the quaternary symmetric 10×10 tours. I can see no way that the pattern could have been singled out by some other form of reasoning than a computer search.

GPJ to TWM 5th October 2002: Having looked in more detail at the semi-magic 10×10 quaternary tour, I have noticed the following geometrical features ... the tour has a high degree of axial symmetry, particularly in the central two ranks and files, while the 4×4 corner areas are filled by ‘quartes’ consisting of a diamond, a square and a pair of ‘semiregular quartes’ as shown in diagram (c) in the section (8) on Semiregular Magic Tours [now termed Irregular] on the Knight's Tour Notes website. Is it possible to do a similar search for semimagic 10×10 tours with binary symmetry? ... the search might be made more manageable by restricting it to tours with axial symmetry in the central ranks and files.

From Tom Marlow 10 October 2002: Thanks for your two messages and the geometrical points about the tour. I've also noticed that every horizontal pair down the e/f files totals 101. This seems suprising in a tour with rotary symmetry and it means that the rectangles e1/f5 and e6/f10 each total to the magic constant. I was suprised that only one semi-magic tour appeared and also that its numbering started at the same point (b3) that my programme starts in its search for tours. This despite the fact that the programme cycles the numbering of each tour in the search for magic. However it does find a cycled version of the same tour and this and other checks that I've done make me reasonably sure that nothing is being missed. I will try to have a look 2-fold symmetric tours but I suspect that the number is enormous.


A New 8×8 Magic Knight Tour
by T. S. Roberts
é

Tim Roberts wrote on 6 November 2002, to express “appreciation for your wonderful site on magic knight's tours” and also to clarify some points. GPJ wrote that “If a new one is found it will be of irregular type.” In a later e-mail Tim suggested that the 8×8 tours, in arithmetical form, should be put into ‘Excel’ spreadsheet format, and subsequently very helpfully sent a version of the catalogue in this form, including diagonal sums. It can now be downloaded from the KTN website. This also stimulated the editor to put some missing notes on irregular tours onto the website. This included Murray's observation that the number of irregular quartes is always a multiple of four.

From Tim S Roberts 21 January 2003: Could you please confirm for me that (so far as you know!) your catalog of magic knight's tours on an 8 by 8 board is up-to-date? If so, I can report the discovery of a new magic tour. It has 8 regular quartes. ... Tim S Roberts, Faculty of Informatics and Communication, Central Queensland University, Bundaberg, Queensland 4670, Australia.

GPJ to TSR 21 January 2003: As far as I know the last 8×8 magic knight's tours discovered were the five found by Tom Marlow and published in The Problemist, January 1988, and I believe my list is complete, but I'm not infallible. Congratulations on finding the new tour! If you could send me a diagram of the tour I could make an independent check for you. I promise not to publish it or distribute it to anyone else before your own article appears. — Later the same day: I forgot to ask whether you found the new tour by reasoning or by a computer search – and if the latter whether you are in a position to say that no others are possible – no doubt all this will be in your article.

From Tim S Roberts 22 January 2003: Here's the square. Please don't do anything with it until I give the go ahead. [After approaching several possible journals, which either have a waiting list of several years or consider the subject beyond their remit, Tim has now given permission for the tours to be published here!] — As you can see it has 8 regular and 8 irregular quartes, and has a '4' in the top left-hand corner, making it easy to check against your catalog! [In the diagram the irregular quartes are those shown by bolder lines.]

4 23 50 55 6 25 58 39
49 54 5 24 57 38 7 26
22 3 56 51 28 1 40 59
53 48 21 2 37 64 27 8
20 35 52 29 14 9 60 41
47 32 13 36 63 44 15 10
34 19 30 45 12 17 42 61
31 46 33 18 43 62 11 16

... Re the new square, hope you can confirm it's original! It was found by a combination of insight and computer search, using a normal Pentium III PC....

In response GPJ noted that the new tour would be 01i in the catalogue and: “The pattern of the 8 irregular quartes used in your tour is quite distinctive, so there is no doubt about it being distinct from the others. This is also clear from the numerical form – being the only one with a 4 in the corner.”

GPJ to TSR and TWM 19 February: I've been looking once again at the patterns formed by the numbers of the four forms 4n, 4n+1, 4n+2, 4n+3 in the magic tours, and your first tour 01i (in its forward-numbered form) besides being the only one with numbers of form 4n in corner cells (4 at a8 and 16 at h1) is also the only one without numbers of this form in the centre cells (d4,d5,e4,e5). Presumably these facts are related.

Tom Marlow to TSR and GPJ 2 March 2003: I have noticed that Tim's first new magic tour has some symmetry in it. This has not been mentioned so far so I'll describe it. — If steps 1 to 12 are rotated 180 degrees they coincide with steps 13 to 24. Then 25 to 32 and 33 to 40 show the same effect and also 41/52 with 53/64. The whole tour is of course not symmetric so perhaps a suitable description is quasi symmetry. — Looking into the possibilities led me to discover that magic tour 01e in the catalogue consists of two 32 step loops with rotary symmetry and furthermore the two form a mirror image pair about a horizontal axis - though the numbering does not line up. My computer says that there is no other magic from a 2×32 set up nor 24-16-24 and I am looking at other variations.


Another New 8x8 Magic Knight Tour
by T. S. Roberts
é

From Tim Roberts, 29 January 2003: I have found another new tour. This one is interesting – count the number of regular quartes!

3 22 49 56 5 20 47 58
50 55 4 21 48 57 6 19
23 2 53 44 25 8 59 46
54 51 24 1 60 45 18 7
15 36 43 52 17 26 9 62
42 39 16 33 12 61 30 27
35 14 37 40 29 32 63 10
38 41 34 13 64 11 28 31

GPJ reply: “Great Stuff! Congratulations again. It looks as though there could be quite a few more magic tours to be found. — The new one knocks down Murray's rule about the irregular quartes occurring in fours. However he seems to have assumed that the irregular quartes had to spread over two or three quadrants, and the quartes in the bottom left and right corners don't meet his criterion.”... [They are of a new semiregular type — ‘semiregular’ meaning: confined within a 4×4 quadrant but not having one cell in each rank and file of the quadrant.] — “Your new one (which becomes 14e in the catalogue) has some nice long braids that make it easy to extend to 12 by 12 or larger boards.” [It will be seen that the pattern formed by the numbers of form 4n+2 and 4n+3, shown by the yellow cells, is much more prosaic than for the first tour.]


Methods of Computer Search for Magic Tours é

After the editor had revised the irregular tours page on the Knight's Tour Notes site, mentioning the new tour in a stop press footnote Tim e-mailed 27 January 2003: I find your statement “With current computing power it should be possible for someone very soon to complete the enumeration of all 8×8 magic knight tours” interesting. When I last tried to estimate how long this would take on my computer, a few weeks ago, I figured it would take approximately 124 million years. I almost started the program anyway, but then thought “What if I get a power glitch after only, say, 103 million years? What a bummer that would be”, so I didn't. :-) :-)

From Tom Marlow 5th February 2003 (after learning about the first new magic tour reported above): I said that I would try to describe my current attempt to find new magic tours by computer, so here it is. — In principle the programme seeks to find every possible knight tour and check it for magic (obviously a ridiculous aim). But it also keeps a running total of the step numbers entered in each column and also of the number of steps in each column. Then if a column reaches eight entries and the step number total is not 260 there is no point in continuing to a complete tour and the programme immediately backtracks. At least one column must reach eight entries by step 57 at latest or step 16 at earliest and presumably the average is around 40 steps. The first such column will usually not total 260 so if this happens at step 40 there should be an enormous reduction in abortive work to find complete tours. However I cannot see how to make any sort of exact assessment of the saving. — In addition the programme makes a similar check at the seventh entry in a column. If that entry is the nth step of the tour then the next entry in the column must be in the range n+2 to 64. If the difference between the running total of the column and 260 is outside that range then that column can never attain 260 and again there can be an immediate backtrack. It is even more difficult to assess how effective this is but I include it because I feel sure that there is a substantial nett gain against the checking that it involves. — A similar check could be done at the sixth entry or earlier but the process gets more complicated to define and the ranges wider and so less effective in limiting the work. — I run the programme for a few hours starting the tour at arbitrary points on the board but so far with no result. I would be interested to have any comments on this process.

From Tim Roberts 31 January 2003: Unfortunately, my programs don't really help to estimate the number of magic tours. My current feeling is that there ‘might’ be hundreds out there, but then again, there might be none! — My programs first attempt to cut down the enormous search space. I had, as I said in an earlier email, got the algorithms refined so that a full search should take only 124 million years! So then it became a matter of just looking at the most likely subsets, which basically meant, sticking very close to tours consisting of regular quartes. — A few weeks ago I repeated Marlow's result that there were no more regular tours to be found (nor semi-regular ones for that matter). So I have now just relaxed the constraints a little, and as a consequence my program finds all of the regular tours, all of the semi-regular ones, and a few of the known irregular ones. And it's now found the two new tours I've sent you. No alarm goes off - when the program finds a tour, it just writes it to a file. I manually check to see if its new - I haven't had the time to automate this yet!!! — Hence the reason why I can't estimate the number out there - my programs are deliberately designed based on characteristics of already-known tours!

From Tim Roberts to Tom Marlow copied to GPJ 6th February 2003: I have been fortunate enough to find two new magic knight's tours on an 8×8 board. ... I can send you the program that found them, if you are interested; I would be happy for you to amend it as you see fit, or use it to find other tours. A warning - it is poorly structured and even more poorly commented - but it is only 150 lines or so in total, and most of those are initialisation and reporting! It uses backtracking, and is written in C++. It makes use of what I call both non-destructive and destructive algorithms. The former attempt to cut down the search space, without destroying any possible tours; the latter are needed to reduce the search space still further, but in so doing they possibly destroy (overlook) many valid solutions. I've also confirmed your earlier work that there are no more regular tours to be found!

GPJ to Tom Marlow and Tim Roberts 6 February 2003: The following is the idea that I had at the back of my mind in my earlier e-mail. Perhaps it can be used to speed up the search by cutting of some sequences before they complete a whole rank or file. The result is a particular case of a property of magic diagrams in general. — First, observe that any four numbers {a1, a2 ,a3, a4} out of the set {1, 2, ..., 64} can occur in a rank or file of a magic tour 8×8, since each can be paired with its complement (65 - ak). At the other extreme 8 given numbers {a1, ..., a8} can only occur if their sum is 260. — Denoting the sum of an arbitrary set of h numbers {a1, ..., ah} by Sh, and using <= for ‘less than or equal to’, we have the requirements:
(a) 260 <= S8 <= 260, which means S8 = 260.
(b) 196 <= S7 <= 259
(c) 133 <= S6 <= 257
(d) 71 <= S5 <= 254
(e) 10 <= S4 <= 250, which is always true.
Of these conditions the 71 <= S5 looks the most useful. It means that if any five numbers in a partially formed magic line add to less than 71 then the line cannot be completed. In other words the computer should keep a watch on the sum of the 5 lowest numbers in each line. I'm not sure if this helps, but it's all I can think of at present.

From Tim Roberts, 6th February: Yes, some of my programs already do a version of this. They use only the upper checks, since the numbers are entered in reverse order (64 down to 1). The bounds can in fact be made more strict than you indicate - since two consecutive numbers can't be in the same rank or file, the actual limits are S7<=259, S6<=256, S5<=251, S4<=244.

From GPJ to TSR 7th February: My statement of the rule about lower and upper limits on the sums of 5, 6 or 7 entries was put in that form since it then also applies to magic tours by other pieces such as king, queen, or rook. The fact that two consecutive numbers cannot occur in a row of a knight's tour is taken care of automatically by the construction sequence following knight moves. ...

From Tom Marlow 10th February: I do my programming of this sort on a (now elderly) Acorn computer. These machines were built in UK, sponsored by the BBC and have an OS which I find much better than Windows. Unfortunately the PC and Windows have won and I am forced to use them as well. — I write the Acorn programmes in Basic with a core of Assembler where the hard work is done. (I fear that the Assembler would be difficult to understand without a manual of ARM Assembler and is almost without comments) I've looked at C++ and been meaning to teach myself it but haven't got round to it yet. And lately I've been doing some work with Visual Basic which I find user unfriendly which puts me off trying MS C++. Can you suggest a compiler that is oriented to our sort of use rather than display? — I would certainly be interested to see your programme if you think a C beginner would understand it. I think you have via George my description of how I work though it may not be clear that I pay no attention to quartes rounds. This may be too ambitious!

From Tim Roberts 11 February: Attached please find the program that found the two new squares.

For those with the technical knowhow, this has been converted to HTML and can be accessed here: gpj25p.htm [Originally called mallv02.htm]
- C++ is certainly not the easiest language to learn; and all of the C++ compilers seem to be exceedingly complex beasts. I'm not sure what would be better, however. Assembler would certainly be faster, but I haven't learnt that on a Windows-based PC. Funnily enough, the 50+ year old Fortran may be OK.... — I spent the first month of my research trying things by hand, which was invaluable for understanding the underlying concepts, I think. I'm happy to explain the program, by the way - it's not commented at all at the moment, since I never expected anyone but myself to be interested in it.... — What really intrigues me is the prospect of a diagonally-magic knight's tour possibly being out there somewhere, but I can't see any quick way to search for one, or, on the contrary, to prove it impossible....
Existence Theorems on Magic Tours
by G. P. Jelliss
é

Theorem 1: A magic rectangle is impossible on a board odd by even.
By a magic rectangle here I 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, since there are s cells in a rank, and the file sum is S = rA, since there are r cells in a file.
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.

Theorem 2: A magic knight's tour is only possible on a board with even sides.
By a magic knight's tour here I mean a magic rectangle in which the numbers 1, 2, ..., rs follow the path of a knight. Labelling the cells of the board according to this pattern:

 U V U V...
 V U V U...
 U V U V...
 V U V U...
 ..........
is known as chequering, and it is a property of the knight that it moves from a cell labelled U to a cell labelled V, and vice versa. All the U-cells will be odd numbered and all the V cells even numbered, or vice versa. In a board with an odd number of files, adjacent ranks would contain an odd and an even number of odd-numbered cells. The rank sums would therefore be alternately odd and even. [This theorem 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) = 4(hkk) + 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 is the required figure). 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.
This result has been used in the tour diagrams above by highlighting the numbers of the forms 4x + 2 and 4x + 3 in yellow.
[I came up with this proof, for the case of the 8×8 board, in an e-mail to Tim Roberts sent on 7th February 2003. For this case 260 denary = 100000100 binary. The unit digits of the four odd numbers in each magic rank and file add up to 4 = 100 binary, so the 2-digits of the eight numbers must add to an even number to ensure the 2-digit of the total is 0.]

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 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 occupy the cells previously labelled U and the Bs and Cs the positions labelled V. 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.
Permuting the ranks or permuting the files of an array of numbers does not alter the rank sums or file sums. By two such permutations we can convert the pattern of the numbers to the form:
 A A A ... B B B ...
 A A A ... B B B ...
 ...................
 C C C ... D D D ...
 C C C ... D D D ...
 ...................
In other words the As form one quarter of the board, the Bs, Cs and Ds other quarters. (This transformation may not be strictly necessary, but it's the way I visualised the argument.) There are hk occurrences of each label (this number being odd, since it is the product of two odd numbers).
Now consider how the numbers of the forms 4x + 2 and 4x + 3 are distributed. The (4x + 3)s, being odd, are in the A and D quarters, while the (4x + 2)s are in the B and C quarters. 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 in A and an odd number of (4x + 2)s in B, then there will be an even number of (4x + 2)s in C. This means that the total number of (4x + 2)s and (4x + 3)s in 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.

THEOREM 5? Work in Progress!
The above theorems account for all cases except boards 4m × (4n + 2). The question still 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, or can someone come up with a counter-example?

Update: I came up with a counter-example on a 12×14 board in 2011. as reported on the KTN page on General Theory of Magic Knight's Tours.


Postscript: Obituaries é

Robin Merson

An e-mail dated 22 August 2002 from Tony Merson, Farnham, Surrey (in response to a letter of my own dated 19 Feb 2000 only recently forwarded to him) reports that his father Robin Merson died as long ago as August 1992. He was belatedly diagnosed with bowel cancer and although this was successfully operated on, he died from a secondary chest infection without returning home from hospital. He left considerable notes on mathematical topics which have been passed to a former colleague at the Royal Aircraft Establishment, Farnborough.

Derick Green

An email from John Beasley reports the sad news that Derick Green has died of cancer. He was only 42 years old. I have no other details but an obituary is due to appear in Variant Chess. I never met Derick, but he contributed five articles to the last five printed issues of The Games and Puzzles Journal. He moved several times and, not having heard from him, I was uncertain whether the last printed issue ever reached him. I believe he was involved extensively in postal games play.


Sections on this page: — (31) A Semimagic 10×10 Knight Tour with Quaternary Symmetry — (32) A New 8×8 Magic Knight Tour — (33) Another New 8×8 Magic Knight Tour — (34) Methods of Computer Search for Magic Tours — (35) Existence Theorems on Magic Tours — Obituaries
Back to: GPJ Index Page

Copyright 2003 G. P. Jelliss and contributing authors.