Magic Tour

Let a chess piece make a tour on an  chessboard whose squares are numbered from 1 to  along the path of the chess piece. Then the tour is called a magic tour if the resulting arrangement of numbers is a magic square, and a semimagic tour if the resulting arrangement of numbers is a semimagic square. If the first and last squares traversed are connected by a move, the tour is said to be closed (or "re-entrant"); otherwise it is open. (Note some care with terminology is necessary. For example, Jelliss terms a semimagic tour a "magic tour" and a magic tour a "diagonally magic tour.")

Magic knight graph tours are not possible on  boards for  odd. However, as had long been known, they are possible for all boards of size  for . However, the  () remained open even since it was first investigated by authors such as Beverley (1848). It was not resolved until an exhaustive computer enumeration of all possibilities was completed on August 5, 2003 (Stertenbrink 2003). This search required an exhaustive 61.40 CPU-days, corresponding to 138.25 days of computation at 1 GHz.

Beverley (1848) composed the  semimagic knight's tour (left figure). Another semimagic tour for  with main diagonal sums of 348 and 168 was found by de Jaenisch (1862; Ball and Coxeter 1987, p. 185; center figure). The "most magic" knight's tour known on the  board has main diagonal sums of 264 and 256 and is shown on the right (Francony 1882). Extensive histories of knight's magic tours are given by Murray (1951) and Jelliss. In all, there are a total of 140 distinct semimagic knight's tours on the  board (Stertenbrink 2003).

Combining two half-knights' tours one above the other as in the above figure gives a magic square (Ball and Coxeter 1987, p. 185).

The illustration above shows a closed magic knight graph tour on a  board (Madachy 1979, p. 88).

A magic tour for king moves is illustrated above (Ball and Coxeter 1987, p. 186).

---

REFERENCES

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 185-187, 1987.

Beverly, W. Philos. Mag. p. 102, Apr. 1848.

de Jaenisch, C. F. Chess Monthly. 1859.de Jaenisch, C. F. Traite des Applications de l'Analyse Mathematiques au jeu des Echecs. Leningrad, 1862.

Francony. In Le Siécle 1876-1885. (Ed. M. A. Feisthamel). 1882.

Friedel, F. "The Knight's Tour." http://www.chessbase.com/columns/column.asp?pid=163.Heinz, H. "Magic Tesseract." http://members.shaw.ca/tesseracts/.Jelliss, G. "Knight's Tour Notes." http://home.freeuk.net/ktn/Jelliss, G. "General Theory of Magic Knight's Tours." http://home.freeuk.net/ktn/mg.htmKraitchik, M. l'Echiquier. 1926.

Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, pp. 87-89, 1979.

Marlow, T. W. The Problemist. Jan. 1988.

Murray, H. J. R. The Magic Knight's Tours, a Mathematical Recreation. 1951.

Peterson, I. "MathTrek: A Magic Knight's Tour." Oct. 4, 2003.

 http://www.sciencenews.org/20031004/mathtrek.asp.Roberts, T. S. The Games and Problems J. Jan. 2003.

Stertenbrink, G. "Computing Magic Knight Tours." http://magictour.free.fr/. Aug. 6, 2003.

Watkins, J. Across the Board: The Mathematics of Chessboard Problems. Princeton, NJ: Princeton University Press, 2004.

Weisstein, E. W. "There Are No Magic Knight's Tours on the Chessboard." MathWorld Headline News, Aug. 6, 2003.

 http://mathworld.wolfram.com/news/2003-08-06/magictours/.Wenzelides, C. Schachzeitung, p. 247, 1849.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength