# Sudoku Solver Problem

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).

``````
// This function checks if the number is safe to put on the board at row, col
private static boolean isSafe(List> board, int row, int col, int num) {

// Check in the row, if the number is already present
for (int i = 0; i < 9; i++) {
if (board.get(row).get(i) == num) {
return false;
}
}

// Check in the column, if the number is already present
for (int i = 0; i < 9; i++) {
if (board.get(i).get(col) == num) {
return false;
}
}

// Check in the corresponding 3 x 3 box, if the number is already present
int boxRowStart = row - row % 3;
int boxColStart = col - col % 3;

for (int i = boxRowStart; i < boxRowStart + 3; i++) {
for (int j = boxColStart; j < boxColStart + 3; j++) {
if (board.get(i).get(j) == num) {
return false;
}
}
}

return true;
}

// Utility function to solve the sudoku board
private static boolean solveSudokuUtil(List> board) {

// Check for next empty space
int row = 0;
int col = 0;
boolean isEmpty = true;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// 0 signifies the empty cell
if (board.get(i).get(j) == 0) {
row = i;
col = j;

isEmpty = false;
break;
}
}
if (!isEmpty) {
break;
}
}

// no empty space left, a solution is found
if (isEmpty) {
return true;
}

// Loop through 1 to 9 and check which number is feasible to be placed in the found empty cell
for (int num = 1; num <= 9; num++) {

if (isSafe(board, row, col, num)) {
board.get(row).set(col, num);

// If a number is found to be safe, recurse to fill the next empty cell
if (solveSudokuUtil(board)) {
return true;

} else {
// If this number does not lead to a solution, try next number in the loop or backtrack to the previous element.
board.get(row).set(col, 0);
}
}
}
return false;
}

// Function to print the board
private static void print(List> board) {
for (int r = 0; r < 9; r++) {
for (int d = 0; d < 9; d++) {
System.out.print(board.get(r).get(d));
System.out.print(" ");
}
System.out.print("\n");
}
System.out.print("\n");
}

public static List> sudokuSolver(List> board) {

solveSudokuUtil(board);
return board;
}
``````

All Posts