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.

How to spot this pattern

Constraint backtracking on a grid: find an empty cell, try each legal digit, recurse, and undo on failure. The box index arithmetic — 3 * (r // 3) for the block's origin — is the piece worth memorising, and returning a boolean lets the recursion stop the instant one solution is complete.

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

▶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

Common pitfalls

Returning `False` after the digit loop but outside it

✗ Wrong

for ch in "123456789":
    ...
continue   # try the next cell

✓ Right

for ch in "123456789":
    ...
return False

If no digit fits this cell, the current partial board is unsolvable and the caller must backtrack. Moving on to another cell explores a dead branch forever instead of retreating.

Computing the box origin without flooring

✗ Wrong

br, bc = r // 3, c // 3

✓ Right

br, bc = 3 * (r // 3), 3 * (c // 3)

r // 3 gives the box number (0–2), not the row where that box begins. Without multiplying back by 3 the scan checks cells from the top-left corner of the grid rather than the relevant block.

Not clearing the cell when a branch fails

✗ Wrong

board[r][c] = ch
if solve(): return True

✓ Right

board[r][c] = ch
if solve(): return True
board[r][c] = "."

A failed digit left in place poisons every later attempt — the cell reads as filled, so it's skipped, and the constraint checks see a value that was rejected. Undo is what makes it backtracking.

06

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.

07

Complexity

Time

O(9^b)

Space

O(b)

b = blank count; pruning makes it practical.

Sudoku Solver

Intuition

Approach

Scan for the next blank

Try digits with a validity check

Recurse, undo on failure

Solution & live demo

Common pitfalls

Returning False after the digit loop but outside it

Computing the box origin without flooring

Not clearing the cell when a branch fails

Edge cases

Complexity

Returning `False` after the digit loop but outside it