Sudoku Solver
You have been given a 9x9 2d integer matrix 'MAT' representing a Sudoku puzzle. The empty cells of the Sudoku are filled with zeros, and the rest of the cells are filled with integers from 1 to 9. Your task is to fill all the empty cells such that the final matrix represents a Sudoku solution.

Note:

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, 3x3 sub-grids of the grid. You can also assume that there will be only one sudoku solution for the given matrix.

Input Format:

The input consists of 9 lines. Each line contains 9 single space-separated integers representing a row of the matrix. An empty cell is represented by 0.

Constraints :

Size of MAT is 9x9 0

Question

Sudoku Solver

You have been given a 9x9 2d integer matrix 'MAT' representing a Sudoku puzzle. The empty cells of the Sudoku are filled with zeros, and the rest of the cells are filled with integers from 1 to 9. Your task is to fill all the empty cells such that the final matrix represents a Sudoku solution.

Note:

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, 3x3 sub-grids of the grid.

You can also assume that there will be only one sudoku solution for the given matrix.

Input Format:

The input consists of 9 lines. Each line contains 9 single space-separated integers representing a row of the matrix. An empty cell is represented by 0.

Constraints :

Size of MAT is 9x9
0 <= MAT[i][j] <= 9

where an empty cell is given by 0 in the matrix.

Output Format :

The output is consists of 9 lines. Each line contains 9 single space-separated integers where the empty cells from the input matrix are replaced by some integers.

Note

You are not required to print anything, and it has already been taken care of. Just implement the function.

Accepted Answer

Naive Backtracking

The naive or brute force approach will be to try every possible configuration of numbers from 1 to 9 for each of the empty cells. After filling all the empty cells in the matrix, we check that the matrix is a valid sudoku solution or not. If we don’t find it valid, we keep checking it for the next configurations recursively until we find one.

Space Complexity: O(1)Explanation:

O(1), i.e., constant space complexity.

In the worst-case scenario, our recursion stack can grow maximum till size 9*9 = 81, which is constant.

Time Complexity: O(1)Explanation:

O(9^K), Where ‘K’ is the number of empty cells in the given 2d matrix.

As we are trying all the numbers from 1 to 9 for every empty cell, our time complexity is exponential and quite high.

Accepted Answer

Optimized Backtracking

Backtracking is a general algorithm for finding all (or some) solutions to a problem that incrementally builds candidates to the solution. As soon as it determines that a candidate can not possibly be the solution to the problem, it abandons it (“backtracks”). We can solve this problem using backtracking.

Before we assign a number in an empty cell, we will check whether it is safe to assign. We will have an ‘isSafe’ function for it, which will check that the same number is not present in the current row, current column, and in the current sub-grid.
If it is safe to assign the number, we will assign it to the empty cell and recursively check whether this assignment leads to a solution or not.
If this assignment doesn’t lead to a solution, then we will try the next number for the current empty cell. And if none of the numbers from 1 to 9 leads to a solution, we will return false.