LeetCode 37 Sudoku Solver: How Backtracking Actually Works
The LeetCode 37 Sudoku Solver problem is solved using a systematic backtracking algorithm. This approach tries possible numbers in empty cells and undoes placements that lead to contradictions. It's a classic demonstration of recursive depth-first search, perfect for both coding interviews and understanding automated solving. While our verified solve path for this specific puzzle uses only Naked Singles, the algorithmic approach must explore all possibilities. This article will show how a [Sudoku Solver Algorithm](/blog/sudoku-solver-algorithm) works in principle and apply it to a concrete example.
Step 1: Understanding the Backtracking Core
Backtracking is a brute-force algorithm adapted with intelligence. It treats the puzzle as a sequence of empty cells to fill. For each empty cell, it tries every digit from 1 to 9 that does not immediately violate Sudoku rules for the row, column, and 3x3 box. The algorithm places a valid digit and then recursively attempts to solve the rest of the puzzle from that new state. If the recursive call eventually solves the entire puzzle, the algorithm returns the solution. If placing that digit leads to a dead-end (a cell with no valid candidates), the algorithm backtracks: it removes the digit (resets the cell to empty) and tries the next possible number for that cell. This process continues until all cells are filled correctly.
Step 2: Defining the Search Order and Validation
A simple yet effective search order is left-to-right, top-to-bottom. This means the algorithm starts at the first empty cell in row 1, column 1 (r1c1), and proceeds linearly. Before placing any number, it must validate the move. The validation function checks the current row, column, and 3x3 box for the presence of the candidate digit. For our puzzle's first empty cell, r1c1, the row already contains 8,7,5,1,3. Column 1 contains 2,9,7. Box 1 contains 8,7,1. Therefore, digits 1,2,3,5,7,8,9 are invalid, leaving only 4 and 6 as possible candidates for a naive algorithm to try. A reliable Python Sudoku Solver implements this validation efficiently.
Step 3: Walking Through the First Backtracking Branch
Following the left-to-right order, the algorithm tries the first candidate for r1c1. From Step 2, the candidates are 4 and 6. It will try 4 first. Placing a 4 in r1c1 is valid based on the initial givens. The algorithm then moves to the next empty cell, r1c3, and repeats the process. It will continue making placements, but this path will eventually fail. The verified logical solve path shows that the correct digit for r1c1 is 6. This discrepancy is key: the backtracking algorithm must discover this through trial and error. It will place 4, proceed many steps, hit a contradiction where a cell has zero valid candidates, and then retreat back to r1c1 to try 6 instead. This backtracking search is different from the logical single-solution path a human might see.
Step 4: Contrasting with the Logical Solve Path
Our provided puzzle has a unique property: from the start, every empty cell can be filled using only Naked Singles if you follow the optimal logical order. This order is not left-to-right. The first logical move is placing an 8 in r2c8. Why? Row 2 already has 7,1,6,2,3. Column 8 has 3,4,5,1,9. Box 3 has 1,3,4,6. The only missing digit for that specific cell is 8. A backtracking algorithm doesn't 'look ahead' for these singles; it brute-forces its way there. However, a more advanced Sudoku Solver on GitHub might integrate human-like logic to prune the search tree dramatically. For LeetCode 37, the pure backtracking approach is sufficient because the 9x9 grid is small.
- The logical first move r2c8=8 is a Naked Single: the only digit missing from the intersection of row 2, column 8, and box 3.
Step 5: How Backtracking Reaches the Solution
Let's trace how backtracking converges to the correct solution. After backtracking from the failed branch starting with r1c1=4, it tries r1c1=6. This is the correct foundation. The algorithm then proceeds, recursively filling cells. It will correctly place r1c3=9 and r1c4=4, matching the logical path. Each placement is validated against the current board state. The recursion continues, and if it ever places a digit that later makes an empty cell have zero valid candidates, it will backtrack to the most recent decision point. This process is guaranteed to find the single solution because it systematically explores all possible configurations that obey the initial constraints. The final filled grid is our provided solution.
Step 6: Optimizations and Interview Tips
While the basic backtracking algorithm works, it can be optimized. A key optimization is to always pick the cell with the fewest possible candidates next, rather than using a fixed order. This 'most constrained variable' heuristic drastically reduces the number of recursive calls. For coding interviews, you are often expected to implement the basic validator and recursive solver. Be prepared to discuss time complexity, which is O(9^(n)) for n empty cells in the worst case, but with validation, it's much faster in practice. Understanding this algorithm is the first step towards Making Your Own Solver with more advanced techniques. Practice by following a Sudoku Solver Step by Step guide to internalize the recursion.
Key Facts
- ▪LeetCode 37 Sudoku Solver is a classic coding problem that requires implementing a backtracking algorithm to fill a 9x9 board.
- ▪Backtracking is a depth-first search algorithm that tries numbers in empty cells and reverts choices that lead to invalid states.
- ▪The algorithm validates each placement by checking the current row, column, and 3x3 box for duplicate digits.
- ▪A common implementation searches empty cells in a left-to-right, top-to-bottom order.
- ▪The worst-case time complexity is exponential, but validation and constraint propagation make it practical for standard Sudoku.
- ▪The puzzle used in this article has 34 given digits and 47 empty cells, with a single unique solution.
- ▪The verified logical solve path for this puzzle fills all cells using only Naked Singles, but the backtracking algorithm does not rely on this pattern.
- ▪A key optimization is to always fill the empty cell with the fewest legal candidates first, which speeds up the search.
- ▪The algorithm's recursion stack unwinds (backtracks) when a cell is reached that has zero valid digits to place.
- ▪Successfully solving LeetCode 37 demonstrates mastery of recursion, constraint validation, and search space navigation.
Frequently Asked Questions
What is the LeetCode 37 Sudoku Solver problem?
It's a coding challenge where you write a function to solve a given 9x9 Sudoku puzzle by modifying the board in-place. The solution must use a backtracking algorithm.
How does backtracking work for Sudoku?
It picks an empty cell, tries a valid digit, and recursively tries to solve the rest. If the recursion fails, it removes the digit (backtracks) and tries the next candidate.
Is backtracking the fastest way to solve Sudoku?
No, for humans, logical techniques are faster. For computers, backtracking combined with constraint propagation and smart cell ordering is very efficient.
What's the difference between the algorithm and the logical solve path?
The algorithm blindly tries possibilities. The logical path uses pattern recognition (like Naked Singles) to deduce the only possible digit, avoiding guesswork.
What is a Naked Single?
A Naked Single occurs when an empty cell has only one possible digit left that doesn't conflict with given numbers in its row, column, and box.
Why does the backtracking solution start at r1c1 with 4?
In a left-to-right search, r1c1 is the first empty cell. Digits 4 and 6 are valid initially. The algorithm tries 4 first, leading to a later backtrack.