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

knight's tour





knight's tour
The earliest known knight's tour
The knight's tour is 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 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