Magic Rectangle 7 by 9

The first rectangle here shows a King Tour in which the ranks sum to all the successive values from 285 to 291 and the files to the successive values from 220 to 228.

01 56 57 15 14 42 43 29 28 
55 02 16 58 41 13 30 43 27 
54 17 03 40 59 31 12 26 45 
18 53 39 04 32 60 25 11 46 
19 38 52 33 05 24 61 47 10 
37 20 34 51 23 06 48 62 09
36 35 21 22 50 49 07 08 63 

The middle rank and file are naturally magic, consisting of pairs of complements (adding to 64) plus the middle average number 32, giving the required totals of 288 and 224.

This type of King Tour with consecutive rank and file totals seems to be possible on any odd-sided oblong where the sides have no common factor. I've not seen this result published anywhere before. The moves are completely regular, being diagonal except where they meet a board edge when the king takes a lateral step along the edge and then resumes its diagonal moves as if reflected from the edge.

I used this regular numbering of the cells to construct the following magic rectangle by a series of interchanges of pairs of entries.

01 59 57 14 15 42 43 29 28 
55 02 18 58 41 13 30 44 27 
60 17 03 40 54 33 11 25 45 
16 52 38 08 32 56 26 12 48 
19 39 53 31 10 24 61 47 04 
57 20 34 51 23 06 46 62 09 
36 35 21 22 49 50 07 05 63 

This began with the interchange of 56 with 59 and 5 with 8 which fixed the top and bottom ranks and the second and eighth files (without altering the total of the middle file). Then the interchange of 16 with 18 and 46 with 48 fixed the second and sixth ranks and the third and seventh files(without altering the total of the middle rank). After that it became a bit more difficult to find suitable changes that did not disrupt the previous ones. The resulting tour uses ten different types of move instead of just two. Can it be done with less disruption?

Here is an earlier example I found based on a knight tour.

03 14 57 56 05 63 31 17 42 
38 55 04 41 48 23 40 09 30 
58 02 27 18 45 21 29 39 49 
54 28 44 52 32 12 20 36 10 
15 25 35 43 19 46 37 62 06 
34 53 24 13 16 51 60 11 26 
22 47 33 01 59 08 07 50 61 

This uses 16 different types of move, so can hardly be called a "tour" at all. It is also not symmetric (or "associated" as magic square devotees term it) since the pairs of complements 55-9, 41-23, 53-11 and 13-51 lie along the second and sixth ranks instead of being diametral.

Bright Sea at Sunset

After sunset tonight the sea was strangely brighter that the sky.

But I'm afraid the photo is inadequate to show it.
Earlier the setting sun was very red but I didn't have the camera with me.

Magic Rectangles 5 by 7

01 25 17 09 33 06 35
20 16 28 04 12 15 31
26 07 29 18 10 34 02
21 23 13 32 05 24 08
22 19 03 27 30 11 14

11 31 16 06 15 26 21
17 27 07 22 32 12 09
13 03 28 18 08 23 33
29 24 04 14 34 19 02
20 05 35 30 01 10 25

13 09 05 35 33 07 24
23 10 30 02 31 08 22
15 16 17 18 19 20 21
14 27 06 34 04 29 12
25 28 32 01 03 26 11

05 27 15 12 25 19 23
32 03 16 29 14 28 04
06 35 26 18 10 01 30
34 08 22 07 20 33 02
13 17 11 24 21 09 31

The first two magic rectangles above were constructed on 7 November
and are rather irregular. The magic constants are 90 and 126 (i.e.
5x18 and 7x18).

The third is slightly more regular, having the sequence 15 to 21 along
the middle rank, similar to the method used for the 3x7 magic
rectangles reported here on 13 October.

The fourth is the most regular having diametrally opposite cells
complementary (i.e. adding to 36) except for two cases 32-04 and 34-
02. It may be that a completely symmetric magic tour is impossible,
but I've not been able to prove this so far. (It is possible on the
3x5 board as I showed in Chessics #26, 1986.)

Obviously every rank and file contains an even number of odd numbers,
and hence an odd number of even numbers. There are 8 numbers of the
form 4n, occurring in pairs of complements, and 9 of the form 4n + 2
consisting of the middle number 18 and four pairs of complements.
There remain 9 each of the forms 4n +1 and 4n + 3, which are
complements of each other.

The method I use for constructing these is to first put the numbers
into the array in some regular pattern, and then to adjust the rank
and file sums to give the magic values by making transpositions of
pairs or groups of numbers.

The ranks and files of these magic rectangles can be permuted without
affecting the magic property. So each generates 5!x7!/4 = 151200
(oriented with the long lines horizontal). The division by 4 is to
avoid counting rotations and reflections separately.

I've been trying to find an arrangement that uses the least number of
types of move but so far have not managed to reduce the number to less
than nine.

=====
Addendum 15 November:
A symmetric solution is possible. One is given in W.S.Andrews
Magic Squares and Cubes Fig.458 due to C.Planck.
Planck also seems to have anticipated my work on the 3x5 case,
since the 39 solutions are mentioned but not diagrammed.

Crane working on Hastings Pier

I meant to post this photo of the crane working on Hastings Pier a while ago.
It was taken 28 September. The crane has since gone.

How it was brought there and taken away I didn't see.
I don't think they were drilling for oil!
Impressive engineering work.

Magic Rectangle Tours

I have been doing a search for magic rectangle tours
on 3 by 7 board (and others) by pieces with limited moves,
and have found only these three so far.

They all contain the rank 8, 9, 10, 11, 12, 13, 14 (in some order)
adding to magic constant 77. The files add to 33.

Each tour is presented in forward and reverse numbering,
and oriented with the 1 (or 2) in the top left.

------
Amazon (Queen + Knight) magic tours:

15 01 19 02 21 03 16 == 06 19 01 20 03 21 07
12 14 09 11 08 13 10 == 12 09 14 11 13 08 10
06 18 05 20 04 17 07 == 15 05 18 02 17 04 16

This uses seven types of move
Rook 02, 03, 04, 05, 06, Bishop 11, Knight 12

01 19 18 04 03 15 17 == 02 17 20 01 06 15 16
12 09 13 08 14 11 10 == 10 13 09 14 08 11 12
20 05 02 21 16 07 06 == 21 03 04 18 19 07 05

This uses nine types of move
Rook 01, 02, 03, 04, 05, Bishop 11, 22, Knight 12

------
Raven (Rook + Nightrider) magic tour:

01 17 15 05 21 02 16 == 06 20 01 17 07 05 21
14 13 12 09 08 11 10 == 12 11 14 13 10 09 08
18 03 06 19 04 20 07 == 15 02 18 03 16 19 04

This uses seven types of move:
Rook 01, 02, 03, 04, 05, Nightrider 12, 24

------
Does anyone know of previous work on this subject?
I published some results on the 3 by 5 board
in Chessics #26 (1986) including a symmetric tour
using only four types of move.

I can only find an article by Marian Trenkler of Slovakia
http://math.ku.sk/~trenkler/
published in Mathematical Gazette 1999.

A Figured King Tour

The wazir tour with squares in a row on boards 2x2, 6x6, 10x10 and so on was published in Chessics #21 (1985). It occurred to me yesterday to look at the same problem on the 8x8 board but using the king as the touring piece. It appears that a solution with the square numbers in order of magnitude is just beyond the realm of possibility (with a knight move in place of one of the king moves it can probably be done). However I did find a solution with the numbers slightly out of order:

I set this as a puzzle on twitter, but haven't had any claims of anyone solving it yet. Of course the tour is not completely determinate. Some of the parallel pairs of moves can be replaced by crossing diagonal moves. But with the condition "minimum crossovers" it is probably unique. It includes a 6x6 solution with the numbers in correct sequence in the central area.

Most Asymmetric Tour?

How does one assess how asymmetric a tour is? Or indeed any object? Is there an objective measure of the degree of asymmetry?

Thinking over this question the last two days I have come up with the tour shown which I mantain is the most asymmetric tour possible. There may be better, or alternative ways of measuring asymmetry, but I have concluded that in the case of a tour it is the number of the 21 geometrically distinct moves that occur an odd number of times. In this tour the total is 18, and moreover 12 of these occur only once.

The only moves that occur an even number of times are the corner moves like a1-c2 (where there are eight, which occur in every closed tour) the edge-to edge moves of the type a2-c1 (eight again), and the pair of moves a3-c2 and h3-f2 which are of the same type. Two moves are considered to be of the same type if one can be put in the position of the other by a rotation or reflection of the board.

The 12 moves that occur only once are b1-c3, d1-c3, f1-e3, b2-c4, d2-b3, d2-f3, d3-c5, e3-d5, a4-b6, e4-g5, b5-d6, e5-f7.

Warnsdorf Squares and Diamonds Tour

The first thing I noticed on seeing the figures from the Warnsdorf 1823 book, is that the final figure #96 is a tour of squares and diamonds type! This seems to have been added as an afterthought and is preceded by a diagram in which the squares and diamonds are lettered A, B, C, D using a different type style in each quarter of the board.
This confirms Murray's statement that 'The first composer to give the figure which shows that the cells of the quadrant could be filled by four closed quartes was v. Warnsdorf (1823)'. However the diagram is not in graphic form, and strangely Murray made no mention of the accompanying tour!
Warnsdorf shows tours in numerical form. Here is the tour diagram in graphic form:

This means that Warnsdorf has priority in the showing of a tour of squares and diamonds type. The previous earliest examples I was aware of were the two given by "F.P.H" in 1825 and the near-magic tours in the study by C. R. R. von Schinnern in 1826.

Warnsdorf from the original source

Thanks to the Cleveland Public Library, Ohio USA, I have now been able to study the diagrams in the 1823 book by H. C. von Warnsdorf. The figures relating to his Rule ("Always move the knight to a cell from which it has the fewest exits") are numbers 32 to 39 in Table 5. He begins by applying the rule to the 6x6 board, with four examples, then goes on to the 6x7, 6x8, 7x8 and 8x8 boards, giving one example for each.
Warnsdorf's tours are shown with the cells numbered in the sequence visited by the knight, but here we show them in geometrical form. A black dot indicates the start cell, and a dark circle the end cell. A circle round the initial dot indicates that there are choices of first move, though this may only be because of symmetry. The light circles mark points where the rule provides a choice of two or more moves, so that alternative routes could have been taken.

In the fourth 6x6 example the move e4-c3 (marked by a cross) does not conform to the rule, which requires e4-f6 as in the third 6x6 example. Similarly in Warnsdorf's 8x8 example there is a deviation from the rule at h5. The correct move should be to f4 which has access to only two exits whereas g7 and f6 have three. However these deviations only go to show the robustness of the rule, since in each case it still goes on to complete a tour.

Google Books useful in my Knight's Tour Research

I've recently found that some important and obscure texts on knight's tours are now available in Google Books. The following are links to four of them:

Warnsdorf 1823

http://books.google.co.uk/books?id=w5FZAAAAYAAJ&printsec=frontcover&dq=h.+c.+von+warnsdorf&hl=en&sa=X&ei=2QZmU9-jJIaXO8-hgKgL&ved=0CDEQ6AEwAA#v=onepage&q=h.%20c.%20von%20warnsdorf&f=false

Kafer 1842

http://books.google.co.uk/books?id=si1RAAAAcAAJ&printsec=frontcover&dq=Kafer+1842&hl=en&sa=X&ei=3nfbU9PFO8PE7AbEooGYDA&ved=0CCEQ6AEwAA#v=onepage&q&f=false

Perenyi 1842

http://books.google.co.uk/books?id=jf0UAAAAYAAJ&printsec=frontcover&dq=perenyi+1842&hl=en&sa=X&ei=dvtlU7fFNcGJPdbZgPgK&ved=0CDEQ6AEwAA#v=onepage&q&f=false

Jaenisch's Treatise 1862

http://books.google.co.uk/books?id=UMpUAAAAYAAJ&pg=PP11&dq=Jaenisch+Traite&hl=en&sa=X&ei=lfLKU-O-O-Se7Aau6YCwDA&ved=0CDAQ6AEwAw#v=onepage&q=Jaenisch%20Traite&f=false

A problem with the Warnsdorf and Kafer books is that the Google versions do not reproduce the figures!
However I found a copy of the Kafer sheet of diagrams elsewhere on the web, and I was able to obtain a copy of the Warnsdorf tours through the kindness of Cleveland Public Library, Ohio.
More on this subsequently.

There are probably may other titles to be found by a search in Google Books.
Kafer details added in update of this page 1 Aug 2014.

Google Rules the Web

Having received instructions from Virgin that my email address on virgin.net would no longer be accepted on Google sites from 7 May I have now changed the email I use for this purpose. I'm also using the Chrome browser to access Google sites, since they object to Internet Explorer. It seems that if you don't conform to what Google dictates these days you are an outcast on the web.

I also note that my Mayhematics home page now doesn't come out properly in Chrome. The six areas around my photo are supposed to be equal-sized squares, but some of them are now stretched out to the right. I suppose I will need to modify the HTML in some way.

Work on Hastings Pier goes ahead

I took this photo from the steps up to the White Rock path near Clambers.

Work so far is only on the front apron of the pier. The far end is still a ruin.

 

 

 

 

Warnsdorf Counterexample

In W. W. Rouse Ball's Mathematical Recreations and Essays (11th edition 1939, and probably earlier editions) states (p.181): "Warnsdorff [sic] added that when, by the rule, two or more cells are open to the knight, it may be moved to either or any of them indifferently. This is not so, and with great ingenuity two or three cases of failure have been constructed, but it would require exceptionally bad luck to happen accidentally on such a route." However he gives no reference to where work showing this was done, and diagrams no example of it. The diagrams shown here are the first cases I have encountered where the rule fails.

The choices of route available from f7 onwards all lead to a dead end, shown by the darker circle, that leaves two cells, marked by crosses, unvisited.

Another Two Warnsdorf Closed Tours

Continuing my enumeration I have found two more closed tours that follow the Warnsdorf rule and have only seven places where the rule allows two or more choices. These points of ambiguity are shown by the white circles.

The tours start at the black dot and end at the darker outlined circle (this is not a point of ambiguity). Perhaps the tours should properly be termed "re-entrant" since the move joining the end point to the first point is extra to the construction. Any link to the black dot in the course of the construction is prohibited since it would result in a closed circuit covering only part of the board. Alternative routes at the last ambiguity lead to open tours.

Two More Warnsdorf Closed Tours

Here are two more closed tours formed according to the Warnsdorf rule, with minimum of seven cells where there is an alternative route. In these tours there is no choice on the first move given the initial placement of the knight at d1.

These tours are not as symmetric as the previous example and differ from each other only in the choice of routes from f5. Other choices at e4 lead to open tours. This is part of work in progress. I've not yet enumerated all the solutions with 6 ambiguities, but have reached 540 incomplete paths with 5 ambiguous points.

Warnsdorf Tour Symmetrised

The Warnsdorf tour I published here a couple of days ago seemed remarkably symmetric compared with others of the type. So I thought I would see what it looks like when completely symmetrised.

This is done by deleting all moves that are not part of a symmetrically arranged pair - which leaves 52 moves in this case - and joining up the loose ends to make a symmetric closed tour. This can be done in two ways as shown here.

A Twissty Tour

I'm making considerable progress with putting together a book on History of Knight's Tours and Related Problems based on my Knight's Tour Notes web pages and other unpublished notes.
The knight's tour of a Circular Chess board shown here appears in Volume 2 of Chess by Richard Twiss published in 1789, although it is shown there by numbers entered on the board. I've had to curve some of the moves for clarity.

The details of this work were sent to me by the late Ken Whyld on 4 March 2002. Twiss reports having seen the round board in a manuscript in the Cotton collection. The text reads: "The figures on this board (in the plate) show the march of the Knight in order to cover the sixty-four squares in as many moves. This I found after four or five hours trial on a slate at different times; it probably has never been done before, and will be found much more regular than any of the like marches on the square board." The visual form is certainly much more striking than the numerical version!

A Warnsdorf Tour with Minimum Ambiguity

In his 1823 book H. C. von Warnsdorf published a rule for constructing a knight's tour of the chessboard. This was to place the knight on any cell and to move it always to a cell from which it has the fewest exits (to cells not yet used). If there are two or more cells with the same number of exits an ambiguity occurs and you may choose any of the moves with fewest exits.

I've not seen Warnsdorf's book, but it is cited in many later publications. There are copies listed in the catalogues of the British Library, the Cleveland Public Library (USA) and the Koninklijke Bibliotheek (Netherlands). I also found a copy for sale on ABE Books from a dealer in Italy who was asking over £500.

I have been making an enumeration of Warnsdorf tours on the 8 by 8 board by hand with diagrams drawn on a computer. I suspect someone must have done it using a computer program, but I've not seen any results published. So far I've reached the fifth ambiguity and 255 diagrams.

Taking a couple of the more promising diagrams I have followed them through to the seventh or eighth ambiguity, and the tour shown here is the first closed tour I have found. So this probably has the minimum ambiguities (shown by the white cells). I don't count the initial move d4-c2 as an ambiguity, since the choice d4-b3 would merely reflect the tour in the diagonal.

I should have mentioned that d4-e2 (and its reflection d4-b5) is an alternative first move, leading to different tours. So perhaps d4 should be counted as an ambiguity as well.