# LeetCode 36: Valid Sudoku

## Problem Restatement

We are given a `9 x 9` Sudoku board.

Each cell contains either:

```python
"." 
```

or a digit from:

```python
"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:

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

## Examples

Example 1:

```python
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:

```python
True
```

Example 2:

```python
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:

```python
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.

```python
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:

1. Have we seen this digit in this row?
2. Have we seen this digit in this column?
3. Have we seen this digit in this box?

If any answer is yes, the board is invalid.

## Key Insight

Use three collections of sets:

```python
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:

```python
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:

```python
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:

```python
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

```python
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:

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

one set for each column:

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

and one set for each `3 x 3` box:

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

Then we visit every cell:

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

Empty cells do not affect validity.

```python
if value == ".":
    continue
```

Compute the box index:

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

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

```python
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.

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

If no duplicate is found, the board is valid.

```python
return True
```

## Testing

```python
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 |