## knight's tour
closed or reentrant.
The earliest recorded solution for a standard 8 × 8 chessboard was given by Abraham de Moivre; the earliest known reentrant solution came from the French mathematician Adrien-Marie Legendre (1752-1833). Not to be outdone Leonhard Euler found a reentrant tour that visits two halves of the board in turn. The problem can be generalized to an n × n board, with some
surprising results; for example, a reentrant tour is not possible on a 4
× 4 board. A knight's tour is called a magic tour if the resulting arrangement of numbers forms a magic square, and a semi-magic tour if the resulting arrangement
of numbers is a semi-magic square.
It has long been known that magic knight's tours aren't possible on n ×
n boards if n is odd. It was also known that such tours are possible for
all boards of size 4k × 4k for k > 2. However,
while a number of semimagic knight's tours were known on the usual 8 ×
8 chessboard, it was not known if any fully magic tours existed on the 8
× 8 board. This longstanding open problem has now been settled in the
negative by an exhaustive computer enumeration of all possibilities. The
software for the computation was written by J. C. Meyrignac, and a website
was established by Guenter Stertenbrink to distribute and collect results
for all possible tours. After 61.40 CPU-days, corresponding to 138.25 days
of computation at 1 GHz, the project was completed on Aug. 5, 2003. In addition
to netting a total of 140 distinct semimagic knight's tours, the computation
demonstrated for the first time that no 8 × 8 magic knight's tour is
possible. More magical and mysterious tours can be conducted on boards on the surfaces of cubes, cylinders, and toruses. ## Related entry• Hamilton path## Related category• GAMES AND PUZZLES | |||||||

Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact |