LeetCode 36: Valid Sudoku

Problem Restatement

We are given a 9 x 9 Sudoku board.

Each cell contains either:

"."

or a digit from:

"1" to "9"

The board does not need to be solved. We only need to check whether the filled cells obey Sudoku rules.

A board is valid when:

Rule	Meaning
Row rule	Each digit `1` to `9` appears at most once in every row
Column rule	Each digit `1` to `9` appears at most once in every column
Box rule	Each digit `1` to `9` appears at most once in every `3 x 3` box

Empty cells marked with "." are ignored.

Input and Output

Item	Meaning
Input	A `9 x 9` board of characters
Output	`True` if the board is valid, otherwise `False`
Empty cell	`"."`
Filled cell	A digit from `"1"` to `"9"`
Important point	Valid means no rule is broken by the current filled cells

Function shape:

def isValidSudoku(board: list[list[str]]) -> bool:
    ...

Examples

Example 1:

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"],
]

This board is valid because no filled digit repeats inside any row, column, or 3 x 3 box.

Return:

True

Example 2:

board = [
    ["8","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"],
]

The digit "8" appears twice in the first column.

Return:

False

First Thought: Check Rows, Columns, and Boxes Separately

A direct solution is to check each rule one by one.

First, check every row.

Then, check every column.

Then, check every 3 x 3 box.

For each group, use a set to detect repeated digits.

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

            for c in range(9):
                value = board[r][c]

                if value == ".":
                    continue

                if value in seen:
                    return False

                seen.add(value)

        for c in range(9):
            seen = set()

            for r in range(9):
                value = board[r][c]

                if value == ".":
                    continue

                if value in seen:
                    return False

                seen.add(value)

        for box_r in range(0, 9, 3):
            for box_c in range(0, 9, 3):
                seen = set()

                for r in range(box_r, box_r + 3):
                    for c in range(box_c, box_c + 3):
                        value = board[r][c]

                        if value == ".":
                            continue

                        if value in seen:
                            return False

                        seen.add(value)

        return True

This is correct and simple.

But the same board cells are scanned multiple times.

Problem With Separate Checks

The board is only 9 x 9, so scanning it three times is still constant time.

But the code is longer than necessary.

We can check row, column, and box constraints in a single pass.

For every filled cell, we need to answer three questions:

Have we seen this digit in this row?
Have we seen this digit in this column?
Have we seen this digit in this box?

If any answer is yes, the board is invalid.

Key Insight

Use three collections of sets:

rows[0..8]
cols[0..8]
boxes[0..8]

Each set stores digits already seen in that row, column, or box.

The only slightly tricky part is mapping a cell (r, c) to its 3 x 3 box index.

Rows 0, 1, 2 belong to box row 0.

Rows 3, 4, 5 belong to box row 1.

Rows 6, 7, 8 belong to box row 2.

The same idea applies to columns.

So:

box_index = (r // 3) * 3 + (c // 3)

For example:

Cell	Box index
`(0, 0)`	`0`
`(1, 4)`	`1`
`(2, 8)`	`2`
`(4, 1)`	`3`
`(4, 4)`	`4`
`(8, 8)`	`8`

Algorithm

Create:

rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]

Then scan every cell (r, c).

If the cell is ".", skip it.

Otherwise, let:

value = board[r][c]
box = (r // 3) * 3 + (c // 3)

If value already appears in rows[r], return False.

If value already appears in cols[c], return False.

If value already appears in boxes[box], return False.

Otherwise, add it to all three sets.

If the scan finishes, return True.

Correctness

Each filled cell belongs to exactly one row, exactly one column, and exactly one 3 x 3 box.

When the algorithm sees a digit, it checks the set for that row. If the digit is already there, then the row contains the same digit twice, so the board violates the row rule.

It also checks the set for that column. If the digit is already there, then the column contains the same digit twice, so the board violates the column rule.

It also checks the set for that box. If the digit is already there, then the 3 x 3 box contains the same digit twice, so the board violates the box rule.

If none of these checks fail, adding the digit records that this row, column, and box now contain the digit.

Therefore, any repeated digit in a row, column, or box is detected when its later occurrence is processed.

If the algorithm finishes without finding a repeated digit, then no row, column, or box rule is broken by the filled cells. So the board is valid.

Complexity

Metric	Value	Why
Time	`O(1)`	The board is always `9 x 9`
Space	`O(1)`	At most 81 filled cells are stored across fixed-size sets

If we generalize to an n x n board, the scan is O(n^2).

Implementation

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for r in range(9):
            for c in range(9):
                value = board[r][c]

                if value == ".":
                    continue

                box = (r // 3) * 3 + (c // 3)

                if value in rows[r]:
                    return False

                if value in cols[c]:
                    return False

                if value in boxes[box]:
                    return False

                rows[r].add(value)
                cols[c].add(value)
                boxes[box].add(value)

        return True

Code Explanation

We prepare one set for each row:

rows = [set() for _ in range(9)]

one set for each column:

cols = [set() for _ in range(9)]

and one set for each 3 x 3 box:

boxes = [set() for _ in range(9)]

Then we visit every cell:

for r in range(9):
    for c in range(9):

Empty cells do not affect validity.

if value == ".":
    continue

Compute the box index:

box = (r // 3) * 3 + (c // 3)

Then check whether this value was already seen in the same row, column, or box.

if value in rows[r]:
    return False

if value in cols[c]:
    return False

if value in boxes[box]:
    return False

If all checks pass, record the value.

rows[r].add(value)
cols[c].add(value)
boxes[box].add(value)

If no duplicate is found, the board is valid.

return True

Testing

def check(board: list[list[str]], expected: bool) -> None:
    actual = Solution().isValidSudoku(board)
    assert actual == expected, (actual, expected)

def run_tests():
    check(
        [
            ["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"],
        ],
        True,
    )

    check(
        [
            ["8","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"],
        ],
        False,
    )

    check(
        [
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
        ],
        True,
    )

    check(
        [
            ["1",".",".",".",".",".",".",".","1"],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
        ],
        False,
    )

    check(
        [
            ["1",".",".",".",".",".",".",".","."],
            [".","1",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
            [".",".",".",".",".",".",".",".","."],
        ],
        False,
    )

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Standard valid board	Confirms normal valid input
Duplicate in a column	Detects column violation
Empty board	Empty cells are ignored
Duplicate in a row	Detects row violation
Duplicate in a box	Detects `3 x 3` box violation