騎士巡邏問題：棋盤上「馬走日」的回溯算法實現

問題描述

在 n×m 棋盤上，將「馬」放置於指定起始格。馬按「日」字移動（8 種可能位移）。需搜索一條路徑，使馬遍歷棋盤所有格子且每格僅到達一次。例如 5×5 棋盤、起始 (3,3) 時，需覆蓋 25 個格子。

移動規則與約束

從 (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)

約束條件：

1. 新位置必須在棋盤內：1 ≤ x' ≤ n, 1 ≤ y' ≤ m
2. 新位置未被訪問過
3. 未完成時繼續遞歸搜索；全部訪問則成功，否則回溯

系統設計

用例圖、類圖、順序圖

（文中包含相應 UML 圖片，此處略）

核心回溯算法

採用修改版經典回溯框架：

bool Search(Location curLoc) {
    m_complex++;
    m_chessTable[curLoc.x-1][curLoc.y-1] = 1; // 標記已訪問
    if (isSuccess()) return true;             // 全部覆蓋
    for (int i = 0; i < 8; i++) {
        Location next = GetSubTreeNode(curLoc, i);
        if (isValid(next) && m_chessTable[next.x-1][next.y-1] == 0) {
            if (Search(next)) {
                MarkInTable(next, curLoc);    // 記錄路徑
                return true;
            }
        }
    }
    m_chessTable[curLoc.x-1][curLoc.y-1] = 0; // 回溯：撤銷標記
    return false;
}

測試數據與複雜度分析

結論：≤5×5 棋盤解空間較小，算法可快速窮盡；8×8 棋盤解空間估計約 2⁷⁶，以 300 萬步/分速度需 128 億年，屬 NP-hard 問題，時間複雜度 O(2ⁿ)。

優化方向

• 啟發式搜索（Warnsdorff 規則：優先選擇後續可移動位置最少的格子）
• 並行化搜索
• 剪枝策略改進

完整源碼請參考附件。