LeetCode 37 - Sudoku Solver

LeetCode Problem 37

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Backtracking, Matrix

Solution

Problem Understanding

The problem asks us to build a complete Sudoku solver. We are given a partially filled 9 x 9 grid where each cell contains either a digit from '1' to '9' or the character '.', which represents an empty space. Our goal is to fill every empty cell so that the final board satisfies all Sudoku rules.

A valid Sudoku board must follow three constraints simultaneously:

1. Every row must contain each digit from 1 through 9 exactly once.
2. Every column must contain each digit from 1 through 9 exactly once.
3. Every 3 x 3 sub-grid must contain each digit from 1 through 9 exactly once.

The important detail is that we are not generating any arbitrary valid Sudoku board. We must complete the specific board given in the input while preserving all existing numbers.

The function does not return a new board. Instead, it modifies the input board directly in-place. This means our algorithm must carefully update cells and undo changes when necessary.

The constraints tell us several important things:

• The board size is fixed at 9 x 9
• Each cell contains either a digit or '.'
• The puzzle always has exactly one valid solution

Although the grid size is small, the search space is enormous. Every empty cell may potentially hold multiple values, which creates an exponential number of possibilities. A naive brute-force search would quickly become infeasible without pruning invalid states early.

Several edge cases can cause issues in naive implementations:

• Boards with many empty cells create a very large search tree
• Incorrect placement validation may allow invalid intermediate states
• Forgetting to backtrack properly can corrupt the board state
• Mishandling sub-box indexing often causes subtle bugs
• Some cells may have only one valid option, while others may have many

The guarantee that the puzzle has exactly one solution simplifies the implementation because we can stop searching as soon as we find a valid completed board.

Approaches

Brute Force Approach

The brute-force strategy tries every possible digit in every empty cell without using much information about Sudoku constraints ahead of time.

For each empty cell, we attempt all digits from 1 through 9. After placing a digit, we recursively continue solving the remaining cells. If we eventually reach a contradiction, we backtrack and try another digit.

This approach is correct because it systematically explores all possible board configurations. Since the valid solution exists somewhere in the search tree, exhaustive exploration guarantees that we eventually find it.

However, this method is extremely slow because the number of possible states grows exponentially. If there are k empty cells, the worst-case search space is approximately 9^k. Even with only 50 empty cells, this becomes astronomically large.

The main issue is that the brute-force approach wastes time exploring many obviously invalid states.

Optimal Approach, Backtracking with Constraint Tracking

The key insight is that Sudoku constraints allow us to reject invalid states immediately instead of exploring them deeply.

Rather than repeatedly scanning rows, columns, and sub-boxes every time we test a number, we maintain fast lookup structures that track which digits already exist in each row, column, and box.

For every placement:

• Check whether the digit already exists in the current row
• Check whether it exists in the current column
• Check whether it exists in the corresponding 3 x 3 box

If any constraint fails, we skip that digit immediately.

This transforms the solution into a classic backtracking problem with aggressive pruning. The algorithm only explores states that remain potentially valid.

Because invalid branches terminate early, the practical runtime becomes dramatically faster than naive brute force.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(9^k × 81)	O(k)	Repeatedly scans rows, columns, and boxes for validation
Optimal	O(9^k)	O(k + 81)	Uses hash sets for constant-time constraint checking

Here, k represents the number of empty cells.

Algorithm Walkthrough

Step 1: Initialize Tracking Structures

We create three collections:

• rows
• cols
• boxes

Each stores which digits are already used.

For example:

• rows[0] contains all digits already placed in row 0
• cols[3] contains all digits already placed in column 3
• boxes[4] contains all digits already placed in the center 3 x 3 box

We use sets because membership checks are extremely fast, approximately O(1).

Step 2: Record Existing Digits

We scan the board once.

Whenever we encounter a digit:

• Add it to the corresponding row set
• Add it to the corresponding column set
• Add it to the corresponding box set

This preprocessing step allows future validity checks to happen instantly.

Step 3: Collect Empty Cells

Instead of repeatedly scanning the board for empty cells during recursion, we store all empty positions in a list upfront.

Each empty cell is represented as (row, col).

This reduces unnecessary repeated work.

Step 4: Start Recursive Backtracking

We recursively process one empty cell at a time.

At recursion level index:

• Retrieve the corresponding empty cell
• Try placing digits '1' through '9'

For each candidate digit:

• Check whether it already exists in the row
• Check whether it already exists in the column
• Check whether it already exists in the box

If the digit is valid:

• Place it on the board
• Update tracking sets
• Continue recursively

Step 5: Handle Dead Ends

If recursive solving fails, the current placement was incorrect.

We must undo all changes:

• Remove the digit from the board
• Remove it from row tracking
• Remove it from column tracking
• Remove it from box tracking

This restoration process is the essence of backtracking.

Step 6: Detect Completion

If we successfully process all empty cells, the puzzle is solved.

At that point, we return True and stop further recursion.

Why it works

The algorithm maintains an important invariant throughout execution:

Every partially filled board explored by the recursion always satisfies all Sudoku constraints.

Whenever we place a digit, we first verify that it does not violate any rule. Therefore, recursive calls only operate on valid intermediate states.

Backtracking guarantees completeness because every possible valid digit assignment is eventually explored. Since the problem guarantees a unique solution, the first complete valid board we find must be the correct answer.

Python Solution

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

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

        empty_cells = []

        # Initialize tracking structures
        for row in range(9):
            for col in range(9):
                value = board[row][col]

                if value == ".":
                    empty_cells.append((row, col))
                else:
                    rows[row].add(value)
                    cols[col].add(value)

                    box_index = (row // 3) * 3 + (col // 3)
                    boxes[box_index].add(value)

        def backtrack(index: int) -> bool:
            # All cells filled successfully
            if index == len(empty_cells):
                return True

            row, col = empty_cells[index]
            box_index = (row // 3) * 3 + (col // 3)

            for digit in "123456789":

                # Skip invalid placements
                if (
                    digit in rows[row]
                    or digit in cols[col]
                    or digit in boxes[box_index]
                ):
                    continue

                # Place digit
                board[row][col] = digit

                rows[row].add(digit)
                cols[col].add(digit)
                boxes[box_index].add(digit)

                # Continue solving
                if backtrack(index + 1):
                    return True

                # Undo placement
                board[row][col] = "."

                rows[row].remove(digit)
                cols[col].remove(digit)
                boxes[box_index].remove(digit)

            return False

        backtrack(0)

The implementation begins by creating three arrays of sets to track used digits in rows, columns, and sub-boxes. This preprocessing phase converts expensive repeated validation into constant-time membership checks.

The board is scanned once to populate these structures. During this scan, all empty cells are also collected into empty_cells, which avoids repeatedly searching for empty positions during recursion.

The recursive backtrack function processes one empty cell at a time. The index parameter determines which empty cell is currently being solved.

For every candidate digit:

• The algorithm checks whether the digit already exists in the corresponding row, column, or box.
• If valid, the digit is placed and all tracking structures are updated.
• The recursion continues to the next empty cell.

If deeper recursion fails, the algorithm removes the digit and restores all state. This ensures future recursive branches start from a clean board configuration.

The recursion terminates successfully once every empty cell has been filled.

Go Solution

func solveSudoku(board [][]byte) {
	rows := make([]map[byte]bool, 9)
	cols := make([]map[byte]bool, 9)
	boxes := make([]map[byte]bool, 9)

	for i := 0; i < 9; i++ {
		rows[i] = make(map[byte]bool)
		cols[i] = make(map[byte]bool)
		boxes[i] = make(map[byte]bool)
	}

	type Cell struct {
		row int
		col int
	}

	var emptyCells []Cell

	// Initialize tracking structures
	for row := 0; row < 9; row++ {
		for col := 0; col < 9; col++ {

			value := board[row][col]

			if value == '.' {
				emptyCells = append(emptyCells, Cell{row, col})
			} else {
				rows[row][value] = true
				cols[col][value] = true

				boxIndex := (row/3)*3 + (col / 3)
				boxes[boxIndex][value] = true
			}
		}
	}

	var backtrack func(int) bool

	backtrack = func(index int) bool {

		// Puzzle solved
		if index == len(emptyCells) {
			return true
		}

		row := emptyCells[index].row
		col := emptyCells[index].col

		boxIndex := (row/3)*3 + (col / 3)

		for digit := byte('1'); digit <= byte('9'); digit++ {

			if rows[row][digit] ||
				cols[col][digit] ||
				boxes[boxIndex][digit] {
				continue
			}

			// Place digit
			board[row][col] = digit

			rows[row][digit] = true
			cols[col][digit] = true
			boxes[boxIndex][digit] = true

			if backtrack(index + 1) {
				return true
			}

			// Undo placement
			board[row][col] = '.'

			delete(rows[row], digit)
			delete(cols[col], digit)
			delete(boxes[boxIndex], digit)
		}

		return false
	}

	backtrack(0)
}

The Go implementation follows the same algorithmic structure as the Python version, but there are several language-specific differences.

Go does not have a built-in set type, so maps of type map[byte]bool are used to simulate sets. Presence in the set is represented by a boolean value.

The board uses [][]byte rather than strings because Go commonly represents characters as bytes for efficiency.

Go also requires explicit struct definitions for storing coordinates, so a small Cell struct is introduced for empty cell positions.

Backtracking state restoration uses the delete function to remove digits from the maps.

Worked Examples

Example 1

Initial 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

The algorithm first initializes tracking sets.

For example:

Structure	Contents
rows[0]	{5, 3, 7}
cols[0]	{5, 6, 8, 4, 7}
boxes[0]	{5, 3, 6, 9, 8}

The first empty cell is (0, 2).

Possible digits:

Digit	Valid?	Reason
1	Yes	Not in row, column, or box
2	Yes	Not in row, column, or box
3	No	Already in row
4	Yes	Valid
5	No	Already in row
6	No	Already in box
7	No	Already in row
8	No	Already in column
9	No	Already in box

The algorithm tries '1' first.

Updated board:

5 3 1 . 7 . . . .
6 . . 1 9 5 . . .
. 9 8 . . . . 6 .
...

The recursion continues to the next empty cell.

Suppose a later placement creates a contradiction where no valid digit can be placed in a future cell. The recursion then backtracks:

• Remove the previously placed digit
• Restore tracking sets
• Try the next candidate

Eventually, the algorithm converges to:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(9^k)	Each empty cell may try up to 9 digits
Space	O(k + 81)	Recursion stack plus tracking structures

Here, k is the number of empty cells.

The worst-case runtime is exponential because Sudoku solving fundamentally requires exploring combinations of placements. However, pruning invalid states early dramatically reduces practical runtime.

The recursion depth is at most the number of empty cells. The tracking structures require fixed space because the board size is always 9 x 9.

Test Cases

from typing import List

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)]

        empty_cells = []

        for row in range(9):
            for col in range(9):
                value = board[row][col]

                if value == ".":
                    empty_cells.append((row, col))
                else:
                    rows[row].add(value)
                    cols[col].add(value)

                    box_index = (row // 3) * 3 + (col // 3)
                    boxes[box_index].add(value)

        def backtrack(index: int) -> bool:
            if index == len(empty_cells):
                return True

            row, col = empty_cells[index]
            box_index = (row // 3) * 3 + (col // 3)

            for digit in "123456789":

                if (
                    digit in rows[row]
                    or digit in cols[col]
                    or digit in boxes[box_index]
                ):
                    continue

                board[row][col] = digit

                rows[row].add(digit)
                cols[col].add(digit)
                boxes[box_index].add(digit)

                if backtrack(index + 1):
                    return True

                board[row][col] = "."

                rows[row].remove(digit)
                cols[col].remove(digit)
                boxes[box_index].remove(digit)

            return False

        backtrack(0)

# Standard example puzzle
board1 = [
    ["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"]
]

expected1 = [
    ["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(board1)
assert board1 == expected1  # verifies standard puzzle solving

# Nearly completed board
board2 = [
    ["5","3","4","6","7","8","9","1","."],
    ["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(board2)

assert board2[0][8] == "2"  # verifies single missing cell handling

# Already solved board
board3 = [
    ["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"]
]

original = [row[:] for row in board3]

Solution().solveSudoku(board3)

assert board3 == original  # verifies already solved input remains unchanged

Test	Why
Standard example puzzle	Validates full backtracking behavior
Nearly completed board	Tests minimal recursion depth
Already solved board	Ensures algorithm handles zero empty cells correctly

Edge Cases

One important edge case is a board that is already completely solved. Some implementations assume there will always be empty cells and may incorrectly enter recursion or modify valid values. This implementation handles the case naturally because the empty_cells list becomes empty, causing the recursive function to immediately return True.

Another critical edge case involves cells with only one valid candidate. Incorrect validation logic can accidentally reject the only valid digit or allow invalid placements. The tracking sets ensure every candidate check is consistent and constant time, preventing subtle rule violations.

A more difficult edge case is a board with many empty cells that requires extensive backtracking. Poor implementations may forget to restore state properly during recursion, leaving stale values inside tracking structures. This implementation explicitly removes digits from the board, row sets, column sets, and box sets during backtracking, guaranteeing each recursive branch starts from a clean state.