---
# System prepended metadata

title: 36_Valid_Sudoku
tags: [leetcode]

---

# 36_Valid_Sudoku
###### tags: `leetcode`
## Problem Statement
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
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.
 
- Example 1:
![](https://i.imgur.com/HnWy6Nq.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
- Example 2:

> 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 or '.'.
## Solution
- To deal with it, the necesary thing is to store the apparances of numbers in each set combinations criteria.
- Save the record in the std ```set```.
```cpp=
unordered_set<char> rowSet[N];
unordered_set<char> colSet[N];
unordered_set<char> squareSet[N];
```
- Count whether the value exists in the set, if not, return false.
```cpp=
int sPos = (r / 3) * 3 + c / 3;
if (rowSet[r].count(val) || colSet[c].count(val) || squareSet[sPos].count(val))
    return false;
```
