## 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 long-standing 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 August 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 |