36. Valid Sudoku

Medium
Description

判斷一個 9x9 的數獨棋盤是否有效。只需驗證已填入的數字是否符合規則：每行、每列、每個 3x3 子方格中數字 1-9 不重複。不需要驗證數獨是否有解。

Example:

Input: 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

Intuition#

核心思路：用三組 HashSet 分別追蹤每行、每列、每個 3x3 方格中已出現的數字，遇到重複即無效。

  • 數獨有效的三個條件：每行不重複、每列不重複、每個 3x3 方格不重複
  • 關鍵：3x3 方格的索引可以用 (row / 3, col / 3) 計算

Approaches#

1: Three Separate Passes#

  • 概念: 分別遍歷每行、每列、每個方格，各自檢查是否有重複
  • 時間複雜度: O(1) - 固定 81 格，常數時間
  • 空間複雜度: O(1) - 固定大小的儲存結構
class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {
        // 檢查每行
        for (row in 0 until 9) {
            val seen = HashSet<Char>()
            for (col in 0 until 9) {
                val c = board[row][col]
                if (c != '.' && !seen.add(c)) return false
            }
        }
        // 檢查每列
        for (col in 0 until 9) {
            val seen = HashSet<Char>()
            for (row in 0 until 9) {
                val c = board[row][col]
                if (c != '.' && !seen.add(c)) return false
            }
        }
        // 檢查每個 3x3 方格
        for (boxRow in 0 until 3) {
            for (boxCol in 0 until 3) {
                val seen = HashSet<Char>()
                for (r in 0 until 3) {
                    for (c in 0 until 3) {
                        val ch = board[boxRow * 3 + r][boxCol * 3 + c]
                        if (ch != '.' && !seen.add(ch)) return false
                    }
                }
            }
        }
        return true
    }
}

⭐2: Single Pass with HashSets#

  • 概念: 只遍歷一次棋盤，同時檢查行、列、方格三個條件，用 (row / 3, col / 3) 定位方格
  • 時間複雜度: O(1) - 固定 81 格
  • 空間複雜度: O(1) - 固定大小（9 行 + 9 列 + 9 方格的 Set）
class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {
        val rows = Array(9) { HashSet<Char>() }
        val cols = Array(9) { HashSet<Char>() }
        val boxes = Array(9) { HashSet<Char>() }

        for (r in 0 until 9) {
            for (c in 0 until 9) {
                val ch = board[r][c]
                if (ch == '.') continue

                val boxIdx = (r / 3) * 3 + (c / 3)

                if (!rows[r].add(ch) || !cols[c].add(ch) || !boxes[boxIdx].add(ch)) {
                    return false
                }
            }
        }
        return true
    }
}

3x3 方格索引公式 boxIdx = (r / 3) * 3 + (c / 3) 是關鍵。整數除法 r / 3 將 0-2 映射到 0、3-5 映射到 1、6-8 映射到 2，再乘以 3 加上列的部分，產生 0-8 的唯一索引。

🔑 Takeaways#

  • Pattern: 矩陣約束驗證 -> 用多組 HashSet 同時追蹤各維度的約束
  • 關鍵技巧: (row / 3) * 3 + (col / 3) 將 2D 方格座標映射到 1D 索引，這個公式在許多矩陣分塊問題中都會用到