騎士巡邏
维基百科,自由的百科全书
點撃這裡即可觀看騎士巡邏的動態影像
騎士巡邏是一個數學問題:將一個國際象棋的騎士(或稱馬)放在棋盤上,有甚麼路徑能使它走遍棋盤上每一格呢?
假若騎士能夠從最後位置合法地走到最初位置,則稱此巡邏為「封閉巡邏」,否則,稱為「開巡邏」。對於8*8棋盤,一共有26,534,728,821,064 種封閉巡邏。到底有多少種開巡邏仍舊是未解決的問題。[1][2][3]
在九世紀的古印度恰圖蘭卡就有出現使用半個8*8棋盤的騎士巡邏棋謎[4]。問題的變化包括用不同大小的棋盤,及一種以此問題為基礎的兩人遊戲。許多數學家曾鑽研此問題,包括歐拉。
參考資料 [编辑]
- ^ 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.
- ^ Brendan McKay. Knight's Tours on an 8x8 Chessboard. Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University). 1997.
- ^ Wegener, I. Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. 2000. ISBN 0-89871-458-3.
- ^ Chess for Beginners
外部連結 [编辑]
- Knight's Tour Notes
- Knight's Tour(Javascript)
- JAVA:Knight's tour