LeetCode 37: Sudoku Solver

Problem Restatement

We are given a partially filled 9 x 9 Sudoku board.

Empty cells are represented by:

"."

We must fill the empty cells so that the final board satisfies Sudoku rules:

Rule	Meaning
Row rule	Each digit `1` to `9` appears exactly once in every row
Column rule	Each digit `1` to `9` appears exactly once in every column
Box rule	Each digit `1` to `9` appears exactly once in every `3 x 3` box

The problem guarantees that the input has exactly one solution.

We must modify the board in place.

Input and Output

Item	Meaning
Input	A partially filled `9 x 9` Sudoku board
Output	Nothing returned
Required mutation	Fill the board in place
Empty cell	`"."`
Solution guarantee	Exactly one valid solution exists

Function shape:

def solveSudoku(board: list[list[str]]) -> None:
    ...

Examples

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"],
]

One valid solved board is:

[
    ["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"],
]

First Thought: Try Every Possibility

An empty cell can contain digits:

1 to 9

So one direct idea is:

Find an empty cell.
Try every digit.
Continue solving the rest of the board.

If a choice eventually leads to a contradiction, undo it and try another digit.

This idea is called backtracking.

Why Backtracking Fits Sudoku

Sudoku is a constraint problem.

Each decision restricts future decisions.

For example:

board[r][c] = "5"

immediately affects:

row r
column c
the 3 x 3 box containing (r, c)

A wrong guess may not fail immediately. It may fail many steps later.

So we need the ability to:

Make a choice.
Explore deeper.
Undo the choice if it fails.

That is exactly what recursive backtracking does.

Key Insight

At every step, we only need to know:

Which digits already exist in the current row.
Which digits already exist in the current column.
Which digits already exist in the current box.

Instead of scanning the board repeatedly, maintain three collections of sets:

rows[0..8]
cols[0..8]
boxes[0..8]

Each set stores digits already used there.

This lets validity checks become constant time.

The box index formula is:

box = (r // 3) * 3 + (c // 3)

Algorithm

First, initialize the sets.

For every filled cell:

Add its digit to the corresponding row set.
Add its digit to the corresponding column set.
Add its digit to the corresponding box set.

Then define a recursive function:

backtrack()

Inside backtrack:

Scan the board to find the next empty cell.
Try digits "1" through "9".
For each digit:
- Check whether it already exists in the row, column, or box.
- If valid:
  - Place the digit.
  - Update the sets.
  - Recurse.
If recursion succeeds, return True.
Otherwise:
- Undo the placement.
- Remove the digit from the sets.
If no digit works, return False.

If no empty cells remain, the board is solved.

Correctness

The algorithm only places digits that satisfy all Sudoku constraints for the current partial board.

Before placing a digit into cell (r, c), it checks that the digit does not already appear in:

row r
column c
the corresponding 3 x 3 box

Therefore, every intermediate board produced by the algorithm remains valid.

The recursive search explores all valid digit choices for each empty cell. If a choice later leads to a contradiction, the algorithm removes that digit and restores the previous state. This guarantees that failed partial solutions do not affect future exploration.

Because the search eventually tries every valid possibility, if a solution exists, the algorithm will eventually reach a fully filled valid board. When no empty cells remain, every row, column, and box satisfies Sudoku rules, so the board is solved correctly.

The problem guarantees exactly one solution, so the first complete valid board found is the correct answer.

Complexity

Metric	Value	Why
Time	Exponential in the number of empty cells	Backtracking may explore many possibilities
Space	`O(81)`	Recursion depth and constraint sets are bounded by board size

In practice, constraint pruning makes the search much faster than naive enumeration.

Implementation

class Solution:
    def solveSudoku(self, board: list[list[str]]) -> None:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        for r in range(9):
            for c in range(9):
                value = board[r][c]

                if value == ".":
                    continue

                box = (r // 3) * 3 + (c // 3)

                rows[r].add(value)
                cols[c].add(value)
                boxes[box].add(value)

        def backtrack() -> bool:
            for r in range(9):
                for c in range(9):
                    if board[r][c] != ".":
                        continue

                    box = (r // 3) * 3 + (c // 3)

                    for digit in "123456789":
                        if digit in rows[r]:
                            continue

                        if digit in cols[c]:
                            continue

                        if digit in boxes[box]:
                            continue

                        board[r][c] = digit

                        rows[r].add(digit)
                        cols[c].add(digit)
                        boxes[box].add(digit)

                        if backtrack():
                            return True

                        board[r][c] = "."

                        rows[r].remove(digit)
                        cols[c].remove(digit)
                        boxes[box].remove(digit)

                    return False

            return True

        backtrack()

Code Explanation

We begin by creating constraint sets.

rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]

Each set stores digits already used there.

Then we scan the initial board.

for r in range(9):
    for c in range(9):

For every filled cell, compute its box index.

box = (r // 3) * 3 + (c // 3)

Then record the digit.

rows[r].add(value)
cols[c].add(value)
boxes[box].add(value)

The recursive function searches for an empty cell.

if board[r][c] != ".":
    continue

For an empty cell, try every digit.

for digit in "123456789":

Skip invalid digits immediately.

if digit in rows[r]:
    continue

The same logic applies to columns and boxes.

When a digit is valid, place it:

board[r][c] = digit

Then update the constraint sets.

rows[r].add(digit)
cols[c].add(digit)
boxes[box].add(digit)

Now recursively solve the remaining board.

if backtrack():
    return True

If recursion fails, undo everything.

board[r][c] = "."

rows[r].remove(digit)
cols[c].remove(digit)
boxes[box].remove(digit)

This restoration step is what makes backtracking work correctly.

If no digit works, return False.

When the scan finds no empty cells, the board is complete.

return True

Testing

def run_tests():
    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"],
    ]

    expected = [
        ["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"],
    ]

    Solution().solveSudoku(board)

    assert board == expected

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Standard Sudoku puzzle	Confirms recursive solving works
Mixed empty and filled cells	Confirms constraint tracking
Deep recursion	Confirms backtracking restoration logic
Unique solution	Confirms the solver reaches the expected final board