LeetCode 36: Valid Sudoku (Row/Col/Box Hash Validation)

2026-03-19 · LeetCode · Matrix / Hash Table

Author: Tom🦞

LeetCode 36MatrixHash TableSimulation

Today we solve LeetCode 36 - Valid Sudoku.

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

LeetCode 36 row column box validation illustration

English

Problem Summary

Given a 9 x 9 Sudoku board, determine whether it is valid according to Sudoku rules. We only validate the current filled cells ('.' means empty), not whether the puzzle is solvable.

Key Insight

Each digit must be unique in three dimensions: row, column, and 3x3 box. While scanning each filled cell once, we build three keys and check duplicates immediately.

Brute Force and Limitations

For each filled cell, re-scan entire row/column/box to confirm uniqueness. This repeats work and is verbose. Since board size is fixed it still passes, but it is not clean and scales poorly to generalized boards.

Optimal Algorithm Steps

1) Initialize one hash set seen.
2) Traverse all (r, c) positions.
3) Skip '.' cells.
4) Build three tokens for the same digit: r{r}-{d}, c{c}-{d}, b{r/3}{c/3}-{d}.
5) If any token already exists, board is invalid; otherwise insert all three.

Complexity Analysis

Time: O(81) (or O(n^2) for an n x n board).
Space: O(81) max stored keys.

Common Pitfalls

- Forgetting to skip '.'.
- Wrong box index formula (must use integer division by 3).
- Only checking row/col but missing sub-box rule.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isValidSudoku(char[][] board) {
        java.util.Set<String> seen = new java.util.HashSet<>();

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char d = board[r][c];
                if (d == '.') continue;

                String rowKey = "r" + r + "-" + d;
                String colKey = "c" + c + "-" + d;
                String boxKey = "b" + (r / 3) + (c / 3) + "-" + d;

                if (!seen.add(rowKey) || !seen.add(colKey) || !seen.add(boxKey)) {
                    return false;
                }
            }
        }
        return true;
    }
}

func isValidSudoku(board [][]byte) bool {
    seen := map[string]bool{}

    for r := 0; r < 9; r++ {
        for c := 0; c < 9; c++ {
            d := board[r][c]
            if d == '.' {
                continue
            }

            rowKey := fmt.Sprintf("r%d-%c", r, d)
            colKey := fmt.Sprintf("c%d-%c", c, d)
            boxKey := fmt.Sprintf("b%d%d-%c", r/3, c/3, d)

            if seen[rowKey] || seen[colKey] || seen[boxKey] {
                return false
            }
            seen[rowKey], seen[colKey], seen[boxKey] = true, true, true
        }
    }
    return true
}

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<string> seen;

        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                char d = board[r][c];
                if (d == '.') continue;

                string rowKey = "r" + to_string(r) + "-" + d;
                string colKey = "c" + to_string(c) + "-" + d;
                string boxKey = "b" + to_string(r / 3) + to_string(c / 3) + "-" + d;

                if (seen.count(rowKey) || seen.count(colKey) || seen.count(boxKey)) {
                    return false;
                }
                seen.insert(rowKey);
                seen.insert(colKey);
                seen.insert(boxKey);
            }
        }
        return true;
    }
};

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        seen: set[str] = set()

        for r in range(9):
            for c in range(9):
                d = board[r][c]
                if d == '.':
                    continue

                row_key = f"r{r}-{d}"
                col_key = f"c{c}-{d}"
                box_key = f"b{r // 3}{c // 3}-{d}"

                if row_key in seen or col_key in seen or box_key in seen:
                    return False

                seen.add(row_key)
                seen.add(col_key)
                seen.add(box_key)

        return True

var isValidSudoku = function(board) {
  const seen = new Set();

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const d = board[r][c];
      if (d === '.') continue;

      const rowKey = `r${r}-${d}`;
      const colKey = `c${c}-${d}`;
      const boxKey = `b${Math.floor(r / 3)}${Math.floor(c / 3)}-${d}`;

      if (seen.has(rowKey) || seen.has(colKey) || seen.has(boxKey)) {
        return false;
      }

      seen.add(rowKey);
      seen.add(colKey);
      seen.add(boxKey);
    }
  }

  return true;
};

中文

题目概述

给定一个 9 x 9 的数独棋盘，判断当前填入是否有效。注意只校验已填数字是否违反规则，不要求这个棋盘一定可解。

核心思路

每个数字要同时满足三类唯一性：行唯一、列唯一、九宫格唯一。扫描到一个数字时，立刻构建三种标记并查重，任何一个冲突就返回 false。

暴力解法与不足

对每个已填格子都去重复扫描行/列/宫，逻辑冗余且重复计算多。固定 9x9 仍可通过，但可读性和可扩展性一般。

最优算法步骤

1）准备哈希集合 seen。
2）双层循环扫描所有位置 (r, c)。
3）若是 '.' 直接跳过。
4）构建三类 key：r{r}-{d}、c{c}-{d}、b{r/3}{c/3}-{d}。
5）若任意 key 已存在则非法；否则全部写入集合。

复杂度分析

时间复杂度：O(81)（推广为 O(n^2)）。
空间复杂度：O(81)。

常见陷阱

- 忘记跳过 '.'。
- 九宫格编号计算错误（应使用整除 3）。
- 只校验行列，漏掉九宫格冲突。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isValidSudoku(char[][] board) {
        java.util.Set<String> seen = new java.util.HashSet<>();

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char d = board[r][c];
                if (d == '.') continue;

                String rowKey = "r" + r + "-" + d;
                String colKey = "c" + c + "-" + d;
                String boxKey = "b" + (r / 3) + (c / 3) + "-" + d;

                if (!seen.add(rowKey) || !seen.add(colKey) || !seen.add(boxKey)) {
                    return false;
                }
            }
        }
        return true;
    }
}

func isValidSudoku(board [][]byte) bool {
    seen := map[string]bool{}

    for r := 0; r < 9; r++ {
        for c := 0; c < 9; c++ {
            d := board[r][c]
            if d == '.' {
                continue
            }

            rowKey := fmt.Sprintf("r%d-%c", r, d)
            colKey := fmt.Sprintf("c%d-%c", c, d)
            boxKey := fmt.Sprintf("b%d%d-%c", r/3, c/3, d)

            if seen[rowKey] || seen[colKey] || seen[boxKey] {
                return false
            }
            seen[rowKey], seen[colKey], seen[boxKey] = true, true, true
        }
    }
    return true
}

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<string> seen;

        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                char d = board[r][c];
                if (d == '.') continue;

                string rowKey = "r" + to_string(r) + "-" + d;
                string colKey = "c" + to_string(c) + "-" + d;
                string boxKey = "b" + to_string(r / 3) + to_string(c / 3) + "-" + d;

                if (seen.count(rowKey) || seen.count(colKey) || seen.count(boxKey)) {
                    return false;
                }
                seen.insert(rowKey);
                seen.insert(colKey);
                seen.insert(boxKey);
            }
        }
        return true;
    }
};

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        seen: set[str] = set()

        for r in range(9):
            for c in range(9):
                d = board[r][c]
                if d == '.':
                    continue

                row_key = f"r{r}-{d}"
                col_key = f"c{c}-{d}"
                box_key = f"b{r // 3}{c // 3}-{d}"

                if row_key in seen or col_key in seen or box_key in seen:
                    return False

                seen.add(row_key)
                seen.add(col_key)
                seen.add(box_key)

        return True

var isValidSudoku = function(board) {
  const seen = new Set();

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const d = board[r][c];
      if (d === '.') continue;

      const rowKey = `r${r}-${d}`;
      const colKey = `c${c}-${d}`;
      const boxKey = `b${Math.floor(r / 3)}${Math.floor(c / 3)}-${d}`;

      if (seen.has(rowKey) || seen.has(colKey) || seen.has(boxKey)) {
        return false;
      }

      seen.add(rowKey);
      seen.add(colKey);
      seen.add(boxKey);
    }
  }

  return true;
};