We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sudoku Solver

Number: 37

Difficulty: Hard

Paid? No

Companies: Google, Bloomberg, Microsoft, Amazon, Confluent, Meta, Intuit, Goldman Sachs, Zoho, Apple, Citadel, Adobe, Riot Games, Oracle, DoorDash, Cadence, Uber, Snap

Problem Description

Write a program to solve a Sudoku puzzle by filling the empty cells in a 9x9 board so that every row, every column, and every 3x3 sub-box contains the digits 1 through 9 exactly once. The board input uses the '.' character to indicate empty cells, and it is guaranteed that the puzzle has only one solution.

Key Insights

  • Use backtracking to explore digit placements for each empty cell.
  • Validate placements by ensuring that the chosen digit is not already present in the corresponding row, column, or 3x3 sub-box.
  • Employ recursion to fill the board incrementally and backtrack upon encountering invalid configurations.
  • Although the worst-case time complexity is exponential, the fixed board size (9x9) keeps the problem computationally manageable.

Space and Time Complexity

Time Complexity: In the worst-case scenario, the algorithm can explore up to O(9^(n)) possibilities where n is the number of empty cells. However, since n is at most 81 and many branches are pruned early, the practical runtime is far less. Space Complexity: O(n) due to the recursion stack, where n is the number of empty cells; given the board’s fixed size, this space is constant in practice.

Solution

The solution uses a backtracking approach. For each empty cell on the board, we attempt to place a digit from '1' to '9'. Before placing a digit, we check if the placement is valid by ensuring that:

  1. The digit is not already present in the same row.
  2. The digit is not already present in the same column.
  3. The digit is not already present in the corresponding 3x3 sub-box.

If a valid digit is found, we place it on the board and recursively attempt to solve the rest of the board. If no valid digit can be placed, the algorithm backtracks by reverting the last move and trying a different digit. This recursive search continues until the board is completely filled with a valid Sudoku configuration.

Code Solutions

def solveSudoku(board):
    # Check if placing the digit 'char' at board[row][col] is valid
    def is_valid(row, col, char):
        for i in range(9):
            # Check the row
            if board[row][i] == char:
                return False
            # Check the column
            if board[i][col] == char:
                return False
            # Check the 3x3 sub-box
            sub_row = 3 * (row // 3) + i // 3
            sub_col = 3 * (col // 3) + i % 3
            if board[sub_row][sub_col] == char:
                return False
        return True

    # Backtracking function to fill the board
    def backtrack():
        for row in range(9):
            for col in range(9):
                if board[row][col] == '.':
                    for char in map(str, range(1, 10)):
                        if is_valid(row, col, char):
                            board[row][col] = char  # Place the digit
                            if backtrack():
                                return True     # Recurse; if solution found, bubble up True
                            board[row][col] = '.'    # Backtrack if not valid further down
                    return False   # No valid digit found; trigger backtracking
        return True   # Board completely filled

    backtrack()

# Example usage:
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"]]
solveSudoku(board)
print(board)
← Back to All Questions