Given a partially filled two-dimensional integer array, fill all the empty cells such that each row, each column and each 3 x 3 subgrid (as highlighted below by bolder lines) has every digit from 1 to 9 exactly once.

Example

Input:

8 4 9 0 0 3 5 7 0

0 1 0 0 0 0 0 0 0

7 0 0 0 9 0 0 8 3

0 0 0 9 4 6 7 0 0

0 8 0 0 5 0 0 4 0

0 0 6 8 7 2 0 0 0

5 7 0 0 1 0 0 0 4

0 0 0 0 0 0 0 1 0

0 2 1 7 0 0 8 6 5

Output:

8 4 9 1 6 3 5 7 2 

3 1 5 2 8 7 4 9 6 

7 6 2 4 9 5 1 8 3 

1 5 3 9 4 6 7 2 8 

2 8 7 3 5 1 6 4 9 

4 9 6 8 7 2 3 5 1 

5 7 8 6 1 9 2 3 4 

6 3 4 5 2 8 9 1 7 

9 2 1 7 3 4 8 6 5

Notes

Input Parameters: The function has one parameter, a two-dimensional integer array. Outer array has nine rows. Each of the inner arrays has nine integers of one row. Empty cells of the sudoku board are represented by 0.

Output: Return a two-dimensional integer array with the empty values filled correctly.

Constraints:

• Size of the input array is exactly 9 x 9
• 0

‍

Optimal Solution

To solve this problem, we will use backtracking. Try each number from 1 to 9 in each empty cell one by one, check if the current position is safe, then recurse for the board with that particular cell filled. While continuing in a similar fashion, if all cells can be finished, then we have found the solution, else backtrack to the previous cell filled, try the next number from 1 to 9 in the loop, and proceed similarly. If all the digits in the loop have been tried and no answer has been found, backtrack more and keep continuing the same process. Please note that here we spend time exploring only the worthy options and not all the possible solutions.

Check the following diagrams

Diagram for problem statement:

If we start filling the board as we discussed, we will first fill 1 in the first empty cell (marked with blue colors), then next cell with 2, next with 6 (as 1,2,3,4 and 5 are not safe there).. and so on, we find that after filling 9 in the second row, the next cell cannot have any number ranging from 1 to 9, so we backtrack and increase the  previously filled cell by 1 and check for safety. Since the previously filled number is also 9 and at the end of the loop, we backtrack more to fill in 6 instead of 5 in the second row. This process continues until all the cells are filled correctly and the correct configuration is found.

Board configuration after all cells filled correctly:

Time Complexity:

The time complexity for solving sudoku using backtracking is tricky to calculate. The worst case time complexity is equal to the number of possible board configurations which is 9^81. This can be even boiled down to 9^k where k is the number of empty cells in the initial board configuration. Even now, we do not calculate all the possible options and prune a huge number of possibilities.

So, worst case time complexity is O(9^k).

Auxiliary Space Used:

O(1). Since we can have a maximum of 81 depth (81 empty cells) in the recursion function stack, the space required is constant.

Space Complexity:

O(1).