Skip to main content
Talentd

Sudoku Solver - Solution & Explanation

HardArrayHash TableBacktrackingMatrix19 min readAsked at: Amazon, Microsoft, Apple +14
Practice this problem

Problem Statement

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 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

 

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 is shown above and the only valid solution is shown below:

 

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 Overview

Problem Overview: Sudoku Solver asks you to fill a partially completed 9×9 board so that every row, column, and 3×3 subgrid contains digits 1–9 exactly once. Empty cells are marked with '.'. The challenge is finding a valid assignment that satisfies all constraints without modifying the fixed cells.

The board naturally forms a matrix, and each placement must respect three constraints: unique numbers per row, column, and 3×3 box. Because every empty cell can potentially take multiple values, the search space grows quickly. The core strategy is to try candidates, verify constraints, and backtrack when a choice leads to an invalid state.

Approach 1: Backtracking (Exponential Time, O(9^(n)) worst case, O(81) space)

This approach treats Sudoku as a constraint satisfaction problem solved using backtracking. Iterate through the board to find an empty cell. Try digits 1–9 one by one and check whether placing the digit violates row, column, or 3×3 box rules. If the placement is valid, recursively attempt to solve the remaining cells. If a later step fails, revert the cell and try the next digit.

Validation is typically done by scanning the row, column, and subgrid each time you place a number. Although the theoretical complexity can reach O(9^(81)), pruning invalid placements dramatically reduces the search space in practice. The recursion depth is bounded by the number of empty cells, so the extra space is mainly the recursion stack, around O(81).

Approach 2: Constraint Propagation with Backtracking (Exponential Time, O(9^(n)) worst case, O(81) space)

This optimization improves the basic backtracking strategy by tracking constraints explicitly using sets or bitmasks. Maintain three structures that record which digits are already used in each row, column, and box. These can be implemented with arrays, hash tables, or bitmasks. When you place a digit, update the corresponding row, column, and box constraints instantly.

Instead of scanning the entire row or column every time, you perform constant-time checks against these constraint structures. This dramatically reduces repeated work and prunes invalid candidates earlier. Some implementations also choose the next cell with the fewest valid candidates (a common constraint propagation heuristic), which further shrinks the branching factor.

The worst‑case complexity remains exponential because Sudoku solving is fundamentally a search problem. However, constraint propagation makes the solver significantly faster in real cases by avoiding unnecessary recursion and repeated validation scans.

Recommended for interviews: Interviewers expect a clean backtracking solution that validates row, column, and box constraints correctly. Showing the baseline recursive search demonstrates understanding of the problem structure. Adding constraint tracking with sets or bitmasks shows stronger problem‑solving skills and awareness of optimization techniques commonly used in constraint satisfaction problems.

Approach 1: Backtracking Approach

The backtracking approach is a classic method to solve problems like Sudoku that require exploring all configurations to find a valid solution. This involves recursively trying all numbers from 1 to 9 in each cell and verifying if they meet Sudoku rules. If a number fits, move to the next cell. If stuck, backtrack to the previous cell and try a different number. This method ensures all constraints are respected at each step.

This solution implements a backtracking algorithm in C. The isValid function checks if placing a digit in a particular cell violates Sudoku rules. The solveSudokuHelper function tries placing digits and uses recursion to backtrack if necessary until the board is completely filled.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(9^(N*N)), where N = 9 (the size of the board), as each empty cell has 9 possibilities.
Space Complexity: O(N*N) for the recursion stack.

Try this approach in the editor →

Approach 2: Constraint Propagation with Backtracking

This approach enhances the basic backtracking method by introducing constraint propagation. Before choosing a number for a cell, it checks constraints upfront, reducing unnecessary exploration by propagating constraints once a number is filled. This technique decreases the number of options that need to be tried, thereby optimizing the backtracking process.

This Python solution incorporates constraint propagation into the backtracking method. It attempts to minimize choices by evaluating constraints before any number is placed, helping to reduce the branching factor in the search tree. If a valid scenario is found using propagation, it progresses further in solving the Sudoku.

Code

Python

Python

Complexity

Time Complexity: Expected better than O(9^(N*N)), depending on effectiveness of constraint propagation reducing possible combinations.
Space Complexity: O(N*N), influenced by recursion.

Try this approach in the editor →

Approach 3: Backtracking

We use arrays row, col, and box to record whether each number has appeared in each row, each column, and each 3x3 sub-box, respectively. If the number i has appeared in row r, column c, or the b-th 3x3 sub-box, then row[r][i], col[c][i], and box[b][i] are all set to true.

We iterate over every empty cell in the board and enumerate the possible numbers v that can be filled in. If v has not appeared in the current row, column, or 3x3 sub-box, we can try filling in v and continue searching for the next empty cell. If we reach the end and all cells are filled, it means we have found a valid solution.

Code

PythonJavaC++GoC#PHP

Python

Java

C++

Go

C#

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking Approach

Time Complexity: O(9^(N*N)), where N = 9 (the size of the board), as each empty cell has 9 possibilities.
Space Complexity: O(N*N) for the recursion stack.

Constraint Propagation with Backtracking

Time Complexity: Expected better than O(9^(N*N)), depending on effectiveness of constraint propagation reducing possible combinations.
Space Complexity: O(N*N), influenced by recursion.

Backtracking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Basic BacktrackingO(9^(n)) worst caseO(81)Best for understanding the core recursion and constraint checks during interviews
Constraint Propagation + BacktrackingO(9^(n)) worst case but faster in practiceO(81)Preferred for optimized implementations using row/column/box tracking or bitmasks

Video Solution

Implement A Sudoku Solver - Sudoku Solving Backtracking Algorithm ("Sudoku Solver" on LeetCode) • Back To Back SWE • 130,354 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sudoku Solver easy or hard?
Sudoku Solver is classified as a Hard problem because it requires recursive backtracking and careful constraint validation across rows, columns, and subgrids. Efficient implementations also track constraints to avoid repeated scans of the board.
Sudoku Solver Python/Java solution
Sudoku Solver is typically implemented using recursion and backtracking in Python, Java, C++, JavaScript, or C#. The algorithm iterates through empty cells, tries digits 1–9, validates constraints, and backtracks when a placement breaks Sudoku rules.
How to solve Sudoku Solver in O(n)?
Sudoku cannot generally be solved in O(n) time because it is a constraint satisfaction problem requiring search. Practical solutions rely on backtracking combined with constraint propagation. These techniques reduce the search space but the theoretical worst‑case complexity remains exponential.
What is the best approach for Sudoku Solver?
Backtracking with constraint tracking is the most effective approach. The algorithm fills empty cells recursively while ensuring that each number is valid for its row, column, and 3x3 box. Using sets or bitmasks to track used numbers reduces repeated checks and speeds up the search significantly.
Is Sudoku Solver asked at Google/Amazon/Meta?
Sudoku-style backtracking problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact LeetCode problem may not always be used, the same recursion, constraint validation, and pruning techniques are commonly tested.
What data structure is used in Sudoku Solver?
Common implementations use arrays or hash sets to track digits already used in each row, column, and 3x3 subgrid. Some optimized solutions replace sets with bitmasks for constant-time constraint checks and lower memory overhead.
What is the time complexity of Sudoku Solver?
The worst‑case time complexity is exponential, commonly described as O(9^(n)) where n is the number of empty cells. Each empty cell may try up to nine digits, and invalid states are pruned through constraint checks. In practice, strong pruning makes most puzzles solve quickly.

Ready to solve this problem?

Practice Sudoku Solver with our built-in code editor and test cases.

Practice on FleetCode
Previous

Unique Paths III

Next

Valid Sudoku