Sudoku Solver

Explanation & Solution

Practice Problem

Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.

2. Each of the digits 1-9 must occur exactly once in each column.

3. Each of the digits 1-9 must occur exactly once in each of the 9 3×3 sub-boxes of the grid.

The '.' character indicates empty cells.

Examples

Example 1

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

Explanation: The input board has a unique solution shown above.

Constraints

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

Approach

Backtracking pattern

1. Initialize Tracking Sets

Create sets for each row, column, and 3×3 box to track which digits are already placed
Scan the board and populate the sets with initial values
Collect all empty cell positions into a list

2. Backtrack Through Empty Cells

Process empty cells one by one in order
For each empty cell, try digits 1 through 9

3. Validate Placement

Before placing a digit, check if it already exists in the same row, column, or 3×3 box using the tracking sets
The box index is computed as floor(row/3) * 3 + floor(col/3)

4. Place and Recurse

If the digit is valid, place it on the board and add it to the row, column, and box sets
Recurse to the next empty cell
If recursion returns true, the puzzle is solved

5. Backtrack on Failure

If no digit 1–9 works for the current cell, undo the placement and remove the digit from the tracking sets
Return false to trigger backtracking in the previous cell

🧠 Key Insight

Using sets for rows, columns, and boxes gives O(1) validity checks per digit attempt.
Collecting empty cells upfront avoids scanning the entire board at each recursive step.

Time

O(9^m) where m is the number of empty cells (worst case), but constraint propagation prunes most branches.

Space

O(m) for the recursion stack plus **O(81)** for the tracking sets.

Visualization

Input:

DFS Traversal9×9 grid

output—

Press play to start dfs traversal

CurrentQueuedVisitedSource

489 steps

Solution Code

Word Search

Permutations