LeetCode #37 Hard

Sudoku Solver

Fill the empty cells of a 9×9 Sudoku so each row, column, and 3×3 box holds digits 1–9 exactly once.

backtrackingmatrix

02

Intuition

💡

Take the first empty cell, try each digit that doesn't clash with its row, column, or box, and recurse. A cell with no legal digit proves an earlier guess wrong — undo and try the next. Constraint checks kill branches so fast the 9^81 space collapses.

03

Approach

1

Scan for the next blank

Solve cells in reading order; the recursion's state is just 'first blank from here'.

2

Try digits with a validity check

A digit is legal if absent from the cell's row, column, and 3×3 box (box index = (r//3)*3 + c//3).

3

Recurse, undo on failure

Place, recurse; if the sub-board is unsolvable, erase and continue. True bubbles up when no blanks remain.

04

Solution & live demo

python

▶1class Solution:
▶2    def solveSudoku(self, board):
▶3        def legal(r, c, ch):
▶4            br, bc = 3 * (r // 3), 3 * (c // 3)
▶5            for k in range(9):
▶6                if board[r][k] == ch or board[k][c] == ch: return False
▶7                if board[br + k // 3][bc + k % 3] == ch: return False
▶8            return True
▶9        def solve():
▶10            for r in range(9):
▶11                for c in range(9):
▶12                    if board[r][c] == ".":
▶13                        for ch in "123456789":
▶14                            if legal(r, c, ch):
▶15                                board[r][c] = ch
▶16                                if solve(): return True
▶17                                board[r][c] = "."
▶18                        return False
▶19            return True
▶20        solve()

05

Edge cases

Board already complete

No blank found → immediately true.

Puzzle propagation

Cells with a single legal digit fall out instantly, cascading constraints — that's why real puzzles solve in milliseconds.

06

Complexity

Time

O(9^b)

Space

O(b)

b = blank count; pruning makes it practical.