騎士巡邏

騎士巡邏（英語：Knight's tour）啊是講咧按照西洋棋中騎士的規定行法行透透規个棋盤每一个方格，而且逐个網格干焦會當經過一擺。假的人若騎會當對行轉來上早位置，是按呢巡邏為著「封閉巡邏」，抑無，這號做「開巡邏」。 對八來講 \ * 八棋盤，攏總有二十六 , 五百三十四 , 七仔二八 , 八百二十一 , 六十四種封閉巡邏，有十九 , 五百九十一 , 八百二八 , 一百七十 , 九百七十九 , 九百空四種開巡邏。

由騎士巡邏引申出一个出名的數學問題：騎士巡邏的問題--揣出所有的騎士巡邏路徑。編寫一个程式來揣出騎士巡邏路徑定定佇電腦系的學生的練習內底出現。騎士巡邏問題的變種包括各種 sài-sù 的棋盤甚至非常四角形的棋盤。

歷史

已知的上早的騎士巡邏問題會當追溯到九世紀的古印度恰圖蘭卡。

歐拉是上早研究騎士巡邏的數學家內底的一員，而且 H ・ C ・ 馮 ・ 汪斯道夫（H . C . von Warnsdorff）佇一八二三年提出頭一个系統化解決騎士巡邏問題的方法—— 汪斯道夫規則。

佇彼个二十世紀，一批烏力波的作家將這个問題用佇咧其他的所在。上明顯的例：喬治 ・ 佩雷克的小說《Life : A User's Manual》的章節順序就是按照十 × 十棋盤的騎士巡邏路徑來編排的。佇二空一空年西洋棋世界冠軍嘿抗賽的第六場比賽中，棋手維斯瓦納坦 ・ 阿南德連紲十三擺徙動騎士（使用兩个騎士）， 線頂評論員拍趣味的講阿南德試圖佇咧遊戲過程當中解決騎士巡邏的問題。

實質

騎士巡邏問題實際上是哈密頓路徑問題的一種特殊形式，走揣騎士的巡邏路徑的數實際上嘛是哈密頓迴圈問題的一種特殊形式。但是佮一般的哈密頓路徑問題無仝，騎士巡邏問題會當佇線性時間內解決。

路徑的數

• 佇一个八 × 八的棋盤內底，有二十六 , 五百三十四 , 七仔二八 , 八百二十一 , 六十四中有向封閉巡邏路徑（互相對稱的巡邏路徑予人看做無仝款的巡邏路徑）。
• 佇六 × 六的棋盤當中，計共是九千八百六十二个閉思。
• 八 × 八棋盤中開巡邏的個數為十九 , 五百九十一 , 八百二八 , 一百七十 , 九百七十九 , 九百空四。對於 $ n \ times n $（_ n _=一，二……）的棋盤中開巡邏的個數是：

一 , 零 , 零 , 零 , 一千七百二十八 , 六百六十三石七千九百二十 , 一千六百五十五鋪七千五百二十一鋪八千三百二十 , 19591828170979904 ,……（ A 十六曲五千一百三十四）

• Schwenk 證明矣，除了是以下三種情形以外，任何的 m×n（m $ \ leq $ n）棋盤攏上無有一个閉思巡邏，。

一 . m 和 n 攏為奇數二 . m=一 , 二 , 四三 . m=三而且 n=四 , 六 , 八

• Cull 和 Conrad 證明矣對任何一个 m×n（五 $ \ leq $ m $ \ leq $ n）棋盤，上無有一个（可能是開巡邏）騎士巡邏路徑。

解決方法

藉助電腦的這个幫助，人發現了真濟種走揣騎士的巡邏路徑的方法。其中一部份靠演算法，毋過另外一寡對啟發法來講。

散舉法

用散舉法來走揣騎士巡邏路徑適用于格數較細的棋盤，因為彼方格數傷濟的時陣，可能的路草傷濟。比如講，八 × 八棋盤內底大約有四 × 十 ^ 五十一種可能的路徑。遮爾大的運算量已經超出現代電腦的運算能力。

分治法

利用分治法將棋盤分做真濟細塊，計算出每一細塊仔內底的所有可能路徑，然後共遮的細塊敆做伙閣共算所有可能的路徑。

人工神經網路方法

騎士巡邏的問題仝款會當使用人工神經網路來解決。

汪斯道夫規則

汪斯道夫規則指佇所有會當行而且無經過的方格中，馬只可能行按呢一个方格：對該方格出發，馬能跳的方數上少；若會當跳的方格數相等，著對當時的位置看，方格序號細的優先。依照這規則往往會當揣著一條路徑毋過並無一定會當成功。

外部連結

• Knight's Tour Notes
• Knight's Tour ( Javascript )
• JAVA：Knight's tour