AlgoMaster Logo

Sudoku Solver

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We are given a 9x9 Sudoku board with some cells already filled and others marked with '.'. Our job is to fill every empty cell with a digit from 1 to 9 such that no digit repeats in any row, any column, or any of the nine 3x3 sub-boxes. The board is modified in-place, so we don't return anything.

This is a constraint satisfaction problem. At each empty cell we have up to 9 choices, and many of them are eliminated by the row, column, and box constraints. The solution is to place a digit, move on to the next empty cell, and if we reach a dead end where no digit is valid, undo the choice and try the next digit. This is backtracking.

The constraints are what make the search tractable. A single placement eliminates possibilities in its row, its column, and its box at the same time, which prunes large parts of the search space before we ever explore them.

Key Constraints:

  • board.length == 9 and board[i].length == 9 → The board is always exactly 9x9. This is a fixed, small size, so even exponential approaches are feasible as long as we prune aggressively.
  • board[i][j] is a digit or '.' → We only need to fill cells containing '.'. Pre-filled cells are guaranteed to be valid.
  • The input board has only one solution → We can stop as soon as we find the first valid completion. No need to enumerate all solutions.

Approach 1: Brute Force Backtracking

Intuition

Classic backtracking solves this directly. Find the first empty cell, try placing digits 1 through 9, and for each digit check whether it violates any Sudoku constraint. If the digit is valid, place it and recursively try to fill the next empty cell. If we get stuck (no digit works for some cell), backtrack by removing the last digit we placed and trying the next option.

The validity check scans the row for a duplicate, scans the column for a duplicate, and scans the 3x3 box for a duplicate. This is correct but does redundant work, since we re-scan the same row, column, and box for every digit we try.

Algorithm

  1. Scan the board to find the first cell containing '.'.
  2. If no empty cell exists, the board is solved. Return true.
  3. For each digit from '1' to '9':
    • Check if placing this digit at the current cell is valid by scanning the row, column, and 3x3 box.
    • If valid, place the digit on the board.
    • Recursively attempt to solve the rest of the board.
    • If the recursion succeeds, return true.
    • If the recursion fails, remove the digit (set cell back to '.') and try the next digit.
  4. If no digit from 1 to 9 works, return false (triggers backtracking in the caller).

Example Walkthrough

Input:

0
1
2
3
4
5
6
7
8
0
5
3
.
.
7
.
.
.
.
1
6
.
.
1
9
5
.
.
.
2
.
9
8
.
.
.
.
6
.
3
8
.
.
.
6
.
.
.
3
4
4
.
.
8
.
3
.
.
1
5
7
.
.
.
2
.
.
.
6
6
.
6
.
.
.
.
2
8
.
7
.
.
.
4
1
9
.
.
5
8
.
.
.
.
8
.
.
7
9

The brute force approach scans left to right, top to bottom. The first empty cell is (0,2). For each candidate digit it scans all of row 0, column 2, and the top-left 3x3 box to check validity. It tries '1' and '2', both of which pass the local check but fail deeper in the recursion and get undone. '3' is rejected immediately because row 0 already contains a '3' at (0,1). '4' is valid and, after the recursion fills the remaining 50-odd empty cells without hitting a dead end, leads to the completed board shown below.

Output:

0
1
2
3
4
5
6
7
8
0
5
3
4
6
7
8
9
1
2
1
6
7
2
1
9
5
3
4
8
2
1
9
8
3
4
2
5
6
7
3
8
5
9
7
6
1
4
2
3
4
4
2
6
8
5
3
7
9
1
5
7
1
3
9
2
4
8
5
6
6
9
6
1
5
3
7
2
8
4
7
2
8
7
4
1
9
6
3
5
8
3
4
5
2
8
6
1
7
9

Code

Every digit we try costs a scan of 27 cells for the validity check. The next approach removes that cost by tracking which digits are already used in each row, column, and box, turning each validity check into a constant-time lookup.

Approach 2: Backtracking with Hash Set Constraint Tracking

Intuition

The brute force re-scans the board for every validity check. Instead, before solving, precompute three collections of sets. rows[i] stores the digits already present in row i. cols[j] stores the digits in column j. boxes[k] stores the digits in box k, where the box index for cell (r, c) is (r / 3) * 3 + (c / 3).

To check if digit d is valid at position (r, c), we do three set lookups: is d in rows[r], in cols[c], or in boxes[boxIndex]? Each lookup is O(1). When we place a digit, we add it to all three sets. When we backtrack, we remove it from all three.

Algorithm

  1. Initialize three arrays of sets: rows[9], cols[9], boxes[9].
  2. Scan the board. For each pre-filled digit at (r, c), add it to rows[r], cols[c], and boxes[(r/3)*3 + c/3].
  3. Call the recursive backtracking function starting from cell (0, 0).
  4. In the recursive function:
    • Find the next empty cell by advancing through the board row by row.
    • If no empty cell remains, return true (board is solved).
    • For each digit '1' to '9': if the digit is not in rows[r], cols[c], or boxes[boxIndex], place it, recurse, and backtrack if needed.
    • If no digit works, return false.

Example Walkthrough

board
1Init: populate rows[], cols[], boxes[] sets from given digits
0
1
2
3
4
5
6
7
8
0
5
3
.
.
7
.
.
.
.
1
6
.
.
1
9
5
.
.
.
2
.
9
8
.
.
.
.
6
.
3
8
.
.
.
6
.
.
.
3
4
4
.
.
8
.
3
.
.
1
5
7
.
.
.
2
.
.
.
6
6
.
6
.
.
.
.
2
8
.
7
.
.
.
4
1
9
.
.
5
8
.
.
.
.
8
.
.
7
9
rows[0]
1rows[0] initialized with digits from row 0: {3, 5, 7}
3
:
true
5
:
true
7
:
true
1/8

Code

We still process empty cells in board order. But some cells have only one valid option while others have five or six. The next approach always fills the most constrained cell first, which cuts the number of branches the recursion has to explore.

Approach 3: Backtracking with Bitmask Constraints and MRV Heuristic

Intuition

The previous approach tracked constraints with boolean arrays. Bitmasks make the same checks tighter. For each row, column, and box we store a 9-bit integer where bit i being set means digit (i+1) is already used. To find the available digits for a cell, OR the three bitmasks together and invert the low 9 bits: every remaining set bit is a candidate.

The larger gain comes from the Minimum Remaining Values (MRV) heuristic from constraint satisfaction. Instead of filling empty cells left to right, always pick the empty cell with the fewest valid candidates. A cell with one candidate causes no branching, since there is only one digit to try. Choosing the most constrained cell at each step minimizes the branching factor near the top of the recursion tree, where a wide branch is most expensive.

Algorithm

  1. Initialize bitmask arrays: rowMask[9], colMask[9], boxMask[9], each starting at 0.
  2. Scan the board. For each pre-filled digit d at (r, c), set bit (d-1) in the corresponding masks.
  3. Collect all empty cell positions into a list.
  4. In the recursive function:
    • If no empty cells remain, return true.
    • Find the empty cell with the fewest valid candidates (MRV).
    • For each valid candidate digit, place it, recurse, and backtrack if needed.

Example Walkthrough

1Init bitmasks. Find MRV cell: (2,0) has only 1 candidate
0
1
2
3
4
5
6
7
8
0
5
3
3 opts
.
.
7
.
.
.
.
1
6
.
.
1
9
5
.
.
.
2
MRV: 1 opt
.
9
8
.
.
.
.
6
.
3
8
.
.
.
6
.
.
.
3
4
4
.
.
8
.
3
.
.
1
5
7
.
.
.
2
.
.
.
6
6
.
6
.
.
.
.
2
8
.
7
.
.
.
4
1
9
.
.
5
8
.
.
.
.
8
.
.
7
9
1/6

Code