Sudoku Solver LeetCode: Complete Backtracking Guide

Sudoku Solver (#37) sits at the top of the backtracking difficulty ladder on LeetCode. While N-Queens tests placement constraints and Word Search tests grid traversal, the sudoku solver leetcode problem combines both — you must satisfy three overlapping constraint types simultaneously across a 9x9 grid.

This problem appears at Google, Amazon, and other top companies as the definitive test of whether you can implement complex constraint-satisfaction from scratch. If you can solve Sudoku Solver cleanly under time pressure, you can handle any backtracking question an interviewer throws at you.

In this walkthrough, you will learn the backtracking approach step by step, build efficient O(1) constraint checking with sets, and understand the implementation details that separate a working solution from a clean one.

The problem gives you a partially filled 9x9 grid. Each cell contains either a digit from 1 to 9 or a dot representing an empty cell. Your task is to fill every empty cell so that each row, each column, and each of the nine 3x3 sub-boxes contains the digits 1 through 9 exactly once.

The problem guarantees exactly one valid solution. This is important because it means once your backtracking finds a solution, you can stop immediately — there is no need to continue searching for alternatives. The board is modified in place, so there is no return value.

Think of it as a constraint-satisfaction problem: every empty cell has a domain of possible values (1-9), and the constraints are that no digit repeats within its row, column, or 3x3 box. The backtracking approach systematically narrows these domains until every cell is filled.

The core algorithm is straightforward: find an empty cell, try placing digits 1 through 9, check whether the placement is valid, and recurse. If no digit works for a cell, backtrack by undoing the placement and returning false to the caller. When every cell is filled, return true.

The backtracking tree for sudoku is deep but narrow. Each empty cell branches into at most 9 choices, and constraint checking prunes most branches immediately. A typical 9x9 puzzle with 30 empty cells has a theoretical upper bound of 9^30 states, but the actual search space is drastically smaller because most digits violate at least one constraint.

The key insight is that your solve function must return a boolean. When a recursive call returns true, you propagate that true upward immediately without trying more digits. When it returns false, you erase the digit you placed and try the next one. This boolean propagation is what makes backtracking work correctly.

Here is the high-level structure: scan the board for the first empty cell. For each digit 1-9, check if placing it is valid. If valid, place it and recurse. If the recursive call returns true, return true. If not, reset the cell to empty and continue. If no digit works, return false.

The naive approach to checking whether a digit is valid scans the entire row, column, and box — that is 27 cells per check. With potentially thousands of checks during backtracking, this adds up. The efficient approach uses three arrays of sets to make each validity check O(1).

Create three data structures: rows[9], cols[9], and boxes[9], where each entry is a set of digits already present. The box index for cell (i, j) is calculated as Math.floor(i / 3) * 3 + Math.floor(j / 3), which maps each 3x3 sub-box to a unique index from 0 to 8.

Before starting the backtracking, scan the entire board once and populate these sets with all the given digits. This pre-population step takes O(81) time and means that during backtracking, checking whether digit d can go in cell (i, j) is a simple three-set membership test: d not in rows[i], d not in cols[j], d not in boxes[box_index].

When you place a digit during backtracking, add it to all three sets. When you remove a digit during backtracking, remove it from all three sets. This maintains consistency and keeps every check at O(1).

Start by initializing the constraint sets. Loop through every cell of the board. For each non-empty cell, parse the digit and add it to rows[i], cols[j], and boxes[box_index]. This gives you the starting state of all constraints.

The solve function scans for the first empty cell by iterating row by row. When it finds one, it tries digits 1 through 9. For each digit, it checks the three sets. If the digit is valid, it places it on the board, adds it to the sets, and calls solve recursively. If solve returns true, it returns true immediately. Otherwise, it removes the digit from the board and the sets, then tries the next digit.

If the scan completes without finding an empty cell, the board is solved — return true. If no digit works for the current empty cell, return false to trigger backtracking in the caller.

One common optimization is to find the empty cell with the fewest valid candidates (the MRV heuristic). For interview purposes, the simple left-to-right scan is usually sufficient and much easier to implement correctly under time pressure.

The problem guarantees a unique solution, so you never need to worry about handling multiple solutions or no-solution boards in an interview. However, understanding the edge cases shows depth of thought. An already-solved board means your solver finds no empty cell on the first scan and returns true immediately — your code should handle this naturally.

A nearly empty board (minimal clues) is the hardest case for runtime because the search space is largest. The minimum number of clues for a unique Sudoku solution is 17. On such boards, your solver will explore more branches, but the constraint sets still prune aggressively.

Time complexity is O(9^m) where m is the number of empty cells, but this is a loose upper bound. In practice, constraint checking prunes so heavily that even worst-case boards solve in milliseconds. Space complexity is O(81) for the board plus O(27) for the constraint sets — effectively O(1) since the grid size is fixed.

Sudoku Solver is the capstone backtracking problem because it synthesizes every technique you need. The constraint-satisfaction pattern — maintaining valid-state sets and checking them before each placement — appears in N-Queens, Combination Sum, and dozens of other problems. Mastering it here means you have the template for all of them.

The boolean return pattern is equally important. Many backtracking problems need you to stop as soon as you find one valid configuration. The discipline of returning true upward through the call stack, and false when a branch fails, is the core mechanism that makes backtracking efficient.

If you can implement Sudoku Solver cleanly in an interview — with pre-populated constraint sets, clean backtracking, and correct boolean propagation — you have demonstrated mastery of the hardest common backtracking pattern. Practice this problem with YeetCode flashcards to build the recall speed you need when time is limited.