主題
Search

魔術巡遊


讓一個棋子在 n×n 棋盤上進行巡遊,棋盤上的方格按照棋子路徑從 1 到 n^2 編號。如果由此產生的數字排列是幻方,則稱此巡遊為魔術巡遊;如果由此產生的數字排列是半幻方,則稱此巡遊為半魔術巡遊。如果第一個和最後一個走過的方格透過一步棋相連,則稱此巡遊為封閉的(或“重入的”);否則它是開放的。(請注意,術語需要謹慎。例如,Jelliss 將半魔術巡遊稱為“魔術巡遊”,將魔術巡遊稱為“對角魔術巡遊”。)

魔術騎士圖巡遊在 n×n 棋盤上對於 n 奇數是不可能的。然而,眾所周知,對於所有大小為 4k×4k 的棋盤(其中 k>2),這是可能的。然而,n=8 (k=2) 的情況仍然懸而未決,即使自 Beverley (1848) 等作者首次研究以來也是如此。直到 2003 年 8 月 5 日完成對所有可能性的詳盡計算機列舉後,這個問題才得到解決(Stertenbrink 2003)。這項搜尋需要耗費 61.40 CPU 日的詳盡計算,相當於在 1 GHz 下計算 138.25 天。

MagicTourKnights8Semimagic

Beverley (1848) 創作了 8×8 半魔術騎士巡遊(左圖)。de Jaenisch (1862;Ball 和 Coxeter 1987,第 185 頁;中心圖) 發現了另一個 n=8 的半魔術巡遊,其主對角線和分別為 348 和 168。8×8 棋盤上已知的“最魔術”騎士巡遊的主對角線和分別為 264 和 256,如右圖所示 (Francony 1882)。Murray (1951) 和 Jelliss 給出了騎士魔術巡遊的廣泛歷史。總共有 140 種不同的 8×8 棋盤上的半魔術騎士巡遊 (Stertenbrink 2003)。

MagicTourKnightsHalfBoards

如上圖所示,將兩個半騎士巡遊上下組合可以得到一個幻方 (Ball 和 Coxeter 1987,第 185 頁)。

MagicTourKnights16

上圖顯示了一個 16×16 棋盤上的封閉魔術騎士圖巡遊 (Madachy 1979,第 88 頁)。

MagicTourKing

上圖展示了國王走法的魔術巡遊 (Ball 和 Coxeter 1987,第 186 頁)。


另請參閱

棋盤, 騎士圖, 幻方, 半幻方, 巡遊

使用 探索

參考資料

Ball, W. W. R. 和 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/.Update a linkJelliss, G. "Knight's Tour Notes." http://home.freeuk.net/ktn/Update a linkJelliss, 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." Headline News, Aug. 6, 2003. https://mathworld.tw/news/2003-08-06/magictours/.Wenzelides, C. Schachzeitung, p. 247, 1849.

在 中引用

魔術巡遊

引用為

Weisstein, Eric W. “魔術巡遊”。來自 —— 資源。 https://mathworld.tw/MagicTour.html

主題分類