Sudoku?
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

Question

Sudoku?

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

Accepted Answer

I followed the backtracking approach. This is a common problem.

Accepted Answer

Brute Force

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.

Space Complexity: OtherExplanation:

O(K), where ‘K’ denotes the total number of empty cells in the given matrix.

We are checking the original matrix itself and the recursion stack can grow in the order of ‘K’ which can take max value as 9 * 9 = 81, the space complexity is approximately constant.

Time Complexity: OtherExplanation:

O(9 ^ K), where ‘K’ denotes the total number of empty cells in the given matrix.

The time complexity is exponential as for each cell we are trying all the digits from 1 to 9.

Accepted Answer

Backtracking

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.