LeetCode 36 Valid Sudoku：驗證數獨合法性

題目簡介

判斷 9×9 數獨盤面是否合法：每行、每列、每個 3×3 子格內數字 1-9 不重複（忽略 '.')。盤面可能未填滿。

解題思路

分三步檢查，每步用哈希表/數組記錄出現過的數字：

1. 檢查 9 行：對每行掃描 9 列，若數字重複返回 false。
2. 檢查 9 列：對每列掃描 9 行。
3. 檢查 9 個 3×3 子格：雙重循環遍歷 9 個子格左上角，內層掃描 3×3。

所有檢查通過返回 true。

代碼實現

public boolean isValidSudoku(char[][] board) {
    Map<Character,Integer> map = new HashMap<>();
    // 行
    for (int i=0;i<9;i++) {
        map.clear(); for (char c='1';c<='9';c++) map.put(c,0);
        for (int j=0;j<9;j++) {
            char c = board[i][j];
            if (c>='1' && c<='9') {
                if (map.get(c) > 0) return false;
                map.put(c,1);
            } else if (c!='.') return false;
        }
    }
    // 列
    for (int j=0;j<9;j++) {
        map.clear(); for (char c='1';c<='9';c++) map.put(c,0);
        for (int i=0;i<9;i++) {
            char c = board[i][j];
            if (c>='1' && c<='9') {
                if (map.get(c) > 0) return false;
                map.put(c,1);
            } else if (c!='.') return false;
        }
    }
    // 子格
    for (int r=0;r<9;r+=3) for (int c=0;c<9;c+=3) {
        map.clear(); for (char ch='1';ch<='9';ch++) map.put(ch,0);
        for (int i=r;i='1' && ch<='9') {
                if (map.get(ch) > 0) return false;
                map.put(ch,1);
            } else if (ch!='.') return false;
        }
    }
    return true;
}

優化建議

可用位掩碼（int 9 位）替代 Map，更高效。也可一次遍歷同時更新行、列、塊的位掩碼。