LeetCode 36 Valid Sudoku：數獨驗證的三種解法對比

LeetCode 36 要求判斷一個 9×9 數獨盤面是否合法（非求解）。合法定義：每行、每列、每個 3×3 子網格內，數字 1~9 至多出現一次，空格用 '.' 表示。本文展示從 unordered_set 到位掩碼的三種解法，並分析時間空間權衡。

一、題目理解與建模

• 盤面固定 9×9，共 81 格。
• 需檢查三個維度：行、列、3×3 宮。
• 只需驗證已填數字無衝突，無需判斷可解性。

二、解法一：unordered_set（直觀但較慢）

為每行、每列、每宮各維護一個 unordered_set<char>，遍歷盤面，若數字已在對應集合中則衝突。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<char> rows[9], cols[9], boxes[3][3];
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                char c = board[i][j];
                if (c == '.') continue;
                if (rows[i].count(c) || cols[j].count(c) || boxes[i/3][j/3].count(c))
                    return false;
                rows[i].insert(c);
                cols[j].insert(c);
                boxes[i/3][j/3].insert(c);
            }
        }
        return true;
    }
};

• Runtime：~24 ms
• 缺點：哈希表開銷大，常數因子高。

三、解法二：定長數組 + 位掩碼（極快）

利用 int 的低 9 位作為位掩碼：第 k 位為 1 表示數字 k+1 已出現。int rows[9][9] = {0} 中 rows[i][d] 記錄第 i 行數字 d+1 是否出現。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int rows[9][9] = {0}, cols[9][9] = {0}, boxes[3][3][9] = {0};
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                char c = board[i][j];
                if (c == '.') continue;
                int d = c - '1';  // 0~8 對應 1~9
                if (rows[i][d]++ || cols[j][d]++ || boxes[i/3][j/3][d]++)
                    return false;
            }
        }
        return true;
    }
};

• Runtime：~12 ms（快一倍！）
• 優勢：連續內存、無哈希計算、分支預測友好、CPU 緩存命中率高。

四、解法三：單次遍歷 + 三個位掩碼整數（空間最優）

每行、每列、每宮各用一個 int（9 位）即可，總共 27 個 int。遍歷時動態計算宮索引。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int rowMask[9] = {0}, colMask[9] = {0}, boxMask[9] = {0};
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                char c = board[i][j];
                if (c == '.') continue;
                int bit = 1 << (c - '1');
                int b = (i / 3) * 3 + j / 3;  // 宮索引 0~8
                if (rowMask[i] & bit) return false;
                if (colMask[j] & bit) return false;
                if (boxMask[b] & bit) return false;
                rowMask[i] |= bit;
                colMask[j] |= bit;
                boxMask[b] |= bit;
            }
        }
        return true;
    }
};

• 空間：僅 27 × 4 = 108 字節。
• Runtime：通常 8~10 ms，最快。

五、三種解法綜合對比

六、核心技巧總結

1. 宮索引公式：box = (i/3)*3 + j/3，將 3×3 宮映射為 0~8。
2. 位掩碼構造：1 << (c - '1')，數字 1→bit 0, 9→bit 8。
3. 後綴自增判斷：if (rows[i][d]++) 利用舊值為 0/1 直接判斷衝突，極其簡潔。
4. 提前剪枝：發現衝突即 return false，無需掃完整盤面。

七、面試/實戰建議

• 面試首選：解法二（定長數組計數），平衡了可讀性、速度、空間，無需解釋位運算細節。
• 極致優化：解法三，適合嵌入式、內存受限環境或追求榜首提交。
• 泛化版本：若面試官問「N×N 數獨驗證」，需改用 vector<unordered_set> 或 vector<vector<bool>>，位掩碼受限於整型位寬（64 位支援至 8×8）。