LeetCode 37 Sudoku Solver：回溯法 + 位掩碼優化完整攻略

題目大意

解決標準 9×9 數獨。空格用 '.' 表示。保證有唯一解。需原地修改棋盤。

算法選型：回溯 + 位掩碼

• 9×9 = 81 格，每格最多 9 種嘗試，搜索空間極大，需強力剪枝。
• 位掩碼：用 9 位整數表示某行/列/宮可用數字。bit i = 1 表示數字 i+1 可用。
  　　row[9], col[9], box[9] 初始全 0x1FF (511)（9 位全 1）。
  　　放入數字 d → mask ^= (1 << (d-1)) 清零對應位。
  　　取可用數字 → mask & -mask 取最低位 1，或預計算 bits[512] 列表。
• 遞歸順序：按格子索引 0..80 線性遞歸，或優先選「可用數字最少」的格子（MRV 启发式）。本題線性遞歸配合位運算已極快（< 10ms）。

核心代碼結構

class Solution {
    int row[9], col[9], box[9];
    vector<pair<int,int>> emptyCells;
    bool solved = false;

    void solveSudoku(vector<vector<char>>& board) {
        // 初始化掩碼
        fill(begin(row), end(row), 0x1FF);
        fill(begin(col), end(col), 0x1FF);
        fill(begin(box), end(box), 0x1FF);
        emptyCells.clear();

        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 9; ++j)
                if (board[i][j] == '.')
                    emptyCells.emplace_back(i, j);
                else {
                    int d = board[i][j] - '1';
                    int mask = 1 << d;
                    row[i] ^= mask;
                    col[j] ^= mask;
                    box[(i/3)*3 + j/3] ^= mask;
                }
        dfs(board, 0);
    }

    void dfs(vector<vector<char>>& board, int idx) {
        if (idx == emptyCells.size()) { solved = true; return; }
        auto [r, c] = emptyCells[idx];
        int b = (r/3)*3 + c/3;
        int avail = row[r] & col[c] & box[b];  // 可用數字掩碼

        while (avail) {
            int bit = avail & -avail;  // 取最低位 1
            avail ^= bit;              // 從可用集移除
            int d = __builtin_ctz(bit); // 數字 0-8
            board[r][c] = '1' + d;
            row[r] ^= bit; col[c] ^= bit; box[b] ^= bit;
            dfs(board, idx + 1);
            if (solved) return;
            // 回溯
            row[r] ^= bit; col[c] ^= bit; box[b] ^= bit;
            board[r][c] = '.';
        }
    }
};

關鍵優化細節

常見錯誤（血淚教訓）

1. 字符比較寫成 board[i][j] == 'p'：p 是變量而非字面量，應為 board[i][j] == d 或 bit 掩碼判斷。
2. 宮索引算錯：(i/3)*3 + j/3 而非 i/3 + j/3*3。
3. 未恢復掩碼：回溯時必須 ^= bit 恢復，否則後續分支錯誤。
4. 未處理 solved 提前返回：找到解後繼續搜索導致 TLE 或覆蓋答案。

複雜度

• 最壞理論 9^81，實際經位掩碼剪枝 + 唯一解保證，< 10^5 節點訪問。
• 時間 < 10ms，空間 O(1) 額外。

總結

Sudoku Solver 是回溯法 + 位掩碼優化的教科書級應用。關鍵在於將「行/列/宮約束」編碼為 9 位整數，利用位運算實現 O(1) 合法性檢查與候選枚舉。掌握此模板，可直接應用於 N 皇後、圖著色、十字填字等精確覆蓋問題。現代 C++ 的 __builtin_ctz、bit & -bit 等位運算技巧，使代碼既簡潔又極致高效。