> ## 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.

# Valid Sudoku Python Solution with Tests

> Tested Python solution for LeetCode 36 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 36, Medium. Topics: Array, Hash Table, Matrix. [View on LeetCode](https://leetcode.com/problems/valid-sudoku/description/).

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

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

## Problem

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.

### 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: true
```

```
Input: 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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
```

### Constraints

* `board.length == 9`
* `board[i].length == 9`
* `board[i][j]` is a digit `1-9` or `'.'`.

## Solution

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

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(1) - fixed 9x9 board
    # Space: O(1) - fixed size sets
    def is_valid_sudoku(self, board: list[list[str]]) -> bool:
        rows: list[set[str]] = [set() for _ in range(9)]
        cols: list[set[str]] = [set() for _ in range(9)]
        boxes: list[list[set[str]]] = [[set() for _ in range(3)] for _ in range(3)]

        for i in range(9):
            for j in range(9):
                if board[i][j] != ".":
                    num = board[i][j]

                    if num in rows[i] or num in cols[j] or num in boxes[i // 3][j // 3]:
                        return False

                    rows[i].add(num)
                    cols[j].add(num)
                    boxes[i // 3][j // 3].add(num)

        return True
```

## Complexity

| Time                   | Space                  |
| ---------------------- | ---------------------- |
| O(1) - fixed 9x9 board | O(1) - fixed size sets |

## Tags

[Grind](/catalog/grind), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).