IDA*算法解決N皇后覆蓋問題：迭代加深與位運算優化

問題背景

本題要求在棋盤上放置最少數量的皇后，使其覆蓋所有格子。皇后可攻擊同行、同列、同對角線的所有格子。題目給出深度上限為5，即最多需5個皇后即可覆蓋整個棋盤。

核心思路：IDA* 迭代加深搜索

採用 IDA*（Iterative Deepening A*）策略，從深度 1 開始逐層遞增上限，直到找到可行解。由於搜索空間較大，需結合剪枝優化：

• 位運算快速判衝突：參考《紫書》技巧，用四個一維數組分別記錄行、列、主對角線（x+y）、副對角線（x-y+偏移量）是否被佔用，O(1) 判斷任意兩子是否衝突。
• 按行遞歸搜索：類似經典八皇后問題，當前行之前的行已放置皇后，無需重複檢查，每層僅從下一行開始枚舉列位置，大幅減少狀態數。

關鍵代碼片段

bool dfs(int cur, int r) {
    if (cur == maxd) {
        // 檢查所有 'X' 格是否被覆蓋
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                if (s[i][j] == 'X' && !vis[0][i] && !vis[1][j] && !vis[2][i+j] && !vis[3][i-j+11])
                    return false;
        return true;
    }
    for (int i = r; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (!vis[0][i] || !vis[1][j] || !vis[2][i+j] || !vis[3][i-j+11]) {
                // 保存狀態以便回溯
                int v1 = vis[0][i], v2 = vis[1][j], v3 = vis[2][i+j], v4 = vis[3][i-j+11];
                vis[0][i] = vis[1][j] = vis[2][i+j] = vis[3][i-j+11] = 1;
                if (dfs(cur + 1, i + 1)) return true;
                // 回溯恢復
                vis[0][i] = v1; vis[1][j] = v2; vis[2][i+j] = v3; vis[3][i-j+11] = v4;
            }
        }
    }
    return false;
}

複雜度分析

理論上每層 O(nm)，但實際受剪枝影響極小。IDA* 保證找到最小深度解，配合位運算與按行搜索，可在限制時間內解決棋盤規模達 15×15 的問題。

總結

本題展示了 IDA* 在組合優化問題中的典型應用：迭代加深保證最優解，位運算與搜索順序優化大幅壓縮狀態空間，是解決此類覆蓋問題的經典範例。