loading

36. Valid Sudoku — Step-by-Step Visualization

mediumLeetCode #36ArrayHash TableMatrix

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: 1. Each row must contain the digits 1-9 without repetition. 2. Each column must contain the digits 1-9 without repetition. 3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. **Note:** - A Sudoku board (partially filled) could be valid but is not necessarily solvable. - Only the filled cells need to be validated according to the mentioned rules.

Algorithm Pattern

Triple Uniqueness Constraint

Key Idea

For each filled cell `(r, c)` with digit `v`, we must ensure `v` is not repeated within its corresponding row index `r`, its column index `c`, and its 3x3 square index `(r//3, c//3)`.

Step-by-Step Approach

  1. Initialize three separate hash sets/arrays for each row, column, and 3x3 square.
  2. Iterate through every cell `(r, c)` in the 9x9 grid.
  3. Skip empty cells marked with `.`.
  4. Calculate the square index: `idx = Math.floor(r/3) * 3 + Math.floor(c/3)`.
  5. Check if the digit already exists in the current row's set, column's set, or square's set.
  6. If a duplicate is found, the board is invalid. Otherwise, add the digit to all three sets and continue.

Common Gotchas

  • Remember that only filled cells need to be validated.
  • The square index calculation `Math.floor(r/3) * 3 + Math.floor(c/3)` is a common way to map any cell to one of the nine 3x3 blocks.
  • Validation does not mean the board is solvable, only that the current state is logically consistent.

Related Problems

← All problems