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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sudoku Solver

Difficulty: Hard

Problem Description

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.

Key Insights

  • The Sudoku board consists of a fixed size (9x9) which allows for a systematic approach.
  • Backtracking is an efficient way to explore possible solutions by trying each number in empty cells and reverting if a conflict arises.
  • Constraints ensure that there is always a unique solution, simplifying the solution process.

Space and Time Complexity

Time Complexity: O(9^(n*n)) in the worst case, where n is the dimension of the board (n=9). Space Complexity: O(n^2) due to the recursion stack in the backtracking approach.

Solution

The solution employs a backtracking algorithm to fill in the empty cells of the Sudoku board. The algorithm checks each empty cell (denoted by '.') and tries inserting digits from 1 to 9. For each placement, it verifies if the digit is valid based on Sudoku rules. If a number leads to a solution, it proceeds; if not, it backtracks and tries the next number. This continues until the board is completely filled.

Code Solutions

def solveSudoku(board):
    def is_valid(board, row, col, num):
        # Check the row and column
        for i in range(9):
            if board[row][i] == num or board[i][col] == num:
                return False
        # Check the 3x3 sub-box
        box_row = row // 3 * 3
        box_col = col // 3 * 3
        for i in range(3):
            for j in range(3):
                if board[box_row + i][box_col + j] == num:
                    return False
        return True

    def backtrack(board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if is_valid(board, i, j, num):
                            board[i][j] = num
                            if backtrack(board):
                                return True
                            board[i][j] = '.'  # Reset if not a solution
                    return False  # Trigger backtracking
        return True  # Solved

    backtrack(board)

# 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)
← Back to All Questions