36. Valid Sudoku

📘 題目敘述

給定一個 9 x 9 的數獨棋盤 board，請判斷它目前是不是一個有效的 Sudoku 盤面。

只需要檢查目前已經填入的格子是否符合以下規則：

• 每一列不能有重複的 1 到 9
• 每一行不能有重複的 1 到 9
• 每一個 3 x 3 小區塊不能有重複的 1 到 9

注意：

• 一個盤面就算目前有效，也不代表它一定有解
• 只需要檢查已經填入的數字
• '.' 表示空格，不需要拿來檢查

條件限制

• board.length == 9
• board[i].length == 9
• board[i][j] 是 '1' 到 '9' 或 '.'

🧠 解題思路

我這題的做法就是直接檢查。

題目要求合法的條件只有三種：

• 每一列不能重複
• 每一行不能重複
• 每一個 3 x 3 小方格不能重複

所以我就把這三件事分開做。
每次檢查某一列、某一行、或某一個 3 x 3 區塊時，都開一個 unordered_set<char> 來記錄目前看過哪些數字。

如果遇到某個數字已經出現過，代表重複了，就直接回傳 false。
如果全部檢查完都沒有問題，那就是合法盤面，回傳 true。

所有變數

這題不用令變數

🪜 主要流程步驟

1. 先逐列檢查有沒有重複數字

我先把每一列獨立檢查一次。

對每一列 i，我都新開一個 unordered_set<char> s，
然後把這一列從左到右掃過去。

如果某個位置是數字 '1' 到 '9'，我才拿來檢查；
如果是 '.'，代表空格，直接跳過。

• 同一列裡每出現一個數字，就先看 set 裡有沒有
• 如果已經有了，代表這一列重複，直接回傳 false
• 否則就把它放進 set

2. 再逐行檢查有沒有重複數字

接著我再把每一行也獨立檢查一次。

做法和檢查列完全一樣，只是這次固定的是欄位 j，
然後往下掃每個 i。

如果某一行中同一個數字出現兩次，也會立刻回傳 false。

3. 最後檢查九個 3 x 3 小區塊

除了列和行之外，數獨還要求每個 3 x 3 小區塊內不能重複。
所以我最後再把九個區塊都檢查一遍。

我用外面兩層迴圈：

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {

來枚舉每個 3 x 3 區塊的左上角區塊編號。

然後再用裡面兩層迴圈：

for (int k = 0; k < 3; k++) {
    for (int l = 0; l < 3; l++) {

去掃那個區塊內的九個位置。

實際座標是：

char c = board[i * 3 + k][j * 3 + l];

這樣就能把第 (i, j) 個小區塊中的所有格子都走到。

如果某個數字在同一個區塊裡出現兩次，就回傳 false：

if (c >= '1' && c <= '9') {
    if (s.count(c)) {
        return false;
    }
    s.insert(c);
}

4. 只要任何一種檢查失敗，就立刻回傳 false

這份寫法的特點就是直接檢查、直接結束。

不管是：

• 某一列重複
• 某一行重複
• 某一個 3 x 3 區塊重複

只要發現其中一個違規，就不用再看後面了，直接回傳 false。

這樣邏輯很直，也很符合題目要求。

5. 如果全部檢查完都沒問題，就回傳 true

如果三種檢查都跑完，沒有遇到任何重複數字，
就代表這個盤面目前是合法的，所以最後回傳 true。

⏱️ 複雜度

• 時間複雜度：O(1)
  棋盤固定是 9 x 9，所以不管怎麼掃，總操作量都是固定常數。
• 空間複雜度：O(1)
  每次檢查只會用到固定大小的 unordered_set。

💻 程式碼實作

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            unordered_set<char> s;
            for (int j = 0; j < 9; j++) {
                if (board[i][j] >= '1' && board[i][j] <= '9') {
                    if (s.count(board[i][j])) {
                        return false;
                    }
                    s.insert(board[i][j]);
                }
            }
        }
        for (int j = 0; j < 9; j++) {
            unordered_set<char> s;
            for (int i = 0; i < 9; i++) {
                if (board[i][j] >= '1' && board[i][j] <= '9') {
                    if (s.count(board[i][j])) {
                        return false;
                    }
                    s.insert(board[i][j]);
                }
            }
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                unordered_set<char> s;
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 3; l++) {
                        char c = board[i * 3 + k][j * 3 + l];
                        if (c >= '1' && c <= '9') {
                            if (s.count(c)) {
                                return false;
                            }
                            s.insert(c);
                        }
                    }
                }
            }
        }
        return true;
    }
};

🔗 題目連結

https://leetcode.com/problems/valid-sudoku/