Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

knight's tour





knight's tour
The earliest known knight's tour
A classic chess puzzle: to find a sequence of moves by which a knight can visit each square of a chessboard exactly once. If the final position is a knight's move away from the first position, the tour is said to be 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