Here is a letter I received some time ago from George Jelliss whom I regard as
the 21st century expert on Knight Tours. George's letter is in response to my very
first Knight's Tour. He has written quite a few excellent articles on chess and has
compiled an immense amount of data on Knight Tours. -- D. Thomasson
Dear Dan,
Thanks for the clarification. I see what you're getting at now. Your claim is that
your Rule produces a unique tour. However I'm afraid I have to say I think you're
cheating a little bit, for the following reasons.
1. At cell 25 (c6) if "moving on the outermost squares" means those farthest
from the centre of the board (measured to the centre point of the square) then
you should go to cell 56 (a7) not to cell 26 (a5). This move does continue the
unidirectional rotation (i.e. rotation of the line from centre of board to knight),
though only just. Continuing with your rule after substituting this move leads
round the board to c8 where a backward rotation c8-d6 is forced.
2. If we allow the above diversion to be backtracked to c6 and take the next
choice of move, to a5, then your route is again followed, but at cell 43 your
Rule, under my interpretation of rotation, requires the knight to go to cell
50 (h2), and this again leads after a circuit of the board to a backward
rotation (f1-e3).
The rule "Keep as far from the centre of the board as possible" was claimed by
Charles Tomlinson in Amusements in Chess 1845 (p.124) to produce a tour, but
the tour he gives violates the rule at one point.
It is in fact possible to devise rules that will produce an exact tour, without
deviation from the rule at any point, and without backtracking. In Chessics #22
(1985) I gave four examples of such "Synthetic Tours". They use Warnsdorff's rule
("Play the knight to a square where it commands the fewest squares not yet used")
in conjunction with either the Obtuse rule ("Play the knight at as obtuse an angle
as possible to the previous move - straight if possible") or the Acute rule
("Play the knight at as acute an angle as possible to the previous move"). The
second rule either takes over when Warnsdorff's rule breaks down (I write these
rules WO and WA), or the second rule is applied to the choice of moves suggested
by the first rule (I write these rules W/O and W/A). The four combination rules all
work if the tour is started a1-b3.
I've run out of web-space on my Stayfree site, so I shall be moving the Knight's
Tour Notes to a new site some time soon. I still have masses of material to be
included. I'll let you know when the new address is up and running.
Best Wishes,
George Jelliss
5 July 2001
Below is a letter from a computer science student who found Knight Tours relevant
to his research. My response follows.
Mr. Thomasson,
I am a computer science student at RIT (Rochester Institute of Technology).
I am doing an Artificial Intelligence project on the Knight's Tour.
My project requires that I implement an algorithm of type A*.
That is just a fancy term for implementing a search algorithm with some heuristics.
Your mathematical analysis would help me tremendously in designing a heuristic
to accompany my search algorithm. In case you are wondering I am using a
best-first search algorithm. The goal is to see if I can make a piece of
software learn the pattern that you devised. However, the trick will be
that the software also be intelligent enough to find an answer from anywhere
on the board.
Thank you,
Frank Pickering
October 13, 2001
Frank,
Having a known repeatable pattern makes the job quite easy. If you use
the number pairs (1/48, 2/47, 3/46, ..., 17/64, 18/63, 19/62, ...) you only
have to cover every other square with 1-16, then making sure that 1/48 can
connect to 49/32 which connects to 16/33 which connects to 17/64. All other
numbers fall in place automatically. The only problem with this method, you
seldom will end up with a closed knight's tour, just an open knight's tour.
I know there are 64 squares on a regular chessboard. If each square is assigned
a number from 1-64 covering all 64 numbers, they would add up to 2080 total.
I want each quadrant to add up to 520. I also want each row and column in each
quadrant to add up to 130. I know that if I take (1+64) + (2+63) they add up to
130. If I repeat the pattern, I will end up with a method for putting four
numbers together that all add up to 130 for each row in a quadrant. However,
this method does not yield a complete knight tour sequence because of the 32/33
number pair. In order to create the number pairs to make knight move sequences,
I use the same method but modify it just a little. I will show you both.
Now I am able to use these numbers to create a knight's tour. When you look at
my webpage at
www.BordersChess.org/KnightTour.htm you will see a couple ways
I used the numbers to create the Knight's Tour Art and the Semi-Magic Square Knight
Tours.
When all is said and done, the number pairs make it easy to create knight tours,
but maybe not so easy to programmatically create heuristic algorithms. On the other
hand, using the matching patterns is quite easy. I will send you an example:
Start from the top left quadrant and make all forward leaning diamond shape moves
around the board. If you look at the top left 64 square chessboard, using algebraic
notation, start with the following move sequence: d8, b7, a5, ... etc. Then from
the top left quadrant, make square shape moves around the board. Then use the
opposite diamond shape pattern starting from the second top left quadrant and move
around the board backwards. Finally, finish the moves by making square shape
patterns in reverse around the board. If this is all confusing, simply follow the
pattern I'm sending you. The same idea will work on 64 squares or thousands of
squares equally divisible by 8.
