引言：什麼是騎士巡邏？

「騎士巡邏」（Knight’s Tour）是近期大熱韓國燒腦真人秀《魔鬼的計謀》（The Devil's Plan）中的一項單人挑戰，其複雜的移動規則和對策略思維的極高要求，讓許多觀眾印象深刻。想了解節目中參加者們是如何絞盡腦汁，試圖解開這個經典謎題的嗎？或者，您也想親自挑戰，掌握其中的奧秘？Search & Match 為您深入剖析騎士巡邏的解決之道！

騎士巡邏本身是一個古老而有趣的數學謎題。目標是讓西洋棋中的「騎士」（馬）在棋盤上移動，並且訪問棋盤上的每一個格子，且每個格子只能訪問一次。如果騎士的最後一步能夠跳回起點，則稱為「封閉巡邏」(Closed Tour)；否則，稱為「開放巡邏」(Open Tour)。

這個謎題不僅考驗邏輯思維，也是一個很好的演算法和啟發式策略練習。讓我們一起探索如何攻克它吧！

基本規則和騎士的移動方式

騎士的移動方式非常獨特，它總是走「L」形：先朝一個方向（上下左右）走兩格，然後再朝著垂直方向走一格；或者先走一格，再朝垂直方向走兩格。

簡單來說，如果騎士在座標 (x, y)，它下一步可能到達的8個座標有：

• (x+1, y+2), (x+1, y-2)
• (x-1, y+2), (x-1, y-2)
• (x+2, y+1), (x+2, y-1)
• (x-2, y+1), (x-2, y-1)

當然，騎士的每一步都必須落在棋盤的邊界之內。

通用解決策略：Warnsdorff's 規則 (華斯道夫規則)

為什麼這個規則有效？

這個策略的目的是避免騎士過早地將自己困在棋盤的某個區域，或者孤立掉一些難以到達的格子。通過優先處理那些選擇性較少的格子（通常是靠近邊緣或角落的格子，或者周圍已被訪問較多的格子），騎士能更有機會在之後處理那些選擇性較多的格子（通常是棋盤中心區域），從而更容易完成整個巡邏。

Warnsdorff's 規則的步驟：

1. 選擇起點： 從棋盤上的任意一個未訪問過的格子開始。
2. 查看下一步： 找出從當前騎士位置所有合法的下一步可以到達的、且尚未訪問過的格子。
3. 計算出口數： 對於每一個合法的下一步（我們稱之為「候選格」）：
   • 假設騎士移動到了這個「候選格」。
   • 計算從這個「候選格」出發，再下一步有多少個合法的、且尚未訪問過的格子可以選擇。這個數量就是該「候選格」的「出口數」。
4. 做出選擇： 從所有「候選格」中，選擇那個「出口數」最少的格子，作為騎士的下一步。
5. 處理平局 (Tie-breaking)： 如果有多個「候選格」的出口數並列最少：
   • 最簡單的方式是隨機選擇其中一個。
   • 另一種常見的策略是，如果有預設的棋盤格子掃描順序（例如，從上到下，從左到右），則選擇第一個遇到的出口數最少的格子。
   • 對於您的遊戲，由於玩家是手動操作，可以讓玩家自行判斷。遊戲中的「輔助開關」其實就是顯示了所有合法的下一步，玩家可以基於此規則自行計算和選擇。
6. 重複： 標記新的格子為已訪問，並重複步驟 2-5，直到棋盤上所有格子都被訪問完畢，或者沒有合法的下一步可以走（這種情況下，如果格子未走完，則表示該次嘗試失敗）。

優點與注意事項：

• 高成功率： Warnsdorff's 規則在尋找騎士巡邏路徑方面非常有效，尤其是在 5x5 及更大的棋盤上。
• 啟發式方法： 它是一種「啟發式」規則，意味著它提供了一個很好的指引，但並非 100% 保證在所有情況下都能找到解（儘管失敗的情況很少見）。
• 開放巡邏： 這個規則主要用於尋找「開放巡邏」。能否形成「封閉巡邏」取決於起點和最後一步的情況。

針對不同棋盤尺寸的提示

Warnsdorff's 規則適用於各種尺寸的棋盤。以下是一些針對常見尺寸的額外提示：

5x5 棋盤 (25格)

5x5 棋盤相對較小，使用 Warnsdorff's 規則通常很容易找到解。記住，騎士每走一步，其所在格子的顏色會改變 (黑到白，或白到黑)。由於總格數是奇數，如果騎士從某種顏色的格子開始，走完24步到達第25格時，第25格的顏色必定與起點顏色不同。因此，5x5 棋盤（以及所有邊長為奇數的棋盤）不可能存在回到起點的「封閉巡邏」。

提示：從角落或邊緣的格子開始，往往能讓 Warnsdorff's 規則的選擇更明確。

6x6 棋盤 (36格)

Warnsdorff's 規則在 6x6 棋盤上同樣有效。總格數為偶數。

提示：當有多個出口數相同的選擇時，嘗試選擇一個能讓騎士朝向棋盤上「未開發區域」或「格子密集區域」的路線。

(由於6x6及更大棋盤的路徑圖較為複雜，建議您親自使用 Warnsdorff's 規則，並配合遊戲中的輔助功能進行推演，更能體會其奧妙。)

7x7 棋盤 (49格)

總格數為奇數。

提示：隨著棋盤變大，嚴格執行 Warnsdorff's 規則變得更為重要。避免被棋盤的對稱性所迷惑，而做出非最優選擇。

8x8 棋盤 (64格)

標準的西洋棋棋盤，Warnsdorff's 規則在此表現極佳。8x8 棋盤存在許多封閉巡邏的解。

提示：在 8x8 棋盤上，如果嚴格遵循 Warnsdorff's 規則，尤其是在平局時做出合理的選擇（例如，優先選擇離棋盤中心更遠的格子，或者按照固定順序選擇），通常都能成功。

其他實用技巧和思考方式

• 避免過早填充中心： 棋盤中心的格子通常有最多的出口。如果太早把中心的格子都走完，可能會使得騎士在後期難以到達邊緣或角落的格子。Warnsdorff's 規則會自然地引導您避免這種情況。
• 特別留意邊角： 角落的格子只有2個出口，邊緣非角落的格子有3或4個出口。這些是棋盤上最受限的區域，需要優先考慮或小心處理，避免它們在遊戲後期被孤立。
• 保持對稱性，尋找關鍵回合： 在遊戲初期，可以嘗試遵循棋盤的對稱性來填補外圍格子。然而，要破解騎士巡邏的精髓，往往需要在某些「關鍵回合」進行「逆向操作」。這意味著，當你意識到目前的順時針或對稱策略可能會將你引向死胡同時，需要果斷地選擇一個看似不那麼直接、但能打開新路徑的步法。
• 先填補外圍，再思考中央： 一種有效的策略是先有意識地填補棋盤的外圍區域，將那些出口較少的格子走掉。這樣可以避免這些外圍格子在後期被孤立。當外圍大部分被填補後，中間區域的選擇性會相對較多，有更多的空間和時間來思考最佳路徑。
• 「封鎖」思考： 當您移動一步後，不僅要考慮下一步的選擇，也要思考您的移動是否「封鎖」了其他未訪問格子的潛在路徑，或者是否使得某些區域變得難以進入。
• 練習與觀察： 多加練習，觀察成功的路徑是如何形成的。您可以嘗試從不同的起點開始，看看路徑有何不同。熟悉騎士的移動模式是關鍵。
• 利用輔助工具： 您的遊戲中提供的「輔助開關」能顯示所有合法的下一步，這是實踐 Warnsdorff's 規則的絕佳工具。您可以手動計算每個合法下一步的「出口數」。

結論

騎士巡邏是一個充滿魅力的邏輯謎題。雖然沒有一種簡單的公式能適用於所有情況，但 Warnsdorff's 規則 提供了一個非常強大且可靠的策略來引導您的騎士完成巡邏。記住，耐心和細緻的觀察是成功的關鍵。

現在，打開您的騎士巡邏遊戲，嘗試運用今天學到的策略，祝您馬到成功，享受破解的樂趣！如果您對我們的服務或遊戲有任何疑問，也歡迎隨時聯絡 Search & Match。