How do you approach Sudoku Solver?

Use backtracking - try numbers 1-9 in each empty cell.

What is the time complexity of Sudoku Solver?

Time complexity: O(9^(empty cells)) in the worst case, but pruning makes it much faster. Space complexity: O(81) for the board plus recursion stack.

What are common mistakes on Sudoku Solver?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Sudoku Solver

HardAlgorithms

Description

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The input is a 9x9 2D array where 0 represents an empty cell. Return the completed board.

Example 1

Input: board = [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,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]]

Constraints

- board.length == 9 - board[i].length == 9 - 0 <= board[i][j] <= 9 - The input board has exactly one solution.

Sudoku Solver: approach, complexity and pitfalls

A hard backtracking problem, graded against 7 test cases (5 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 3-step hint ladder

Use backtracking - try numbers 1-9 in each empty cell.
Before placing a number, check if it is valid in the current row, column, and 3x3 box.
If no valid number can be placed, backtrack to the previous cell.

The optimal approach

Show the approach: Backtracking

Iterate through each cell. When an empty cell (0) is found, try placing digits 1-9. For each digit, check validity against the row, column, and 3x3 sub-box. If valid, place the digit and recurse. If no digit works, reset to 0 and backtrack.

Time: O(9^(empty cells)) in the worst case, but pruning makes it much faster
Space: O(81) for the board plus recursion stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.