Leetcode Problem - Sudoku Solver

Problem link: https://leetcode.com/problems/sudoku-solver/
Difficulty: Hard
Category: Backtracking

Step 1: Grasping the Problem

We have to design a [Sudoku] solver. The problem statement defined what is Sudoku and how it is played. The given board is always a fixed size of 9x9. So, the input is always a fixed board. In that case, whatever we do with the solution (unless we are doing terribly complicated things), it will be a O(1) solution.

In spite of the time complexity is O(1), we need to think of the total time the solution might take. For example, if you do a blind brute force, the total search space for the 9x9 board is going to be (9x9)^9 = 150094635296999121 ~ 1.5x10^17. So a naive brute force solution will not be feasible.

There are some restrictions on putting a value in an index in the board. So, we do not need to put all values from 0 to 9 to check if we can solve. This is a perfect example for Backtracking algorithms where you have a number of of constraints to check and if following the constraints for a particular set of values end-up in a dead end, then go back and change some of the values to try the next space.

Wikipedia has an amazing animation to demonstrate how backtracking works with sudoku.

Sudoku Backtracking Wikipedia

Step 2: Implement Board Validation Function

Before implementation of the solver itself, first we need to create a function that can be used to see if we can put a value on an index in the board. The function will take the board, a row, a col and finally a val to put into that index of the board.

1
def validate_board(self, board, row, col, val):

The function will first check if there is same value as val in the same row or column in the board. We can check this easily by looping through that row and column once at a time.

1
2
3
4
5
6
7
8
9
# Check if duplicate in row
for row_it in range(9):
    if board[row_it][col] == val:
        return False
    
# Check if duplicate in col
for col_it in range(9):
    if board[row][col_it] == val:
        return False

Then we will check if the same value as val also appears in the same 3x3 block. To do this, we will take the current block where row and col resides. Then we will iterate through the block and check accordingly.

1
2
3
4
5
6
7
# Check if block has duplicate
row_block = row - row%3
col_block = col - col%3
for row_it in range(3):
    for col_it in range(3):
        if board[row_block+row_it][col_block+col_it] == val:
            return False

Finally if none of these return False, we are sure that val at row, col position is a valid move. So we will return true.

1
2
# None of them return false. So satisfies
return True

Step 3: Base Conditions of Recursing Backtracking

We will start from the first element in the board. We will putting valid values in places and move forward. To do this, we will continuously put values, then increment col.

While incrementing col, we will reach at a point when col will be greater than 8 (out of the board). At that time, we reset col to zero and increment row. Finally row will go out of the board, so at that time, we will be sure that the board is solved.

1
2
3
4
5
6
if row == 9:
    # If all rows are complete, we have solved it!
    return True
if col == 9:
    # This column is complete, go to next row's first col
    return self.recursiveSolve(board, row+1, 0)

Also, if an index of the board is already filled by the problem, then we do not need to do anything at that index. So we will move forward.

1
2
3
if board[row][col] != '.':
    # This index is already filled
    return self.recursiveSolve(board, row, col+1)

Step 4: Implement Recursive Backtracking

For the backtracking, we will take numbers from 1 to 9 and fill each index of the board one by one. The problem gives us the board with characters in the indices. So we also need to put characters (or strings for python). For this, we will loop over the characters from ‘1’ to ‘9’.

1
for val in ['1', '2', '3', '4', '5', '6', '7', '8', '9']:

A more pythonic way of doing this is following.

1
for val in '123456789':

Then we will see if we can put val in the index with the help of our previously implemented function validate_board.

1
if self.validate_board(board, row, col, val):

If we can, we will put the value in the board and recursively go to the next index. And after continuously doing this, finally we will get an answer if puting val in this index results in a feasible board solution. If it is feasible, then we are done. If not, then we will have to backtrack. For backtracking we will again put a '.' in the index and continue with the next val.

1
2
3
4
5
6
7
# Put a correct value
board[row][col] = val
# Check if we can proceed to finish
if self.recursiveSolve(board, row, col+1):
    return True
# Couldn't finish, so BackTrack!
board[row][col] = '.'

Finally there will be at least one state for which, recursiveSolve will return True. For that case, we are returning True. And for the rest of the case, we will return False.

1
2
# Dead end in this path. So return false
return False

Step 5: Start the Backtracking

We will start the backtracking process from row=0 and col=0. Even if there may be already a value in that index, our backtracking function will take care of it.

1
2
3
4
5
6
def solveSudoku(self, board: [[str]]) -> None:
    """
    Modify board in-place
    """
    # Start solving from first index
    self.recursiveSolve(board, 0, 0)

This is the most known algorithm for solving Sudoku. The time complexity as already mentioned is O(1). The space is only the board size. The problem expects you to change the board in place so this solution is perfect. If you could not change the board and return a new one, you can do a slight modification to this program like copying the board before the backtracking and returning the board after the process.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def solveSudoku(self, board: [[str]]) -> [[str]]:
    """
    Modify board in-place
    """
    # Copy board
    board_copy = board.copy()
    # Start solving from first index
    self.recursiveSolve(board_copy, 0, 0)
    # Return the copy
    return board_copy

The complete solution of the problem is given by the following.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution:
    def solveSudoku(self, board: [[str]]) -> None:
        """
        Modify board in-place
        """
        # Start solving from first index
        self.recursiveSolve(board, 0, 0)
        
        
    def validate_board(self, board, row, col, val):
        # Check if duplicate in row
        for row_it in range(9):
            if board[row_it][col] == val:
                return False
            
        # Check if duplicate in col
        for col_it in range(9):
            if board[row][col_it] == val:
                return False
            
        # Check if block has duplicate
        row_block = row - row%3
        col_block = col - col%3
        for row_it in range(3):
            for col_it in range(3):
                if board[row_block+row_it][col_block+col_it] == val:
                    return False
        # None of them return false. So satisfies
        return True
    
    def recursiveSolve(self, board, row, col):
        if row == 9:
            # If all rows are complete, we have solved it!
            return True
        if col == 9:
            # This column is complete, go to next row's first col
            return self.recursiveSolve(board, row+1, 0)
        if board[row][col] != '.':
            # This index is already filled
            return self.recursiveSolve(board, row, col+1)
        
        # Try putting all values in 1-9
        for val in '123456789':
            if self.validate_board(board, row, col, val):
                # Put a correct value
                board[row][col] = val
                # Check if we can proceed to finish
                if self.recursiveSolve(board, row, col+1):
                    return True
                # Couldn't finish, so BackTrack!
                board[row][col] = '.'
        
        # Dead end in this path. So return false
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    void solveSudoku(vector<vector<char>> &board) {
        // Start solving from first index
        recursiveSolve(board, 0, 0);
    }

private:
    bool validateBoard(vector<vector<char>> &board, int row, int col, int val) {
        // Check if duplicate in row
        for(int rowI = 0; rowI < board.size(); rowI++)
            if(board[rowI][col] == val)
                return false;
            
        // Check if duplicate in col
        for(int colI = 0; colI < board.size(); colI++)
            if(board[row][colI] == val)
                return false;
        
        // Check if block has duplicate
        int rowBlock = row - row%3;
        int colBlock = col - col%3;
        for(int rowI = 0; rowI < 3; rowI++)
            for(int colI = 0; colI < 3; colI++)
                if(board[rowBlock+rowI][colBlock+colI] == val)
                    return false;
        
        // None of them return false. So satisfies
        return true;
    }

    bool recursiveSolve(vector<vector<char>> &board, int row, int col) {
        // If all rows are complete, we have solve it!
        if(row == 9)
            return true;

        // This column is done, go to next row's first col
        if(col == 9)
            return recursiveSolve(board, row+1, 0);

        // This index is already filled
        if(board[row][col] != '.')
            return recursiveSolve(board, row, col+1);
        
        // Try putting all values in 1-9
        for(char val = '1'; val <= '9'; val++) {
            if(validateBoard(board, row, col, val)) {
                // Put a correct value
                board[row][col] = val;
                // Check if we can proceed to finish
                if(recursiveSolve(board, row, col+1))
                    return true;
                // Couldn't finish, so BackTrack!
                board[row][col] = '.';
            }
        }
        // Dead end in this path, So return false
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    public void solveSudoku(char[][] board) {
        // Start solving from first index
        recursiveSolve(board, 0, 0);
    }

    private boolean validateBoard(char[][] board, int row, int col, int val) {
        // Check if duplicate in row
        for(int rowI = 0; rowI < board.length; rowI++)
            if(board[rowI][col] == val)
                return false;
            
        // Check if duplicate in col
        for(int colI = 0; colI < board.length; colI++)
            if(board[row][colI] == val)
                return false;
        
        // Check if block has duplicate
        int rowBlock = row - row%3;
        int colBlock = col - col%3;
        for(int rowI = 0; rowI < 3; rowI++)
            for(int colI = 0; colI < 3; colI++)
                if(board[rowBlock+rowI][colBlock+colI] == val)
                    return false;
        
        // None of them return false. So satisfies
        return true;
    }

    private boolean recursiveSolve(char[][] board, int row, int col) {
        // If all rows are complete, we have solve it!
        if(row == 9)
            return true;

        // This column is done, go to next row's first col
        if(col == 9)
            return recursiveSolve(board, row+1, 0);

        // This index is already filled
        if(board[row][col] != '.')
            return recursiveSolve(board, row, col+1);
        
        // Try putting all values in 1-9
        for(char val = '1'; val <= '9'; val++) {
            if(validateBoard(board, row, col, val)) {
                // Put a correct value
                board[row][col] = val;
                // Check if we can proceed to finish
                if(recursiveSolve(board, row, col+1))
                    return true;
                // Couldn't finish, so BackTrack!
                board[row][col] = '.';
            }
        }
        // Dead end in this path, So return false
        return false;
    }
}