Sudoku Solver solution and explanation
Google
9 more videos on this problem
Implement A Sudoku Solver - Sudoku Solving Backtracking Algorithm ("Sudoku Solver" on LeetCode)Back To Back SWE · 9:53 · 130K views
LeetCode 37. Sudoku SolverHappy Coding · 16:43 · 18K views
[Java] Leetcode 37. Sudoku Solver [Backtracking #8]Eric Programming · 17:44 · 13K views
Sudoku Solver | Simple Explanation | Leetcode 37 | codestorywithMIKcodestorywithMIK · 26:37 · 12K views
Sudoku Solver - LeetCode 37 - JavaScriptAlgoJS · 9:27 · 4K views
Sudoku Solver | Leetcode 37 | Live coding session 🔥🔥🔥Coding Decoded · 13:34 · 3K views
Sudoku Solver Python Solution - LeetCode #37Professor Oakes · 9:19 · 2K views
LeetCode in C# | 37. Sudoku SolverJosh Ackland · 12:01 · 2K views
leetCode #37 Sudoku Solver(BackTracking) | JSer - algorithm and JavaScriptJSer · 19:59 · 1K views
37. Sudoku Solver | Leetcode Daily - PythonLeetcode Daily · 5:20 · 1K views
The problem
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-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 == 9board[i].length == 9board[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.
class Solution:
def solveSudoku(self, board):
def is_valid(board, r, c, num):
for i in range(9):
if board[i][c] == num or board[r][i] == num:
return False
if board[3*(r//3) + i//3][3*(c//3) + i%3] == num:
return False
return True
def solve(board):
for r in range(9):
for c in range(9):
if board[r][c] == '.':
for num in '123456789':
if is_valid(board, r, c, num):
board[r][c] = num
if solve(board):
return True
board[r][c] = '.'
return False
return True
solve(board)class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board)) return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[i][col] == c || board[row][i] == c ||
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
return false;
}
}
return true;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool isValid(vector<vector<char>>& board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[i][col] == c || board[row][i] == c ||
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
return false;
}
}
return true;
}
bool solve(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board)) return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}
};function solveSudoku(board) {
function isValid(board, r, c, num) {
for (let i = 0; i < 9; i++) {
if (board[i][c] == num || board[r][i] == num ||
board[Math.floor(r / 3) * 3 + Math.floor(i / 3)][Math.floor(c / 3) * 3 + i % 3] == num) {
return false;
}
}
return true;
}
function solve(board) {
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] == '.') {
for (let num = '1'; num <= '9'; num++) {
if (isValid(board, r, c, num)) {
board[r][c] = num;
if (solve(board)) return true;
board[r][c] = '.';
}
}
return false;
}
}
}
return true;
}
solve(board);
}#include <stdbool.h>
bool isValid(char board[9][9], int row, int col, char num) {
for (int x = 0; x < 9; x++) {
if (board[row][x] == num || board[x][col] == num ||
board[3 * (row / 3) + x / 3][3 * (col / 3) + x % 3] == num) {
return false;
}
}
return true;
}
bool solveSudokuHelper(char board[9][9]) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == '.') {
for (char num = '1'; num <= '9'; num++) {
if (isValid(board, row, col, num)) {
board[row][col] = num;
if (solveSudokuHelper(board)) return true;
board[row][col] = '.'; // Backtrack
}
}
return false; // Trigger backtracking
}
}
}
return true;
}
void solveSudoku(char board[9][9]) {
solveSudokuHelper(board);
}public class Solution {
public void SolveSudoku(char[][] board) {
Solve(board);
}
private bool Solve(char[][] board) {
for (int row = 0; row < board.Length; row++) {
for (int col = 0; col < board[0].Length; col++) {
if (board[row][col] == '.') {
for (char num = '1'; num <= '9'; num++) {
if (IsValid(board, row, col, num)) {
board[row][col] = num;
if (Solve(board)) return true;
board[row][col] = '.';
}
}
return false;
}
}
}
return true;
}
private bool IsValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[i][col] == c || board[row][i] == c ||
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
return false;
}
}
return true;
}
}The Python solution follows a similar strategy, using nested functions for validity checking and recursive backtracking. The is_valid helper ensures compliance with Sudoku rules while the recursive solve function attempts to solve the board.
Time Complexity: O(9^(N*N)) due to the possibility of exploring every configuration.
Space Complexity: O(N*N) due to recursion stack usage.
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.
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def isSafe(row, col, num):
for i in range(9):
if board[row][i] == str(num) or board[i][col] == str(num):
return False
if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == str(num):
return False
return True
def solveSudoku():
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in range(1, 10):
if isSafe(i, j, num):
board[i][j] = str(num)
if solveSudoku():
return True
board[i][j] = '.'
return False
return True
solveSudoku()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.
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.
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.
func solveSudoku(board [][]byte) {
var row, col [9][9]bool
var block [3][3][9]bool
var t [][2]int
ok := false
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] == '.' {
t = append(t, [2]int{i, j})
} else {
v := int(board[i][j] - '1')
row[i][v], col[j][v], block[i/3][j/3][v] = true, true, true
}
}
}
var dfs func(int)
dfs = func(k int) {
if k == len(t) {
ok = true
return
}
i, j := t[k][0], t[k][1]
for v := 0; v < 9; v++ {
if !row[i][v] && !col[j][v] && !block[i/3][j/3][v] {
row[i][v], col[j][v], block[i/3][j/3][v] = true, true, true
board[i][j] = byte(v + '1')
dfs(k + 1)
row[i][v], col[j][v], block[i/3][j/3][v] = false, false, false
}
if ok {
return
}
}
}
dfs(0)
}class Solution {
/**
* @param String[][] $board
* @return NULL
*/
function solveSudoku(&$board) {
$row = array_fill(0, 9, array_fill(0, 9, false));
$col = array_fill(0, 9, array_fill(0, 9, false));
$block = array_fill(0, 3, array_fill(0, 3, array_fill(0, 9, false)));
$ok = false;
$t = [];
for ($i = 0; $i < 9; ++$i) {
for ($j = 0; $j < 9; ++$j) {
if ($board[$i][$j] === '.') {
$t[] = [$i, $j];
} else {
$v = ord($board[$i][$j]) - ord('1');
$row[$i][$v] = true;
$col[$j][$v] = true;
$block[intval($i / 3)][intval($j / 3)][$v] = true;
}
}
}
$dfs = function ($k) use (&$dfs, &$board, &$row, &$col, &$block, &$ok, &$t) {
if ($k === count($t)) {
$ok = true;
return;
}
[$i, $j] = $t[$k];
for ($v = 0; $v < 9; ++$v) {
if (!$row[$i][$v] && !$col[$j][$v] && !$block[intval($i / 3)][intval($j / 3)][$v]) {
$row[$i][$v] = $col[$j][$v] = $block[intval($i / 3)][intval($j / 3)][$v] = true;
$board[$i][$j] = chr($v + ord('1'));
$dfs($k + 1);
if ($ok) {
return;
}
$row[$i][$v] = $col[$j][$v] = $block[intval($i / 3)][intval($j / 3)][
$v
] = false;
}
}
};
$dfs(0);
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(9^(N*N)) due to the possibility of exploring every configuration. |
| Constraint Propagation with Backtracking | Time Complexity: Expected better than O(9^(N*N)), depending on effectiveness of constraint propagation reducing possible combinations. |
| Backtracking | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Basic Backtracking | O(9^(n)) worst case | O(81) | Best for understanding the core recursion and constraint checks during interviews |
| Constraint Propagation + Backtracking | O(9^(n)) worst case but faster in practice | O(81) | Preferred for optimized implementations using row/column/box tracking or bitmasks |
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.