How do you solve Sudoku Solver on LeetCode?

Sudoku Solver (LeetCode #37) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: Sudoku is a constraint satisfaction problem, where each number placement affects the validity of other placements.

What is the brute force solution for Sudoku Solver?

The brute force approach for Sudoku Solver is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves trying every possible number in each empty cell until the Sudoku is solved. This method is straightforward but can be inefficient as it explores every possibility. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Sudoku Solver?

Sudoku Solver uses the following concepts: Array, Hash Table, Backtracking, Matrix. The recommended patterns to study are: Backtracking, Constraint Satisfaction.

What are the interview tips for Sudoku Solver?

Explain your thought process clearly as you implement the solution. Discuss edge cases, such as a completely filled board or a board with no solution. Practice writing clean and efficient code, as readability matters in interviews.

What are common mistakes when solving Sudoku Solver?

Failing to check all constraints when placing a number (row, column, and box). Not implementing backtracking correctly, leading to infinite loops or incorrect solutions.

#37

Sudoku Solver

Hard

ArrayHash TableBacktrackingMatrixBacktrackingConstraint Satisfaction

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(1)

💡

Intuition

Time O(n²)Space O(1)

The optimal solution uses backtracking efficiently by leveraging the constraints of Sudoku to minimize unnecessary checks. It fills cells one by one, backtracking only when necessary, which significantly reduces the number of attempts.

⚙️

Algorithm

5 steps

1Step 1: Create a helper function to check if placing a number in a cell is valid.
2Step 2: Use a recursive function to fill the board, starting from the first empty cell.
3Step 3: For each empty cell, try placing numbers from 1 to 9, checking validity.
4Step 4: If a number is valid, place it and recursively attempt to fill the next empty cell.
5Step 5: If the board is completely filled, return true. If not, backtrack by removing the number.

solution.py26 lines

1def solveSudoku(board):
2    def isValid(board, row, col, num):
3        for i in range(9):
4            if board[row][i] == num or board[i][col] == num:
5                return False
6        startRow, startCol = 3 * (row // 3), 3 * (col // 3)
7        for i in range(3):
8            for j in range(3):
9                if board[startRow + i][startCol + j] == num:
10                    return False
11        return True
12
13    def solve(board):
14        for row in range(9):
15            for col in range(9):
16                if board[row][col] == '.':
17                    for num in '123456789':
18                        if isValid(board, row, col, num):
19                            board[row][col] = num
20                            if solve(board):
21                                return True
22                            board[row][col] = '.'
23                    return False
24        return True
25
26    solve(board)

ℹ

Complexity note: The time complexity remains O(n²) because we still check each cell and each number. However, the backtracking reduces the number of attempts significantly compared to brute force. Space complexity is O(1) as we are not using any additional data structures.

1Sudoku is a constraint satisfaction problem, where each number placement affects the validity of other placements.
2Backtracking is a powerful technique for solving problems where you need to explore multiple possibilities.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.