‹ (1) Magic Squares using Alternating Moves. ›

The following note was sent by Professor Donald E. Knuth of Stanford University (dated 16 Sep 2000): I ran across a curious thing in The Strand Magazine volume 36 (1908), contributed by "Mr J.Wallis, 51, Holsworthy Square, Gray's Inn Road, W.C.": He constructed a tour of the chessboard in which knight's moves alternate with rook moves, and the square is also magic [i.e. adds to the same sum, 260, in each rank, each file and the two main diagonals]:

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

(This was on page 480 of the American edition, probably in the same place of the London edition since each number had 120 pages that year.) ... So I have two questions: (1) Have you ever heard of this "J.Wallis" before? (2) Have you ever heard of such alternating tours before? [Wallis also presented one for knight and bishop, but not magic, on page 360.]

Editor's Response: I've had no luck tracing this J. Wallis. There are some notes on earlier, non-magic, Alternating Tours in item (2) below. I noted however that by simple transformations Wallis's tour can be converted into other alternating tours similarly magic:

In the above diagram (A) is the Wallis tour, which uses {0,1} and {0,2} rook moves alternating with {1,2} knight moves. (B) is formed by interchanging the second and third and the sixth and seventh files, giving a tour using {0,1} and {0,2} rook moves alternating with {1,1} bishop moves (in other words it is a magic queen tour). Diagram (C) is derived from (B) by interchanging the 2-3 and 6-7 ranks, giving a magic rook + knight tour, though now three different rook moves are used. Diagram (D) is derived from (C) by interchanging the 2-3 and 6-7 files, or from (A) by interchanging the 2-3 and 6-7 ranks, giving a rook + alfil tour, using three types of rook move (this can also be regarded as a magic queen tour). It is necessary to show some of the moves as curved, otherwise they merge and the route becomes unclear.

‹ (2) History of Alternating Tours. ›

The day after replying to Prof. Knuth's letter decribed in item (1) I received a letter (dated 26 September) from Colin Singleton, the new co-editor of the Journal of Recreational Mathematics, asking about tours of the 8 by 8 board by alternating knight {1,2} and fers {1,1} moves, since he had also received a note from Prof. Knuth on this subject. My reply (27 September 2000; copy to D.E.Knuth) was as follows:
Dear Colin, Strangely enough I also received a little note from Professor Knuth a few days ago, enquiring about the history of alternating knight and other-piece tours, to which I replied briefly yesterday. I'm afraid his work is slightly anticipated by a thousand years or so! Knight-Fers and Knight-Alfil tours were first given by Abu-Bakr Muhammad ben Yahya as-Suli (born circa 880, died 946 ad). They are reproduced in numerical form in H.J.R.Murray A History of Chess (1913) p.336. I give them in diagram form. Similar tours also appear in other Indian and Turkish sources of later date.

This subject was rediscovered by P.B.van Dalfsen who published symmetric solutions in Fairy Chess Review (Vol.8, issue 10, problem 9601 June 1953 p.74; solution in issue 12, October 1953 p.93). The solutions in FCR are given as series of square coordinates (a1, b2 etc) I show them in diagram form above.

‹ (3) Doubled Alternating Tours. ›

My letter continued: I sent the following results to Stefanos Pantazis for the US Probem Bulletin on 14 June 1993 (I just located a copy of the letter in my files), but I don't think they were ever published there. I found that it is possible to construct a pair of knight-fers and knight-alfil tours that are not only symmetric but both use the same pattern of knight's moves! (as shown in the third diagram). Also from the same letter is an alternating knight-commuter tour (in numerical form because of difficulty in showing it graphically).

It is easy to prove that the fers moves must form a fixed pattern of crosses. Just start at a1 and put in the only possible fers move, then go to c1 (which cannot join to b2) then go to e1 and so on. A similar argument shows that alfil (2,2) moves and commuter (4,4) moves similarly form a fixed pattern in alternating tours. [In fact the {4,4} case needs no proof since they form a fixed pattern anyway.] If you would like to use these items in J. Rec Math please let me know, otherwise I will publish them on my web pages.
—You could set as a problem to find (or prove impossible) a set of knight-fers, knight-alfil and knight-commuter tours with the same knight moves in all three (the example shown above combined with the commuter moves forms circuits).

‹ (4) Tripled Alternating Tours. ›

Since I've received no response from Colin, I publish the notes above and also the following solution to the above triple tour problem that I have received from Prof. Knuth. (8 October 2000). Dear George, Many thanks for sending me a copy of the wonderful letter you wrote to Colin Singleton on 27 September. Of course I couldn't resist setting my computer loose on the problem, especially because a small modification of my "dancing links" program handles situations like this with ease! Eureka! My program found the symmetrical pattern of knight moves (A) that makes a complete tour when combined with any of the restricted bishop moves [{1,1}, {2,2}, {4,4}], or any of the rook-reflection moves [horizontal or vertical, as diagrammed], thus making five tours altogether! The same holds if the middle pattern is changed as in (B).

Besides these two symmetric solutions, there are seven distinct asymmetrical solutions to this 5-way tour problem. Disregarding symmetry, the total number of solutions is therefore 4×2 + 8×7 = 64. Now that we know such solutions exist, we can reasonably ask people to find a single solution, because the five conditions provide plenty of constraints to keep the amount of backtracking to a human scale (without computer assistance).
—A similar problem turns out to have an essentially unique solution: Instead of rook-reflection use horizontal or vertical 4-leaps, {0,4} [horizontal case diagrammed]. Then the knight moves leading to five tours must be as in (C), or one of the other seven obtained by rotation or reflection. With shorter leaps, wazir {0,1} there are no such solutions; but with dabbbaba {0,2} there are two, (D) and (E), almost identical. Overall, the symmetrical solutions with rook-reflections are most appealing, I think.

Prof. Knuth's letter concludes with further extensive results on enumerating alternating tours but I leave these for publication elsewhere – unless there is an outcry for them – since they go beyond my idea of "recreational" mathematics. I will only mention his results that there are 4×895 + 8×16,072,302 = 128,581,996 knight + commuter alternating tours 8 by 8 as against 4×(12 + 20) + 8×160 = 1408 knight + tripper alternating tours on the 6 by 6 board. The symmetric tours on the 8 by 8 board are all rotational, but on the 6 by 6 board 20 are rotational and 12 reflective.
—These results interest me since the {3,3} move on the 6×6 and the {4,4} move on the 8×8 board are the moves connecting each cell to its uniquely defined "antipode" on that board. In fact I think it is true to say that on a board 2k×2k the diagonal moves that can be used to form alternating tours with knight are those moves {r,r} for which r is a divisor of k. (On the 4×4 board no tours are possible, but knight + fers and knight + alfil pseudotours, consisting of two superimposed circuits occur. On the 2×2 board the knight cannot move, but an alternating wazir + fers (i.e. king) tour is possible.) I leave the question of an alternating tour using {5,5} antipodean leaps on the 10×10 board for further study!

‹ (5) Figured Tours: Prime Numbers Guarded by Queen. ›

The following three Figured Knight's Tours are constructed so that a Queen placed on an appropriate cell guards all 17 odd primes; in other words the cells containing the odd prime numbers are all on the rank, file and diagonals through one particular cell (coloured mauve). The first two solutions appeared on Mike Keith's fascinating "World of Words & Numbers" website [now available here and as PDF download here] where it is stated that the problem was first proposed by G. L. Honaker Jr. in November 1998. (A) by Mike Keith is an open tour showing all 18 primes (i.e. including the even prime 2) guarded by the queen on cell 35. (B) by someone identified only as "gscgz" is a closed tour showing all 18 primes also guarded by the queen on cell 35. (C) is a solution I found on 11 October 2000, and sent to Mike Keith, in which the queen, standing on square 1, 'observes' all 17 odd primes, and 'ignores' all 14 odd composite numbers.

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

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

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

On Arrangement Conventions. The Frénicle convention of arranging numbered arrays so that the smallest numbers are in the first two cells of the top row (which I use for example in my catalogue of 8×8 magic knight's tours) is convenient for some purposes, such as ensuring there are no duplicates in a collection, but often results in the geometrical properties of arrays being differently oriented. There doesn't seem to be any 'perfect' convention suitable for all circumstances. H.J.R.Murray in his cataloguing of the magic knight's tours followed the convention of having the odd numbers on the white cells (those reached by bishop moves from the top left corner cell). Thus I have reflected my original version of (C) left-to-right so that the odd numbers occur on the white cells as in (A) and (B). If shown according to the Frénicle convention (A) would be rotated 90° clockwise, while (B) would be reflected left-to right. Murray also had additional rules to ensure a magic tour could only have one orientation, which seem to be that '1' should be above the two semi-diagonals a8-d4, e4-h8 or if on the semidiagonal a8-d4 then '2' should be above the diagonal. This convention works for knight's tours on the 8×8 board, and on any even-sided square board, but does not necessarily work for other boards or other pieces. The Frénicle convention has the advantage of being more universally applicable.