# Ivars Peterson's MathTrek

October 6, 2003

## A Magic Knight's Tour

For as long as chessboards have existed, there have been puzzles involving chessboards and chess pieces. Some of the most enduring conundrums have involved knights.

According to the rules of chess, a knight makes an L-shaped move that shifts its position by a single square in one direction and two squares in a perpendicular direction. Indeed, the knight is the only chess piece that covers an asymmetrical pattern of squares.

One of the most venerable of chess puzzles is that of the knight's tour: Following the rules of chess, is it possible for a knight to tour a chessboard in such a way that it visits each square of the board exactly once?

Such problems intrigued Leonhard Euler (1707–1783), and he spent some time working on this puzzle and its generalization to boards of different sizes and shapes. Many others have followed in his footsteps.

It turns out there's a huge number of different knight's tours of a standard chessboard. In some cases, the knight ends up just a knight's move away from its initial starting position.

If the successive squares that a knight visits are numbered from 1 to 64, in order, and the numbers form a magic square, the path is called a magic tour. A magic square is a square array of numbers such that each row and column and the two main diagonals sum to the same number (the magic constant).

Knight's tours in which the rows and columns sum to the same number but the diagonals do not are known.

Example of a knight's tour in which the rows and columns have the same sum (260), but the diagonals add up to 348 and 168.

The question remains: Are there are any fully magic knight's tours of the standard chessboard?

No one was sure of the answer until last summer, when a team used computers to check all the relevant possibilities and concluded that there are no magic knight's tours on an eight-by-eight chessboard (see http://magictour.free.fr/). The team did find a total of 140 distinct "semimagic" tours in which just the rows and columns have the same sum.

Interestingly, magic knight's tours are not possible on n x n boards, when n is odd. They are possible for all boards of size 4k x 4k, for k greater than 2.

Chess pieces and chessboards lend themselves to all sorts of puzzles and mathematical investigations. A few years ago, for example, there was a flurry of attention paid to knight coverings for large chessboards. The problem was how to cover a chessboard with the smallest number of knights so that every square on the board is either occupied by a knight or attacked by a knight.

For this puzzle, the optimal solutions for boards of sizes 3 x 3 to 10 x 10, along with 12 x 12 and 13 x 13, have been known since the 19th century. The best solution for 11 x 11 was found in 1973 and the best one for 14 x 14 in 1977. In 2000, Frank Rubin found good solutions for boards as large as 26 x 26 (see http://www.contestcen.com/knight.htm).

And there's much more, especially involving knights and standard chessboards.

"Mathematically, the choice of (2,1) and of the 8 x 8 board may seem to be a special case of no particular interest," Noam D. Elkies and Richard P. Stanley wrote in a recent Mathematical Intelligencer article. "But long experience points to the standard knight's move and chessboard size as felicitous choices not only for the game of chess but also for puzzles and problems involving the board and pieces."

References:

Elkies, N.D., and R.P. Stanley. 2003. The mathematical knight. Mathematical Intelligencer 25 (No. 1):22-34.

Gardner, M. 1990. Knights of the square table. In Mathematical Magic Show. Washington, D.C.: Mathematical Association of America.

Kumar, A. 2003. In search of perfect magic tour of knight on 12 x 12 board. Games and Puzzles Journal (April-June). Available at http://www.gpj.connectfree.co.uk/gpjh.htm.

Rubin, F. 2000. Knight coverings for large chessboards. Contest Center (Nov. 9). Available at http://www.contestcen.com/knight.htm.

Weisstein, E. 2003. There are no magic knight's tours on the chessboard. Eric Weisstein's World of Mathematics (Aug. 6). Available at http://mathworld.wolfram.com/news/2003-08-06/magictours/.

Knight's tour notes by George Jelliss can be found at http://www.ktn.freeuk.com/.

Information about computing magic knight tours is available at http://magictour.free.fr/.

Diagram of a knight's tour created using a Mathematica program developed by Eric Weisstein, Wolfram Research. See http://mathworld.wolfram.com/KnightsTour.html and http://mathworld.wolfram.com/MagicTour.html.

Various chessboard puzzles can be found at http://www.contestcen.com/chess.htm.