# 36. Valid Sudoku
> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/arrays]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: done]
> [link:: https://leetcode.com/problems/valid-sudoku/]
> [up:: [[Leetcode MOC]]]
## 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.
**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"]]
```
**Output:** `true`
## Solution
### Mine
We can use the techniques from [[Spaces/Personal Projects/Leetcode/217. Contains Duplicate]] to efficiently check rows and columns: using a dictionary and ensuring that we don't find the same key more than once (filtering out the `"."`).
Each step is technically $O(n^2)$ but a Sudoku board is always 10x10, so that isn't really a practical problem to worry about - the actual time and space complexity is $O(9^2)$. Using a set and comparing to the original is also an option, but that would still require some filtering of the `"."`. The filtering is just when you're at that cell, do an equality check and continue the iteration.
#### Addressing the Subsquares
We have 9 rows and 9 columns. What if we had coordinates/indices for each of the subsquares: (0, 0), (0, 1), (0, 2), (1, 0), etc.? Then we'd have to convert the indices we have into the indices for the subsquares, and we'd know which individual cells go where.
How can we convert coordinate systems? Simple integer division by 3! e.g. (7, 3) would be in (2, 1). So then we can store this in a dictionary where the key is (r/3, c/3) and the value is the set of all numbers at that key.
#### Python
```python
def validate_board(board: List[List[str]]) -> bool:
rows = collections.defaultdict(set)
columns = collections.defaultdict(set)
subsquares = collections.defaultdict(set)
for r in range(9): # We can hardcode because it's constant
for c in range(9):
if board[r][c] == ".":
continue
if (
board[r][c] in rows[r]
or board[r][c] in columns[c]
or board[r][c] in subsquares[(r // 3, c // 3)]
):
return False
rows[r].add(board[r][c])
columns[c].add(board[r][c])
subsquares[(r // 3, c // 3)] = board[r][c]
return True
```
#### Rust
### LC's
## Things I Learned
---
You can transpose a list of lists with `zip`:
```python
list(map(list, zip(*l)))
```
## Scratchpad