# 36. Valid Sudoku

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

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

<pre><code><strong>Input: board = 
</strong>[["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"]]
<strong>Output: true
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: board = 
</strong>[["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"]]
<strong>Output: false
</strong><strong>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.
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
Just check using BruteForce

Just that, 

For checking in sub-boxes
To divide in particular 

Use (row/3) * 3 + col /3
To find the respective index num, its just converting 2D to 1D

```

### Links

<https://leetcode.com/problems/valid-sudoku/description/>

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // Check for row
        for(int row=0; row<9; row++){
            unordered_set<char> checkrow;
            for(int col=0; col<9; col++){
                if(board[row][col] != '.' and checkrow.find(board[row][col]) != checkrow.end())
                    return false;

                checkrow.insert(board[row][col]);
            }
        }

        // Check for col
        for(int row=0; row<9; row++){
            unordered_set<char> checkcol;
            for(int col=0; col<9; col++){
                if(board[col][row] != '.' and checkcol.find(board[col][row]) != checkcol.end())
                    return false;

                checkcol.insert(board[col][row]);
            }
        }

        //Check for buckets
        vector<unordered_set<char>> buck(9); 
        for(int row=0; row<9; row++){
            for(int col=0; col<9; col++){
                int pos = (row/3)*3 + col/3;

                if(board[row][col] != '.' and buck[pos].find(board[row][col]) != buck[pos].end())
                    return false;

                buck[pos].insert(board[row][col]);
            }
        }

        return true;
    }
};
```

{% endcode %}

### Approach 2:

```
Using Set , Short code
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<set<int>> rows(9), cols(9), blocks(9);
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                
                if (board[i][j] == '.') continue;
                
                int curr = board[i][j] - '0';
                if (rows[i].count(curr) || cols[j].count(curr) || blocks[(i/3)*3+j/3].count(curr)) 
                    return false;
                
                rows[i].insert(curr);
                cols[j].insert(curr);
                blocks[(i/3)*3+j/3].insert(curr);
            }
        }
        
        return true;
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###