頭條新聞

棋盤上不存在幻方騎士巡邏

作者：Eric W. Weisstein

2003年8月6日——經過 61.40 天的計算，一個有 150 年曆史的未解決的問題終於得到了解答。這個問題涉及在一個空的編號為 8 x 8 的棋盤上，騎士可以走出的路徑是否存在。

回顧一下，騎士可以走“L”形步法，即在一個方向上偏移一格，在垂直方向上偏移兩格。現在讓騎士在一個 n x n 的棋盤上移動，棋盤上的方格沿騎士的路徑從 1 到 n² 編號，即初始方格標記為“1”，騎士觸及的第二個方格標記為“2”，依此類推。如果這條路徑恰好訪問每個方格一次，則稱為巡邏。上面的圖表說明了 8 x 8 棋盤上的六種騎士巡邏。

騎士巡邏中產生的數字陣列還可以滿足許多有趣的性質。特別是，考慮一個稱為幻方（或有時稱為“對角幻方”）的數字陣列，上面展示了一個。如果一個 n x n 的數字陣列（數字從 1 到 n²）中，每行、每列和對角線的數字之和都為一個相同的數字（稱為該幻方的幻和），則稱其為幻方。例如，在上圖中，幻和為 15。如果一個方陣未能成為完全幻方，僅僅是因為其對角線未能求和為幻和（但其行和列求和為幻和），則稱為半幻方。

毫不奇怪，如果騎士巡邏產生的數字排列形成幻方，則稱為幻方巡邏；如果產生的數字排列是半幻方，則稱為半幻方巡邏。長期以來，人們都知道，對於 n 為奇數的 n x n 棋盤，不可能存在幻方騎士巡邏。人們也知道，對於所有尺寸為 4k x 4k（k > 2）的棋盤，這種巡邏是可能的。然而，雖然在常見的 8 x 8 棋盤上已知存在許多半幻方騎士巡邏，包括上面所示的那些，但不知道在 8 x 8 棋盤上是否存在任何完全幻方巡邏。

這個長期存在的開放性問題現在已經透過對所有可能性的詳盡計算機列舉得到了否定性的解決。用於計算的軟體由 J. C. Meyrignac 編寫，網站http://magictour.free.fr 由 Guenter Stertenbrink 建立，用於分發和收集所有可能巡邏的結果。經過 61.40 個 CPU 日（相當於以 1 GHz 執行 138.25 天的計算），該專案於 2003 年 8 月 5 日完成。結果是什麼？除了獲得了總共 140 種不同的半幻方騎士巡邏之外，計算首次證明了不可能存在 8 x 8 幻方騎士巡邏，從而最終解決了這個長期存在的開放性問題。