37. Sudoku Solver — DSA Atlas

HardBacktrackingDFS backtracking with row/column/box constraint setsConstrained cell filling with backtracking

Sudoku Solver

Fill a partially completed 9x9 Sudoku board in place so that every row, every column, and each of the nine 3x3 sub-boxes contains the digits 1-9 exactly once. Empty cells are marked with '.'; a unique solution is guaranteed.

Open official problem prompt ↗

In plain English

Complete the grid so all Sudoku rules hold, mutating the given board in place.

Picture it like this

Like solving a crossword in pen you can erase: pencil in a letter that fits every crossing word, keep going, and rub it out the moment a later square has no legal option.

Example

Input: 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"]]
Output: First row becomes ["5","3","4","6","7","8","9","1","2"] and the whole board is fully and validly filled.
Why: Every row, column, and 3x3 box now holds 1-9 once; the given clues are unchanged.

Constraints

board.length == 9board[i].length == 9board[i][j] is a digit 1-9 or '.'It is guaranteed that the input board has exactly one solution

Pattern lesson

See the pattern, then code

Constrained cell filling with backtracking

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. Track which digits are already used in each row, column, and box with sets so validity of a candidate is O(1); place a digit only if it violates none of the three sets, then recurse and undo.

New words, made simpleKnow these before the algorithm

Backtracking: Try a choice, recurse, and undo it if it cannot lead to a full solution.
Constraint set: A set of digits already used in a given row, column, or box, giving O(1) legality checks.
Box index: Which 3x3 sub-grid a cell belongs to, computed as (r // 3) * 3 + c // 3.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Re-scan validity each placement

Correct but each check re-walks 27 cells, wasting work that a set makes O(1).

For each candidate digit, loop across the row, column, and box to check for conflicts.

Time O(9^m * 27)Space O(m)

Best choiceBacktracking with row/col/box sets

O(1) legality checks and cheap undo make this the standard efficient solver.

Maintain three arrays of sets so a candidate is legal iff it is in none of them; place, recurse, undo.

Time O(9^m) with strong pruningSpace O(m)

The rule we keep true

Invariant

At every recursion level the partially filled board is fully consistent: no row, column, or box contains a repeated digit.

Why this is correct

Reasoning

Digits are only ever placed when legal, so any completed board is valid; because the search exhaustively tries every legal digit in every empty cell and the puzzle has a unique solution, it is guaranteed to be reached, and undoing on failure guarantees no dead-end pollutes later attempts.

The algorithm in three movesSay these aloud before coding

1Scan the board once, recording existing digits into rows/cols/boxes sets and collecting empty cells

cell (0,2) empty, box0 = {5,3,6,9,8}

2Recurse over empty cells by index

candidates absent from row0/col2/box0 -> 1,2,4

3For each cell try digits 1-9 that are absent from its row, column, and box sets

try 4 -> add to sets -> recurse to (0,3)

4Place the digit, add to all three sets, recurse; if the recursion fails, remove it and try the next

5Return True when every empty cell is filled

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readthe 9x9 board

2 · Askwhich cells are empty and what is already used?

3 · Update staterows/cols/boxes sets seeded; empties list built

4 · Resultrecursion starts at empties[0] = (0,2)

Key takeaway

Filling the first empty cell (0,2): only digits missing from its row, column, and 3x3 box are candidates.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-16Seed constraints
One pass records existing digits into the three set arrays and gathers empty coordinates to fill.
2
Lines 17-19Base case
When the index reaches the number of empties, every cell is filled and we report success.
3
Lines 20-31Try, recurse, undo
Skip digits present in row/col/box; otherwise place, update sets, recurse, and on failure remove the digit and its set entries.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A nearly full board with a single empty cell
Clues that force long chains before any conflict appears
Boards where the first few digits at a cell all fail and only the last works

Common beginner mistakes

Forgetting to remove the digit from all three sets when undoing, corrupting later branches
Miscomputing the box index (using r//3 + c//3 instead of (r//3)*3 + c//3)
Returning without propagating the True/False signal, so the solver keeps searching after it is solved

Check your understanding

Why store empty cells in a list instead of scanning for the next '.' inside the recursion?

PyPython 3 · solution.py

Optimal

1class Solution:2    def solveSudoku(self, board: list[list[str]]) -> None:3        rows = [set() for _ in range(9)]4        cols = [set() for _ in range(9)]5        boxes = [set() for _ in range(9)]6        empties = []7        for r in range(9):8            for c in range(9):9                v = board[r][c]10                if v == '.':11                    empties.append((r, c))12                else:13                    rows[r].add(v)14                    cols[c].add(v)15                    boxes[(r // 3) * 3 + c // 3].add(v)16        def backtrack(i: int) -> bool:17            if i == len(empties):18                return True19            r, c = empties[i]20            b = (r // 3) * 3 + c // 321            for d in '123456789':22                if d in rows[r] or d in cols[c] or d in boxes[b]:23                    continue24                board[r][c] = d25                rows[r].add(d); cols[c].add(d); boxes[b].add(d)26                if backtrack(i + 1):27                    return True28                board[r][c] = '.'29                rows[r].discard(d); cols[c].discard(d); boxes[b].discard(d)30            return False31        backtrack(0)

Time complexityO(9^m) worst case where m is the number of empty cells, pruned heavily by the three constraint setsOptimized

Space complexityO(m) recursion depth plus O(1) fixed-size constraint setsExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftUber

Sudoku Solver

Sudoku Solver

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking