POJ 2676 Sudoku 數獨求解器：DFS 回溯 + 位元優化完整實作

題目大意

標準 9×9 數獨，輸入多組測資，0 代表空格。輸出任一合法解。限制：每行、每列、每 3×3 宮內數字 1~9 不重複。

核心演算法：DFS 回溯 + 位元遮罩加速

用三個陣列記錄行、列、宮的已用數字狀態，以 int 位元操作 (1 << d) 實現 O(1) 合法性檢查與狀態更新，極大提升速度。

狀態表示

• row[9]：第 i 行已用數字位元遮罩。
• col[9]：第 j 列已用數字位元遮罩。
• box[9]：第 k 宮已用數字位元遮罩，k = (i/3)*3 + j/3。

DFS 搜尋順序優化

1. 預先收集所有空格座標至向量 empties。
2. 按「候選數最少」啟發式排序 (MRV)，或簡單線性遞增 (本題資料量小，線性即可)。
3. 遞迴嘗試填入 1~9，位元檢查合法後更新狀態，遞迴下一格；回溯時復原位元。
4. 找到解即設全域旗標 solved 並層層返回。

完整高效程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;

char board[9][10]; // +1 for null terminator
int rowMask[9], colMask[9], boxMask[9];
vector> empties;
bool solved;

inline int boxIndex(int r, int c) { return (r/3)*3 + c/3; }

void dfs(int idx) {
    if (solved) return;
    if (idx == (int)empties.size()) {
        solved = true;
        return;
    }
    int r = empties[idx].first;
    int c = empties[idx].second;
    int b = boxIndex(r, c);
    int used = rowMask[r] | colMask[c] | boxMask[b];
    // 嘗試數字 1~9 (bit 1~9)
    for (int d = 1; d <= 9; ++d) {
        int bit = 1 << d;
        if (used & bit) continue;
        // 放置
        board[r][c] = '0' + d;
        rowMask[r] |= bit; colMask[c] |= bit; boxMask[b] |= bit;
        dfs(idx + 1);
        if (solved) return;
        // 回溯
        rowMask[r] &= ~bit; colMask[c] &= ~bit; boxMask[b] &= ~bit;
        board[r][c] = '0';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        // 初始化
        memset(rowMask, 0, sizeof(rowMask));
        memset(colMask, 0, sizeof(colMask));
        memset(boxMask, 0, sizeof(boxMask));
        empties.clear();
        solved = false;

        for (int i = 0; i < 9; ++i) {
            cin >> board[i];
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '0') {
                    empties.emplace_back(i, j);
                } else {
                    int d = board[i][j] - '0';
                    int bit = 1 << d;
                    rowMask[i] |= bit;
                    colMask[j] |= bit;
                    boxMask[boxIndex(i, j)] |= bit;
                }
            }
        }

        dfs(0);

        for (int i = 0; i < 9; ++i)
            cout << board[i] << '\n';
        if (T) cout << '\n'; // 依題目格式決定是否空行
    }
    return 0;
}

關鍵優化細節

1. 位元運算：used = row|col|box 一次取得所有衝突位，if (used & bit) 判斷衝突，比陣列 bool used[10] 快數倍。
2. 空格預收集：避免 DFS 中掃描整個棋盤找下一個 0。
3. MRV 啟發式 (可選)：sort(empties.begin(), empties.end(), [](...){ return __builtin_popcount(rowMask[r]|colMask[c]|boxMask[b]); }); 可進一步剪枝，但 9×9 規模下線性序通常足夠。
4. 全域 solved 剪枝：找到第一解即停止所有遞迴。

複雜度分析

• 最壞情況指數級，但標準數獨有唯一解且約束極強，實際搜尋節點極少 (通常 < 10,000)。
• 位元操作使每節點檢查極快，單測資通常 < 10ms 內解出。

延伸：唯一性驗證

若需確認解唯一，找到第一解後繼續搜尋，若再找到第二解則非唯一。修改 dfs 回傳 int 計數即可。