No Magic Knight's Tours

Apparently they've solved the Magic Knight's Tours problem, using brute force. Enumerating every solution to a problem almost feels like cheating, especially if it doesn't lead to a deeper knowledge of the nature of simliar types of problems, but it's still cool.

Not surprisingly, a knight's tour is called a magic tour if the resulting arrangement of numbers forms a magic square, and a semimagic tour if the resulting arrangement of numbers is a semimagic square. It has long been known that magic knight's tours are not possible on n x n boards for n odd. It was also known that such tours are possible for all boards of size 4k x 4k for k > 2. However, while a number of semimagic knight's tours were known on the usual 8 x 8 chessboard, including those illustrated above, it was not known if any fully magic tours existed on the 8 x 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 the website http://magictour.free.fr 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. What are the results? In addition to netting a total of 140 distinct semimagic knight's tours, the computation demonstrated for the first time that no 8 x 8 magic knight's tour is possible, thus finally laying this long-open problem to rest.

The goal of this type of research is to eventually come up with a 'perfect' game strategy. For example, a pair of researchers form the Free University of Amsterdam solved the African game 'Awari', so that if you play their sequence of moves you will win every time. Now if only a computer could make me a better backgammon player :)

Tangentially-related chess puzzle: 8 queens problem (I solved it in 2 tries.)