> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Sudoku Solver Python Solution with Tests

> Tested Python solution for LeetCode 37 with 13 pytest cases. Generate a practice environment with lcpy.

LeetCode 37, Hard. Topics: Array, Hash Table, Backtracking, Matrix. [View on LeetCode](https://leetcode.com/problems/sudoku-solver/description/).

Generate this problem as a practice environment: tested reference solution, 13 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 37   # by problem number
lcpy gen -s sudoku_solver   # by problem name
```

## Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy **all of the following rules**:

1. Each of the digits `1-9` must occur exactly once in each row.
2. Each of the digits `1-9` must occur exactly once in each column.
3. Each of the digits `1-9` must occur exactly once in each of the 9 `3x3` sub-boxes of the grid.

The `'.'` character indicates empty cells.

### Examples

![Example 1](https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png)

```
Input: 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"]]
Output: [["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"]]
Explanation: The input board is shown above and the only valid solution is shown below:

![Solution](https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png)
```

### Constraints

* board.length == 9
* board\[i].length == 9
* board\[i]\[j] is a digit or '.'.
* It is guaranteed that the input board has only one solution.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/sudoku_solver/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/sudoku_solver/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(9^(n)) where n = number of empty cells, pruned heavily by validity checks
    # Space: O(n) recursion stack + O(1) bookkeeping sets
    def solve_sudoku(self, board: list[list[str]]) -> None:
        rows = [set[str]() for _ in range(9)]
        cols = [set[str]() for _ in range(9)]
        boxes = [set[str]() for _ in range(9)]
        empties: list[tuple[int, int]] = []

        for r in range(9):
            for c in range(9):
                ch = board[r][c]
                if ch == ".":
                    empties.append((r, c))
                else:
                    rows[r].add(ch)
                    cols[c].add(ch)
                    boxes[(r // 3) * 3 + c // 3].add(ch)

        def backtrack(idx: int) -> bool:
            if idx == len(empties):
                return True
            r, c = empties[idx]
            b = (r // 3) * 3 + c // 3
            for d in map(str, range(1, 10)):
                if d in rows[r] or d in cols[c] or d in boxes[b]:
                    continue
                board[r][c] = d
                rows[r].add(d)
                cols[c].add(d)
                boxes[b].add(d)
                if backtrack(idx + 1):
                    return True
                board[r][c] = "."
                rows[r].discard(d)
                cols[c].discard(d)
                boxes[b].discard(d)
            return False

        backtrack(0)
```

## Complexity

| Time                                                                        | Space                                        |
| --------------------------------------------------------------------------- | -------------------------------------------- |
| O(9^(n)) where n = number of empty cells, pruned heavily by validity checks | O(n) recursion stack + O(1) bookkeeping sets |

## Tags

[Grind](/catalog/grind).