Algocademy Logo

Course Outline

Sudoku Solver in Python with Time Complexity Analysis


Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  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-boxes of the grid.

The '.' character indicates empty cells.

 

Example 1:



Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

 

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.

Understanding the Problem

The core challenge of solving a Sudoku puzzle lies in ensuring that each number from 1 to 9 appears exactly once in each row, column, and 3x3 sub-box. This problem is significant in various fields such as constraint satisfaction problems, artificial intelligence, and recreational mathematics. A common pitfall is not considering all constraints simultaneously, leading to invalid solutions.

Approach

To solve the Sudoku puzzle, we can use a backtracking algorithm. This approach involves trying to place a number in an empty cell, checking if it leads to a valid solution, and backtracking if it doesn't. Here's a step-by-step breakdown:

  1. Identify the first empty cell.
  2. Try placing each number from 1 to 9 in the cell.
  3. Check if placing the number violates any Sudoku rules.
  4. If it doesn't, move to the next empty cell and repeat the process.
  5. If placing a number leads to a violation, backtrack and try the next number.
  6. Continue this process until the board is completely filled.

Algorithm

Here's a detailed breakdown of the backtracking algorithm:

def solve_sudoku(board):
    def is_valid(board, row, col, num):
        # Check if the number is not repeated in the current row, column, and 3x3 sub-box
        for i in range(9):
            if board[row][i] == num or board[i][col] == num:
                return False
            if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
                return False
        return True

    def solve(board):
        for row in range(9):
            for col in range(9):
                if board[row][col] == '.':
                    for num in '123456789':
                        if is_valid(board, row, col, num):
                            board[row][col] = num
                            if solve(board):
                                return True
                            board[row][col] = '.'
                    return False
        return True

    solve(board)

Code Implementation

Here's the complete Python code to solve the Sudoku puzzle:

def solve_sudoku(board):
    def is_valid(board, row, col, num):
        # Check if the number is not repeated in the current row, column, and 3x3 sub-box
        for i in range(9):
            if board[row][i] == num or board[i][col] == num:
                return False
            if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
                return False
        return True

    def solve(board):
        for row in range(9):
            for col in range(9):
                if board[row][col] == '.':
                    for num in '123456789':
                        if is_valid(board, row, col, num):
                            board[row][col] = num
                            if solve(board):
                                return True
                            board[row][col] = '.'
                    return False
        return True

    solve(board)

Complexity Analysis

The time complexity of the backtracking algorithm is O(9^(n*n)), where n is the size of the board (9 in this case). This is because, in the worst case, we might have to try all 9 numbers for each cell. The space complexity is O(n*n) due to the recursion stack.

Edge Cases

Potential edge cases include:

  • A nearly complete board with only one empty cell.
  • A board with multiple empty cells but only one valid solution.

Our algorithm handles these cases by ensuring that it checks all possible numbers for each empty cell and backtracks if necessary.

Testing

To test the solution comprehensively, we can use a variety of test cases:

  • Simple cases with only a few empty cells.
  • Complex cases with many empty cells.
  • Edge cases as mentioned above.

We can use Python's unittest framework to automate the testing process.

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

  • Break down the problem into smaller, manageable parts.
  • Consider all constraints and ensure they are satisfied simultaneously.
  • Practice solving similar problems to improve problem-solving skills.

Conclusion

Solving a Sudoku puzzle using a backtracking algorithm is a classic example of constraint satisfaction problems. Understanding and implementing this algorithm helps in developing problem-solving skills and understanding the importance of considering all constraints simultaneously.

Additional Resources

For further reading and practice problems, consider the following resources: