Log inSign up
hardLeetCodeNot Started

Sudoku Solver

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

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: board = [ ["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: Every row, column, and 3x3 sub-box contains digits 1-9 without repetition.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master grid coordinate mapping for sub-boxes: boxIndex = (row / 3) * 3 + (col / 3).
  • Learn early boolean exit propagation in backtracking (if (solve()) return true).
  • Utilize bitmask integers for instantaneous O(1) constraint tracking.

1. Linear Scan Validation Backtracking

Intuition

Iterate across all 81 cells. If board[i][j] == '.', try '1' to '9'. Function isValid(board, row, col, c) checks if c appears in row, in col, or in the 3x3 block 3 * (row / 3) + i / 3 and 3 * (col / 3) + i % 3.

Algorithm

  1. Step 1: Fill all empty cells with random digits 1 to 9.
  2. Step 2: Validate the entire 9x9 board across all 9 rows, 9 columns, and 9 3x3 sub-boxes.
  3. Step 3: If valid, return board; otherwise try next configuration.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 bool isValid(const std::vector<std::vector<char>>& board, int row, int col, char c) {
7 for (int i = 0; i < 9; i++) {
8 if (board[row][i] == c) return false;
9 if (board[i][col] == c) return false;
10 if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
11 }
12 return true;
13 }
14
15 bool solve(std::vector<std::vector<char>>& board) {
16 for (int i = 0; i < 9; i++) {
17 for (int j = 0; j < 9; j++) {
18 if (board[i][j] == '.') {
19 for (char c = '1'; c <= '9'; c++) {
20 if (isValid(board, i, j, c)) {
21 board[i][j] = c;
22 if (solve(board)) return true;
23 board[i][j] = '.';
24 }
25 }
26 return false;
27 }
28 }
29 }
30 return true;
31 }
32
33 void solveSudoku(std::vector<std::vector<char>>& board) {
34 solve(board);
35 }
36};
37
38int main() {
39 Solution solver;
40 std::vector<std::vector<char>> board = {
41 {'5','3','.','.','7','.','.','.','.'},
42 {'6','.','.','1','9','5','.','.','.'},
43 {'.','9','8','.','.','.','.','6','.'},
44 {'8','.','.','.','6','.','.','.','3'},
45 {'4','.','.','8','.','3','.','.','1'},
46 {'7','.','.','.','2','.','.','.','6'},
47 {'.','6','.','.','.','.','2','8','.'},
48 {'.','.','.','4','1','9','.','.','5'},
49 {'.','.','.','.','8','.','.','7','9'}
50 };
51 solver.solveSudoku(board);
52 std::cout << "Solved Sudoku Board:\n";
53 for (const auto& row : board) {
54 for (char c : row) std::cout << c << " ";
55 std::cout << "\n";
56 }
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(9^m * 9) — m empty cells, testing up to 9 digits each with O(9) validation checks.
  • Space complexity: O(1) recursion depth bounded by 81 — Recursion depth is at most 81 frames.

2. Boolean Constraint Arrays

Intuition

Pre-populate the tables from initial numbers. When testing digit d at (r, c): check !rows[r][d] && !cols[c][d] && !boxes[boxIndex][d]. Setting and resetting these flags is O(1).

Algorithm

  1. Step 1: Find the first empty cell (r, c) on the board containing ..
  2. Step 2: If no empty cells remain, puzzle is solved; return true.
  3. Step 3: Try placing digits 1 to 9.
  4. Step 4: Check isValid(board, r, c, digit) by scanning row r, column c, and 3x3 subgrid in O(9) = O(1).
  5. Step 5: If valid, place board[r][c] = digit and recurse solve(board). If true, return true.
  6. Step 6: Backtrack by resetting board[r][c] = ..
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 bool rows[9][10] = {false};
7 bool cols[9][10] = {false};
8 bool boxes[9][10] = {false};
9 std::vector<std::pair<int, int>> emptyCells;
10
11 bool backtrack(int index, std::vector<std::vector<char>>& board) {
12 if (index == (int)emptyCells.size()) return true;
13
14 auto [r, c] = emptyCells[index];
15 int b = (r / 3) * 3 + (c / 3);
16
17 for (int d = 1; d <= 9; d++) {
18 if (!rows[r][d] && !cols[c][d] && !boxes[b][d]) {
19 rows[r][d] = cols[c][d] = boxes[b][d] = true;
20 board[r][c] = d + '0';
21
22 if (backtrack(index + 1, board)) return true;
23
24 rows[r][d] = cols[c][d] = boxes[b][d] = false;
25 board[r][c] = '.';
26 }
27 }
28 return false;
29 }
30
31 void solveSudoku(std::vector<std::vector<char>>& board) {
32 for (int r = 0; r < 9; r++) {
33 for (int c = 0; c < 9; c++) {
34 if (board[r][c] != '.') {
35 int d = board[r][c] - '0';
36 int b = (r / 3) * 3 + (c / 3);
37 rows[r][d] = cols[c][d] = boxes[b][d] = true;
38 } else {
39 emptyCells.push_back({r, c});
40 }
41 }
42 }
43 backtrack(0, board);
44 }
45};
46
47int main() {
48 Solution solver;
49 std::vector<std::vector<char>> board = {
50 {'5','3','.','.','7','.','.','.','.'},
51 {'6','.','.','1','9','5','.','.','.'},
52 {'.','9','8','.','.','.','.','6','.'},
53 {'8','.','.','.','6','.','.','.','3'},
54 {'4','.','.','8','.','3','.','.','1'},
55 {'7','.','.','.','2','.','.','.','6'},
56 {'.','6','.','.','.','.','2','8','.'},
57 {'.','.','.','4','1','9','.','.','5'},
58 {'.','.','.','.','8','.','.','7','9'}
59 };
60 solver.solveSudoku(board);
61 std::cout << "Solved with Boolean Arrays:\n";
62 for (char c : board[0]) std::cout << c << " ";
63 std::cout << "\n";
64 return 0;
65}

Time & Space Complexity

  • Time complexity: O(9^m) — O(1) check replaces linear scan for each of the 9m branch states.
  • Space complexity: O(1) — Fixed boolean tables of size 9x10 = 90 booleans.

3. Bitmask State Vector Backtracking (Gold Standard)

Intuition

Testing if digit d is available: !((rows[r] | cols[c] | boxes[b]) & (1 << d)). Placing and removing digit d toggles bit 1 << d with XOR ^= (1 << d). This yields lightning fast register-level execution.

Algorithm

  1. Step 1: Maintain bitmasks rowMask[9], colMask[9], and boxMask[3][3] to track used digits in O(1) bitwise operations.
  2. Step 2: In solve(board): locate next empty cell (r, c). If none, puzzle is solved; return true.
  3. Step 3: Compute candidate digits using bitwise NOT of (rowMask[r] | colMask[c] | boxMask[r/3][c/3]).
  4. Step 4: For each valid bit digit d (1 to 9): set bits in rowMask, colMask, and boxMask, assign board[r][c] = d.
  5. Step 5: Recurse on solve(board). If successful, return true.
  6. Step 6: Backtrack: clear bits and reset board[r][c] = ..

Sudoku Board Placement Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Locate first empty cell '
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
5
3
.
↑ curr
7
Variables at this step
row
0
col
2
currentVal
.
Check / comparison
Cell (0,2) is '.' (Empty)
Decision / next transition
Test digit validity for numbers 1 to 9
Why this step matters

Locate first empty cell . at row 0, col 2. Inspect candidate digits 1 to 9.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int rowMask[9] = {0};
7 int colMask[9] = {0};
8 int boxMask[9] = {0};
9 std::vector<std::pair<int, int>> emptyCells;
10
11 bool backtrack(int index, std::vector<std::vector<char>>& board) {
12 if (index == (int)emptyCells.size()) return true;
13
14 auto [r, c] = emptyCells[index];
15 int b = (r / 3) * 3 + (c / 3);
16 int usedMask = rowMask[r] | colMask[c] | boxMask[b];
17
18 for (int d = 1; d <= 9; d++) {
19 int bit = 1 << d;
20 if (!(usedMask & bit)) {
21 rowMask[r] ^= bit;
22 colMask[c] ^= bit;
23 boxMask[b] ^= bit;
24 board[r][c] = d + '0';
25
26 if (backtrack(index + 1, board)) return true;
27
28 rowMask[r] ^= bit;
29 colMask[c] ^= bit;
30 boxMask[b] ^= bit;
31 board[r][c] = '.';
32 }
33 }
34 return false;
35 }
36
37 void solveSudoku(std::vector<std::vector<char>>& board) {
38 for (int r = 0; r < 9; r++) {
39 for (int c = 0; c < 9; c++) {
40 if (board[r][c] != '.') {
41 int d = board[r][c] - '0';
42 int bit = 1 << d;
43 int b = (r / 3) * 3 + (c / 3);
44 rowMask[r] |= bit;
45 colMask[c] |= bit;
46 boxMask[b] |= bit;
47 } else {
48 emptyCells.push_back({r, c});
49 }
50 }
51 }
52 backtrack(0, board);
53 }
54};
55
56int main() {
57 Solution solver;
58 std::vector<std::vector<char>> board = {
59 {'5','3','.','.','7','.','.','.','.'},
60 {'6','.','.','1','9','5','.','.','.'},
61 {'.','9','8','.','.','.','.','6','.'},
62 {'8','.','.','.','6','.','.','.','3'},
63 {'4','.','.','8','.','3','.','.','1'},
64 {'7','.','.','.','2','.','.','.','6'},
65 {'.','6','.','.','.','.','2','8','.'},
66 {'.','.','.','4','1','9','.','.','5'},
67 {'.','.','.','.','8','.','.','7','9'}
68 };
69 solver.solveSudoku(board);
70 std::cout << "Optimal Bitmask Solved Sudoku:\n";
71 for (const auto& row : board) {
72 for (char c : row) std::cout << c << " ";
73 std::cout << "\n";
74 }
75 return 0;
76}

Time & Space Complexity

  • Time complexity: O(9^m) — Fastest possible backtracking loop running entirely on CPU registers.
  • Space complexity: O(1) — O(1) memory for three 9-integer bit arrays.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Scan Validation BacktrackingO(9^m * 9)O(1)For each empty cell, test 1-9 by scanning row, col, and box in O(9) time per check.Linear cell scanning during validation
2.Boolean Hash Table Sets (Better)O(9^m)O(1)Maintain boolean arrays rowUsed[9][10], colUsed[9][10], boxUsed[9][10] for O(1) checks.Array indexing
3.Bitmask State Vector Backtracking (Optimal)OptimalO(9^m)O(1)Use 9-bit integers rows[9], cols[9], boxes[9] with bitwise XOR for instant updates.Branching factor

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Returning false immediately after the loop over 1-9 without checking if any recursive branch returned true.

Pitfall 2:

Incorrect box index math: must use (row / 3) * 3 + (col / 3).

Crucial Edge Cases to Validate:

  • Nearly full board (e.g. 1 empty cell) -> solved in O(1) step.
  • Hard Sudoku with extensive branch pruning -> solves in under 5ms using bitmasking.
  • Grid containing all numbers 1-9 already placed -> returns immediately true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by stating the 3 Sudoku constraints and how box index is computed.
  2. Highlight the difference between searching cells iteratively vs collecting empty cells into a list first for cleaner code.
  3. Discuss Dancing Links (Algorithm X) by Donald Knuth as the theoretical exact cover optimization for generalized N*N Sudokus.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does the formula (row / 3) * 3 + (col / 3) map every (row, col) cell to its 3x3 sub-box index (0 to 8)?

Back to DSA Sheet