騎士巡邏

维基百科，自由的百科全书
跳转至： 导航、 搜索
點撃這裡即可觀看騎士巡邏的動態影像

騎士巡邏是一個數學問題：將一個國際象棋的騎士（或稱馬）放在棋盤上，有甚麼路徑能使它走遍棋盤上每一格呢？

假若騎士能夠從最後位置合法地走到最初位置，則稱此巡邏為「封閉巡邏」，否則，稱為「開巡邏」。對於8*8棋盤，一共有26,534,728,821,064 種封閉巡邏。到底有多少種開巡邏仍舊是未解決的問題。[1][2][3]

在九世紀的古印度恰圖蘭卡就有出現使用半個8*8棋盤的騎士巡邏棋謎[4]。問題的變化包括用不同大小的棋盤，及一種以此問題為基礎的兩人遊戲。許多數學家曾鑽研此問題，包括歐拉。

這問題是在圖論裏的哈密頓路徑問題的特別案例。

參考資料 [编辑]

  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.  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. 
  3. ^ Wegener, I. Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. 2000. ISBN 0-89871-458-3. 
  4. ^ Chess for Beginners

外部連結 [编辑]

来自“http://zh.wikipedia.org/w/index.php?title=騎士巡邏&oldid=25374182”