Sudoku Solver - Leetcode Solution

The Sudoku Solver problem on LeetCode is a classic backtracking problem, where we are supposed to find a solution for a given Sudoku board. The problem statement requires us to fill the board with numbers from 1 to 9, such that each row, column, and 3 x 3 sub-grid contains all the numbers from 1 to 9.

The suggested approach is to use backtracking to place a number in the empty cells of the Sudoku board, and to keep checking if the number satisfies the constraints of the game. The given Sudoku board can have multiple solutions, and we need to find all of them.

Let us first discuss the algorithm for solving this problem:

Algorithm:

• Define a function called solveSudoku that takes the initial Sudoku board as input and returns the solved board.
• Create a helper function isValid to check the validity of the number in a particular position of the board.
• Iterate through each cell of the board.
• If the cell is empty, iterate from 1 to 9 and try placing each number in the cell.
• Check if the number placed in the cell is valid by calling the isValid method.
• If the number is valid, recursively fill the rest of the board using the same approach until the board is completely filled.
• If the placement of the number leads to an invalid board, then backtrack and try the next number.
• If all the numbers from 1 to 9 have been tried and no number leads to a valid solution, then backtrack to the previous cell and try the next number from there.
• If there are no empty cells left on the board and the board satisfies all the constraints, then we have found a valid solution.

Now, let us implement the above algorithm in Python.

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def isValid(row, col, num):
            # Check if num already exists in row
            for i in range(9):
                if board[row][i] == num:
                    return False
            # Check if num already exists in column
            for i in range(9):
                if board[i][col] == num:
                    return False
            # Check if num already exists in 3x3 sub-grid
            row_start = (row // 3) * 3
            col_start = (col // 3) * 3
            for i in range(row_start, row_start + 3):
                for j in range(col_start, col_start + 3):
                    if board[i][j] == num:
                        return False
            return True
        
        def solve():
            for row in range(9):
                for col in range(9):
                    if board[row][col] == '.':
                        for num in range(1, 10):
                            if isValid(row, col, str(num)):
                                board[row][col] = str(num)
                                if solve():
                                    return True
                                board[row][col] = '.'
                        return False
            return True
        
        solve()

Let us go through the code snippet step by step.

• We define a function isValid that takes the row, column, and number as input, and checks if the placement of the given number is valid in that cell.
• We define the solve function that iterates through all cells of the board, and tries to fill the empty cells with numbers from 1 to 9.
• We use recursion to fill the rest of the board using the same approach until the board is completely filled.
• We use backtracking to undo the previous placement of the number if it does not lead to a valid solution.
• Finally, we call the solve function to solve the Sudoku board.

The time complexity of this algorithm is O(9^(nn)), where n is the side of the board, which is typically 9. The space complexity is O(nn).

In conclusion, we have discussed the approach to solve the Sudoku Solver problem on LeetCode using backtracking. The above solution allows us to find all the possible solutions of the given Sudoku board.

1