36. Valid Sudoku

題目 / Problem

中文： 給定一個 9 x 9 的數獨棋盤，判斷它是否「有效」。只需要驗證已經填入數字的格子（空格用 . 表示），規則如下：

1. 每一列（row）的數字 1-9 不能重複。
2. 每一行（column）的數字 1-9 不能重複。
3. 棋盤被切成 9 個 3 x 3 的小方塊（sub-box），每個小方塊內的數字 1-9 也不能重複。

注意：一個有效的棋盤不一定有解；我們只檢查目前已填入的數字是否違反上面三條規則。

English: Given a 9 x 9 Sudoku board, decide whether it is valid. You only validate the filled cells (empty cells are marked .). The rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. The grid is divided into nine 3 x 3 sub-boxes, and each sub-box must contain 1-9 without repetition.

Note: a valid board need not be solvable; we only check that the already-filled digits break none of the three rules.

Constraints / 限制條件: - board.length == 9, board[i].length == 9 — 棋盤固定是 9×9 / the board is always 9×9. - board[i][j] 是 '1'–'9' 的數字字元，或是 '.' / each cell is a digit char '1'–'9' or '.'.

Example / 範例:

board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

如果把左上角的 "5" 改成 "8"，左上角小方塊就有兩個 8，結果變成 false。/ If the top-left "5" is changed to "8", the top-left box has two 8s, so the result becomes false.

名詞解釋 / Glossary

• row / 列（橫排）：棋盤的一整橫排，例如 board[0] 就是第 0 列。本題裡「row」指水平方向的一排。/ One horizontal line of the board; board[0] is row 0.
• column / 行（直排）：棋盤的一整直排，所有 board[i][j] 中 j 固定、i 變化的格子。/ One vertical line; all cells sharing the same column index j.
• sub-box / 小方塊：把 9×9 切成 3×3=9 個小區塊，每個小區塊本身是 3×3。/ The grid split into nine 3×3 blocks.
• hash set / 雜湊集合：一種能 O(1) 平均時間判斷「某元素是否已出現過」的容器。我們用它記錄某列/行/小方塊看過哪些數字。/ A container that tells you in ~O(1) whether an item has already been seen; used to track which digits appeared.
• boolean array as a seen-table / 用布林陣列當「看過了沒」的表：因為數字只有 1-9 共 9 種，我們可以用一個長度 9 的布林陣列，seen[d]=true 表示數字 d 出現過，比雜湊集合更快更省。/ Since digits are only 1-9, a length-9 boolean array indexed by digit acts as a fast membership table.
• box index / 小方塊編號：用公式 (i/3)*3 + (j/3) 把格子 (i,j) 對應到 0–8 的小方塊編號。/3 是整數除法，會把 0,1,2→0；3,4,5→1；6,7,8→2。/ The formula (i/3)*3 + (j/3) maps cell (i,j) to a box number 0–8; /3 is integer division.
• integer division / 整數除法：在 C/C++ 中兩個整數相除會丟掉小數，例如 7/3 == 2。/ Dividing two ints discards the fractional part, e.g. 7/3 == 2.

思路

我們先想最直接的「暴力」做法：對每一列檢查有沒有重複、對每一行檢查、對每個小方塊檢查，總共要分開掃描棋盤三次。這樣雖然能做，但邏輯重複、而且每次都要重新建立紀錄。其實有一個關鍵觀察：每一個格子 (i,j) 只屬於「一列、一行、一個小方塊」，所以只要掃描棋盤一次，對每個填了數字的格子，同時去檢查它所在的那一列、那一行、那一個小方塊裡，這個數字是不是已經出現過。為了「記住出現過哪些數字」，我們需要紀錄表：用 9 個列的紀錄、9 個行的紀錄、9 個小方塊的紀錄。因為數字只有 1–9，最省的做法是用布林陣列——rows[r][d] 為真就代表第 r 列已經有數字 d 了。關鍵公式是小方塊編號 (i/3)*3 + (j/3)：整數除法 i/3 把第 0~8 列壓成 0/1/2 三段，乘 3 再加上 j/3，就能把九個小方塊各自編成 0 到 8。每碰到一個數字，先看三張表裡有沒有它；只要任何一張說「看過了」，就立刻回傳 false；否則把三張表都標記為「看過」。掃完整個棋盤都沒衝突就回傳 true。這個方法只掃一次、且檢查與標記都是 O(1)，所以非常快。

The brute-force idea is to scan the board three separate times: once to check every row for duplicates, once for every column, once for every 3×3 box. It works but repeats logic and rebuilds bookkeeping each pass. The key observation is that each cell (i,j) belongs to exactly one row, one column, and one box — so a single pass suffices if, for each filled cell, we simultaneously check whether its digit already appeared in that row, that column, and that box. To "remember what we've seen" we keep three tables of records: 9 rows, 9 columns, 9 boxes. Because digits are only 1-9, the cheapest record is a boolean array — rows[r][d] == true means row r already contains digit d. The box number comes from (i/3)*3 + (j/3): integer division i/3 collapses rows 0–8 into three bands 0/1/2, multiply by 3 and add j/3 to give each of the nine boxes a unique id 0–8. For each digit, look it up in all three tables; if any says "already seen," return false immediately, otherwise mark all three as seen. If the whole board passes, return true. One pass with O(1) checks makes this very fast.

逐步走查 / Walkthrough

我們用範例的前幾個格子來走查。三張表 rows、cols、boxes 一開始全是 false。空格 . 直接跳過。/ We trace the first few cells of the example. Tables rows, cols, boxes start all-false; . cells are skipped.

整個棋盤掃完都沒有任何一次檢查命中 true，所以回傳 true。/ The whole scan never hits an already-true slot, so the answer is true.

對照 Example 2：左上角改成 8 後，當掃到 (2,2) 的 8 時（也在 box 0），boxes[0][8] 已經被 (0,0) 的 8 設成 true，檢查命中 → 立即回傳 false。/ In Example 2, after the top-left becomes 8, scanning the 8 at (2,2) (also box 0) finds boxes[0][8] already true → return false.

Solution — C

// 演算法：一次掃描整個棋盤。對每個已填數字，檢查它所在的「列/行/小方塊」是否已出現過該數字。
// Algorithm: single pass. For each filled digit, check if it already appeared in its row / column / box.
// 用布林陣列當紀錄表（數字只有 1-9），命中重複就回傳 false，全部通過回傳 true。
// Use boolean tables (digits are 1-9 only); a repeat means false, otherwise true.

#include <stdbool.h>   // 讓我們能使用 bool / true / false / lets us use bool, true, false
#include <string.h>    // 提供 memset，用來把陣列一次清成 0 / provides memset to zero an array at once

// LeetCode 給的是「字串陣列的陣列」：board[i] 是一行字串，board[i][j] 是字元。
// LeetCode passes an array of strings: board[i] is one row, board[i][j] is a char.
bool isValidSudoku(char** board, int boardSize, int* boardColSize) {
    // 三張紀錄表，大小 9×10。第二維用 10 是為了讓索引能直接用數字 1..9（索引 0 不用，較直覺）。
    // Three tables, 9×10. Width 10 so we can index directly by digit 1..9 (index 0 unused, clearer).
    bool rows[9][10];
    bool cols[9][10];
    bool boxes[9][10];

    // memset 把整塊記憶體的每個 byte 設成 0；對 bool 來說 0 就是 false，等於全部清空。
    // memset sets every byte to 0; for bool, 0 means false, so this clears all tables.
    memset(rows, 0, sizeof(rows));
    memset(cols, 0, sizeof(cols));
    memset(boxes, 0, sizeof(boxes));

    // 外層走 9 列，內層走 9 行，逐格檢查。
    // Outer loop over 9 rows, inner over 9 columns; visit each cell.
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char c = board[i][j];          // 取出這一格的字元 / read this cell's char

            if (c == '.') continue;        // 空格不檢查，直接跳到下一格 / empty cell: skip to next

            // 字元轉成數字：'5' - '0' == 5。字元在記憶體裡是編碼，相減得到 0..9 的整數。
            // Char to int: '5' - '0' == 5. Chars are codes; subtracting '0' yields the integer 0..9.
            int d = c - '0';

            // 小方塊編號：i/3 是整數除法（丟小數），把列壓成 0/1/2；乘 3 再加 j/3，得到 0..8。
            // Box id: i/3 is integer division (drops fraction) giving 0/1/2; *3 + j/3 yields 0..8.
            int b = (i / 3) * 3 + (j / 3);

            // 若這個數字已在「同列」或「同行」或「同方塊」出現過，就違反規則，回傳 false。
            // If this digit already appeared in same row / col / box, a rule is broken → return false.
            if (rows[i][d] || cols[j][d] || boxes[b][d]) {
                return false;
            }

            // 否則把這個數字在三張表裡都標記為「已出現」，供後面的格子比對。
            // Otherwise mark this digit as seen in all three tables for later cells to compare against.
            rows[i][d] = true;
            cols[j][d] = true;
            boxes[b][d] = true;
        }
    }

    // 全部掃完都沒衝突，棋盤有效。
    // No conflict after the full scan: the board is valid.
    return true;
}

Solution — C++

// 演算法與 C 版相同：一次掃描，對每個數字檢查其列/行/小方塊是否重複。
// Same algorithm as the C version: one pass, check row/col/box duplication per digit.
// 這裡用 std::array 包成固定大小的二維表，型別安全且不需手動管理記憶體。
// Here we use std::array as fixed-size 2D tables — type-safe and no manual memory management.

#include <vector>
#include <array>
#include <string>
using namespace std;

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // std::array<bool,10> 是固定長度 10 的布林陣列；外層 array<...,9> 給每列/行/方塊各一份。
        // std::array<bool,10> is a fixed length-10 bool array; the outer array<...,9> gives one per row/col/box.
        // 大括號 {} 會把所有元素初始化成 false（值初始化），不必再手動清零。
        // The braces {} value-initialize every element to false, so no manual clearing is needed.
        array<array<bool, 10>, 9> rows{};
        array<array<bool, 10>, 9> cols{};
        array<array<bool, 10>, 9> boxes{};

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                char c = board[i][j];        // 這一格的字元 / this cell's char
                if (c == '.') continue;      // 空格跳過 / skip empty cells

                int d = c - '0';             // 字元轉數字 1..9 / char to int 1..9
                int b = (i / 3) * 3 + (j / 3); // 小方塊編號 0..8 / box id 0..8（整數除法 / integer division）

                // 任一張表已標記 → 出現重複 → 棋盤無效。
                // Any table already marked → duplicate → invalid board.
                if (rows[i][d] || cols[j][d] || boxes[b][d]) {
                    return false;
                }

                // 標記三張表，記錄「此數字已在這列/行/方塊出現」。
                // Mark all three tables: this digit now seen in this row/col/box.
                rows[i][d] = cols[j][d] = boxes[b][d] = true;
            }
        }

        return true; // 沒有任何衝突 / no conflicts found
    }
};

複雜度 / Complexity

• Time: O(1) — 棋盤大小固定為 9×9 = 81 格，每格只做常數次比對與標記。若把「邊長」當成變數 n（這裡 n=9），則是 O(n²)，因為要看每一格一次。/ The board is fixed at 81 cells, each handled in constant work. Treating side length as n, it's O(n²) since each cell is visited once.
• Space: O(1) — 三張表大小固定（9×10），不隨輸入變化；以 n 表示則為 O(n²)。/ Three fixed-size tables (9×10), independent of input; O(n²) in terms of n.

Pitfalls & Edge Cases

• 小方塊編號公式寫錯 / Wrong box-index formula：常見錯誤是寫成 i/3 + j/3，這樣不同方塊會撞號（例如 box(0,3) 與 box(3,0) 都得 1）。正確是 (i/3)*3 + (j/3)，乘 3 才能把三段分開。/ Writing i/3 + j/3 collides different boxes; the *3 separates the three bands.
• 忘記跳過 . / Forgetting to skip .：若不先判斷空格，'.' - '0' 會得到一個負數索引，造成陣列越界、未定義行為。程式用 if (c == '.') continue; 避開。/ Without the skip, '.' - '0' is a negative index → out-of-bounds. The continue guards it.
• 字元 vs 數字 / Char vs int：board[i][j] 是字元 '5' 而不是整數 5；必須用 c - '0' 轉換才能當索引。/ Cells are chars like '5', not ints; convert with c - '0' before indexing.
• 索引從 0 還是 1 / 0- vs 1-based table：我們把表的第二維開成 10，讓數字 1–9 直接當索引，索引 0 留空不用——比起「d-1」更不容易寫錯。/ Width 10 lets digit 1–9 index directly (slot 0 unused), avoiding off-by-one from d-1.
• 只驗證已填格 / Only filled cells matter：題目明說不必判斷是否可解，也不必填滿；遇到 . 不算錯。/ The board need not be full or solvable; . is never a violation.
• 同一數字出現在不同列/行/方塊是合法的 / Same digit in different row/col/box is fine：重複只在「同一」列、行或方塊內才算違規，三張分開的表正好對應這點。/ A digit repeats legally across different units; the three separate tables capture exactly this.