Start learning free

LESSON 122 OF 321 · BACKTRACKING

Sudoku Solver in Python with Time Complexity Analysis

Practice O(nn2) Read the full explanation

You get an unfinished Sudoku board with 9 rows and 9 columns. Each cell is a character. It is a digit from '1' to '9', or '.' for an empty cell.

Return the board with every empty cell filled in.

The finished board must follow three rules:

  1. Each row holds the digits 1 to 9 once.
  2. Each column holds the digits 1 to 9 once.
  3. Each 3 x 3 block holds the digits 1 to 9 once. The thick lines in the picture below mark the nine blocks.

The digits already on the board stay where they are.

 

Example 1:

382 132 745 567 657134 784 326 685 572

Input: board = [
  [".","3","8",".",".","2",".",".","."],
  [".","1",".","3",".",".","2",".","."],
  [".",".",".",".","7","4","5",".","."],
  [".",".",".",".","5","6",".","7","."],
  ["6",".","5","7",".","1","3",".","4"],
  [".","7",".","8","4",".",".",".","."],
  [".",".","3","2","6",".",".",".","."],
  [".",".","6",".",".","8",".","5","."],
  [".",".",".","5",".",".","7","2","."]
]
Output: [
  ["5","3","8","6","9","2","4","1","7"],
  ["4","1","7","3","8","5","2","6","9"],
  ["2","6","9","1","7","4","5","3","8"],
  ["3","8","4","9","5","6","1","7","2"],
  ["6","9","5","7","2","1","3","8","4"],
  ["1","7","2","8","4","3","6","9","5"],
  ["9","5","3","2","6","7","8","4","1"],
  ["7","2","6","4","1","8","9","5","3"],
  ["8","4","1","5","3","9","7","2","6"]
]
Explanation: The puzzle is drawn above.
It has exactly one solution, drawn below.
The digits you add are in blue.


  
  
  
  
    382
    132
    745
    567
    657134
    784
    326
    685
    572
  
  
    569417
    478569
    269138
    384912
    928
    123695
    957841
    724193
    841396
  

 

Constraints:

  • The board is always 9 rows of 9 cells.
  • A cell is a digit from '1' to '9' or '.' (empty).
  • Every puzzle you get has exactly one solution.

STEP 1 OF 29
    Ctrl + Enter to check

    PYTHON · BACKTRACKING

    Sudoku in Python, explained

    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:

    Keep going with Python1,600+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free