October 16, 2020

A Magic Knight's Tour

For as long as the game of chess has 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 2002, 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 "Computing Magic Knight Tours"). 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 while 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.

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 their article "The Mathematical Knight" in the Mathematical Intelligencer. "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."

Originally posted October 6, 2003

See also "Knight Moves in 3D."

No comments: