# Sudoku?

Posted: 23 Sep, 2020

Difficulty: Moderate

#### You have been given a 9 X 9 2D matrix 'MATRIX' with some cells filled with digits(1 - 9), and some empty cells (denoted by 0).

#### You need to find whether there exists a way to fill all the empty cells with some digit(1 - 9) such that the final matrix is a valid Sudoku solution.

#### A Sudoku solution must satisfy all the following conditions-

```
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, 3 x 3 sub-matrices of the matrix.
```

##### Note

```
1. There will always be a cell in the matrix which is empty.
2. The given initial matrix will always be consistent according to the rules mentioned in the problem statement.
```

##### Input Format:

```
The first line contains a single integer 'T' denoting the number of test cases.
Then 'T' test cases follow.
Every test case contains 9 lines, with each line containing 9 single space-separated digits (0, if the cell is empty or a digit (1 - 9) otherwise).
```

##### Output Format:

```
For each test case, print a single line containing “yes”(without quotes), if there exists a Sudoku solution or “no” (without quotes) otherwise. Note the lowercase format of the output.
```

##### Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= 'T' <= 5
N = 9
0 <= MATRIX[i][j] <= 9
Where 'N' denotes the size of the given square matrix.
Time Limit: 1sec
```

Approach 1

- For all the empty cells of the matrix try all the arrangements of the digits (1 - 9) in those cells i.e filling all the empty cells with some digit.
- For each arrangement, check whether the matrix now violates any of the given rules, if it does, then check for some other arrangement, otherwise, we found a solution.
- If after checking all the arrangements/configurations, we can’t find a solution, then there doesn’t exist any solution to the given input.

Approach 2

- Instead of trying all digits in the empty cell, we will try and find a solution using only those digits which don't violate any of our conditions when placed in the cell.
- Thus, before assigning a number to an empty cell, check if it satisfies all the rules. If yes then assign this number to the cell and then recursively check if it leads to a successful filing of all the empty cells, otherwise try some other valid number for the current cell and then repeat the recursion.
- If at some stage we can't find a number which is valid for the current empty cell or which leads us to the solution, then we
**bactrack**i.e move one step behind and check for some other possible candidates(numbers) for the cell. - The backtracking might continue until we dont get a valid configuration of the matrix or if it has tried all the possibilities. If the latter happens, then there is no solution for the given input matrix.