# LeetCode 37: Sudoku Solver

## Problem Restatement

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

Empty cells are represented by:

```python
"."
```

We must fill the empty cells so that the final board satisfies Sudoku rules:

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

The problem guarantees that the input has exactly one solution.

We must modify the board in place.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A partially filled `9 x 9` Sudoku board |
| Output | Nothing returned |
| Required mutation | Fill the board in place |
| Empty cell | `"."` |
| Solution guarantee | Exactly one valid solution exists |

Function shape:

```python
def solveSudoku(board: list[list[str]]) -> None:
    ...
```

## Examples

Example input:

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

One valid solved board is:

```python
[
    ["5","3","4","6","7","8","9","1","2"],
    ["6","7","2","1","9","5","3","4","8"],
    ["1","9","8","3","4","2","5","6","7"],
    ["8","5","9","7","6","1","4","2","3"],
    ["4","2","6","8","5","3","7","9","1"],
    ["7","1","3","9","2","4","8","5","6"],
    ["9","6","1","5","3","7","2","8","4"],
    ["2","8","7","4","1","9","6","3","5"],
    ["3","4","5","2","8","6","1","7","9"],
]
```

## First Thought: Try Every Possibility

An empty cell can contain digits:

```python
1 to 9
```

So one direct idea is:

1. Find an empty cell.
2. Try every digit.
3. Continue solving the rest of the board.

If a choice eventually leads to a contradiction, undo it and try another digit.

This idea is called backtracking.

## Why Backtracking Fits Sudoku

Sudoku is a constraint problem.

Each decision restricts future decisions.

For example:

```python
board[r][c] = "5"
```

immediately affects:

- row `r`
- column `c`
- the `3 x 3` box containing `(r, c)`

A wrong guess may not fail immediately. It may fail many steps later.

So we need the ability to:

1. Make a choice.
2. Explore deeper.
3. Undo the choice if it fails.

That is exactly what recursive backtracking does.

## Key Insight

At every step, we only need to know:

1. Which digits already exist in the current row.
2. Which digits already exist in the current column.
3. Which digits already exist in the current box.

Instead of scanning the board repeatedly, maintain three collections of sets:

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

Each set stores digits already used there.

This lets validity checks become constant time.

The box index formula is:

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

## Algorithm

First, initialize the sets.

For every filled cell:

1. Add its digit to the corresponding row set.
2. Add its digit to the corresponding column set.
3. Add its digit to the corresponding box set.

Then define a recursive function:

```python
backtrack()
```

Inside `backtrack`:

1. Scan the board to find the next empty cell.
2. Try digits `"1"` through `"9"`.
3. For each digit:
   - Check whether it already exists in the row, column, or box.
   - If valid:
     - Place the digit.
     - Update the sets.
     - Recurse.
4. If recursion succeeds, return `True`.
5. Otherwise:
   - Undo the placement.
   - Remove the digit from the sets.
6. If no digit works, return `False`.

If no empty cells remain, the board is solved.

## Correctness

The algorithm only places digits that satisfy all Sudoku constraints for the current partial board.

Before placing a digit into cell `(r, c)`, it checks that the digit does not already appear in:

- row `r`
- column `c`
- the corresponding `3 x 3` box

Therefore, every intermediate board produced by the algorithm remains valid.

The recursive search explores all valid digit choices for each empty cell. If a choice later leads to a contradiction, the algorithm removes that digit and restores the previous state. This guarantees that failed partial solutions do not affect future exploration.

Because the search eventually tries every valid possibility, if a solution exists, the algorithm will eventually reach a fully filled valid board. When no empty cells remain, every row, column, and box satisfies Sudoku rules, so the board is solved correctly.

The problem guarantees exactly one solution, so the first complete valid board found is the correct answer.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | Exponential in the number of empty cells | Backtracking may explore many possibilities |
| Space | `O(81)` | Recursion depth and constraint sets are bounded by board size |

In practice, constraint pruning makes the search much faster than naive enumeration.

## Implementation

```python
class Solution:
    def solveSudoku(self, board: list[list[str]]) -> None:
        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)

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

        def backtrack() -> bool:
            for r in range(9):
                for c in range(9):
                    if board[r][c] != ".":
                        continue

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

                    for digit in "123456789":
                        if digit in rows[r]:
                            continue

                        if digit in cols[c]:
                            continue

                        if digit in boxes[box]:
                            continue

                        board[r][c] = digit

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

                        if backtrack():
                            return True

                        board[r][c] = "."

                        rows[r].remove(digit)
                        cols[c].remove(digit)
                        boxes[box].remove(digit)

                    return False

            return True

        backtrack()
```

## Code Explanation

We begin by creating constraint sets.

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

Each set stores digits already used there.

Then we scan the initial board.

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

For every filled cell, compute its box index.

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

Then record the digit.

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

The recursive function searches for an empty cell.

```python
if board[r][c] != ".":
    continue
```

For an empty cell, try every digit.

```python
for digit in "123456789":
```

Skip invalid digits immediately.

```python
if digit in rows[r]:
    continue
```

The same logic applies to columns and boxes.

When a digit is valid, place it:

```python
board[r][c] = digit
```

Then update the constraint sets.

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

Now recursively solve the remaining board.

```python
if backtrack():
    return True
```

If recursion fails, undo everything.

```python
board[r][c] = "."

rows[r].remove(digit)
cols[c].remove(digit)
boxes[box].remove(digit)
```

This restoration step is what makes backtracking work correctly.

If no digit works, return `False`.

When the scan finds no empty cells, the board is complete.

```python
return True
```

## Testing

```python
def run_tests():
    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"],
    ]

    expected = [
        ["5","3","4","6","7","8","9","1","2"],
        ["6","7","2","1","9","5","3","4","8"],
        ["1","9","8","3","4","2","5","6","7"],
        ["8","5","9","7","6","1","4","2","3"],
        ["4","2","6","8","5","3","7","9","1"],
        ["7","1","3","9","2","4","8","5","6"],
        ["9","6","1","5","3","7","2","8","4"],
        ["2","8","7","4","1","9","6","3","5"],
        ["3","4","5","2","8","6","1","7","9"],
    ]

    Solution().solveSudoku(board)

    assert board == expected

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard Sudoku puzzle | Confirms recursive solving works |
| Mixed empty and filled cells | Confirms constraint tracking |
| Deep recursion | Confirms backtracking restoration logic |
| Unique solution | Confirms the solver reaches the expected final board |