維基百科

騎士巡邏

騎士巡禮（英語：Knight's tour）是指在按照西洋棋中騎士的規定走法走遍整個棋盤的每一個方格，而且每個網格只能夠經過一次。假若騎士能夠從走回到最初位置，則稱此巡禮為「封閉式巡禮」，否則，稱為「開放巡禮」。對於8*8棋盤，一共有26,534,728,821,064種封閉巡禮，有19,591,828,170,979,904種開放式巡禮。[1][2][3]

一種開放式巡禮走法
5×5棋盤中的一種開放式巡禮走法

由騎士巡禮引申出了一個著名的數學問題 ：騎士巡禮問題--找出所有的騎士巡禮路徑。編寫一個程式來找出騎士巡禮路徑經常在電腦系的學生的練習中出現。騎士巡禮問題的變種包括各種尺寸的棋盤甚至非正方形的棋盤。

歷史

 
土耳其行棋傀儡執行的騎士巡邏。由於其路線是一條閉路，因此從棋盤上任何一點開始都能完成巡邏。[4]

已知的最早的騎士巡邏問題可以追溯到九世紀的古印度恰圖蘭卡。[5]

歐拉是最早研究騎士巡邏的數學家中的一員，而H·C·馮·汪斯道夫（H. C. von Warnsdorff）在1823年提出了第一個系統化解決騎士巡邏問題的方法——汪斯道夫規則。

在20世紀，一批烏力波的作家將這個問題用在了其它的地方。最明顯的例子：喬治·佩雷克的小說《人生使用法（英語：Life: A User's Manual）》的章節順序就是按照10×10棋盤的騎士巡邏路徑來編排的。在2010年西洋棋世界冠軍對抗賽的第六場比賽中，棋手維斯瓦納坦·阿南德連續13次移動騎士（使用了兩個騎士），線上評論員打趣地說阿南德試圖在遊戲過程中解決騎士巡邏問題。

實質

 
騎士巡邏圖展現了所有可能的騎士巡邏路徑，節點上的數字表示在這個節點上騎士可能路徑的個數

騎士巡邏問題實際上是哈密頓路徑問題的一種特殊形式，尋找騎士巡邏的閉巡邏路徑的個數實際上也是哈密頓迴圈問題的一種特殊形式。但是和一般的哈密頓路徑問題不同，騎士巡邏問題可以在線性時間內解決。[6]

路徑的個數

  • 在一個8×8的棋盤中，有26,534,728,821,064中有向封閉巡邏路徑（相互對稱的巡邏路徑被視為不同的巡邏路徑）。[7][3]
  • 在6×6的棋盤中，共有9862個閉巡邏。[8]
  • 8×8棋盤中開巡邏的個數為19,591,828,170,979,904。對於 （n=1，2……）的棋盤中開巡邏的個數是：
1, 0, 0, 0, 1728, 6637920, 165575218320,19591828170979904,……（  A165134）
  • Schwenk證明了，除了以下3種情況外，任何的m×n（m n）棋盤都至少有1個閉巡邏，。[9]
  1. m和n都為奇數
  2. m= 1, 2, 4
  3. m= 3且n= 4, 6, 8
  • Cull和Conrad證明了對於任何一個m×n（5 m n）棋盤，至少有一個（可能是開巡邏）騎士巡邏路徑。[10][6]

解決方法

 
利用類神經網路的方法在24 × 24的棋盤中尋找到的一條閉巡邏。

藉助電腦的幫助，人們已經發現了很多種尋找騎士巡邏路徑的方法。其中一部分依靠演算法，而另外一些則依靠啟發法。

窮舉法

用窮舉法來尋找騎士巡邏路徑適用于格數較小的棋盤，因為當方格數過多時，可能的路徑過多。例如，8×8棋盤中大約有4×10^51種可能的路徑。[11]如此大的運算量已經超出了現代電腦的運算能力。

分治法

利用分治法將棋盤分成很多小塊，計算出每一小塊中的所有可能路徑，然後將這些小塊合併再計算所有可能的路徑。

類神經網路方法

騎士巡邏問題同樣可以使用類神經網路來解決。[12]

汪斯道夫規律

汪斯道夫規律指在所有可走且未經過的方格中，騎士只可能走這個方格：從該格出發，騎士能跳的方格數最少；如果可跳的方格數相等，則從當前位置看，方格序號小的優先。依照這一規律往往可以找到一條路徑但並不一定能夠成功。

參考資料

  1. ^ Martin Loebbing; Ingo Wegener. The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams. The Electronic Journal of Combinatorics. 1996, 3 (1): R5 [2012-12-20]. （原始內容存檔於2012-01-22）.  （頁面存檔備份，存於網際網路檔案館） Remark: The authors later admitted （頁面存檔備份，存於網際網路檔案館） that the announced number is incorrect. According to McKay's report, the correct number is 13,267,364,410,532 and this number is repeated in Wegener's 2000 book.
  2. ^ Brendan McKay. Knight's Tours on an 8x8 Chessboard. Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University). 1997. （原始內容存檔於2012-01-27）.  （頁面存檔備份，存於網際網路檔案館）
  3. ^ 3.0 3.1 Wegener, I. Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. 2000. ISBN 0-89871-458-3. 
  4. ^ Standage, 30–31.
  5. ^ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhitraversal: Parimal Sanskrit Series No. 30. 
  6. ^ 6.0 6.1 Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. Solution of the Knight's Hamiltonian Path Problem on Chessboards. Discrete Applied Mathematics. 1994, 50 (2): 125–134. doi:10.1016/0166-218X(92)00170-Q. 
  7. ^ Brendan McKay. Knight's Tours on an 8x8 Chessboard. Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University). 1997 [2014-03-24]. （原始內容存檔於2013-09-28）.  （頁面存檔備份，存於網際網路檔案館）
  8. ^ Weisstein, Eric W. (編). Knight's Tour. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）. 
  9. ^ Allen J. Schwenk. Which Rectangular Chessboards Have a Knight’s Tour?. Mathematics Magazine. 1991: 325–332. 
  10. ^ Cull, P.; De Curtins, J. Knight's Tour Revisited (PDF). Fibonacci Quarterly. 1978, 16: 276–285 [2014-03-24]. （原始內容存檔 (PDF)於2016-04-19）.  （頁面存檔備份，存於網際網路檔案館）
  11. ^ Enumerating the Knight's Tour. 
  12. ^ Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.

外部連結

取自「https://zh.wikipedia.org/w/index.php?title=騎士巡邏&oldid=82532379」