The Algorithm Behind Solving Any Sudoku Puzzle in Milliseconds

Sudoku is a constraint satisfaction problem disguised as a number puzzle. Every cell must satisfy three constraints simultaneously: its row contains each digit 1-9 exactly once, its column contains each digit 1-9 exactly once, and its 3x3 box contains each digit 1-9 exactly once.

A standard 9x9 Sudoku has 81 cells. A typical puzzle provides 25-35 clues. That leaves 46-56 cells to fill. The brute force search space is enormous -- up to 9^56 possibilities. Yet a well-implemented solver handles any valid puzzle in under 10 milliseconds. The secret is constraint propagation combined with backtracking.

Constraint propagation: the first pass

Before doing any searching, you can eliminate candidates from each empty cell based on what is already placed.

For each empty cell, start with candidates {1,2,3,4,5,6,7,8,9}. Remove any digit that already appears in the same row, column, or box. After this single pass, many cells are reduced to a handful of candidates, and some cells are reduced to a single candidate -- meaning they are solved.

When you solve a cell, that triggers further reductions in its row, column, and box. This cascade can sometimes solve the entire puzzle without any guessing.

function propagate(grid) {
  let changed = true;
  while (changed) {
    changed = false;
    for (let i = 0; i < 81; i++) {
      if (grid[i].candidates.length === 1) continue;
      const peers = getPeers(i);
      const eliminated = peers
        .filter(p => grid[p].candidates.length === 1)
        .map(p => grid[p].candidates[0]);
      const before = grid[i].candidates.length;
      grid[i].candidates = grid[i].candidates
        .filter(c => !eliminated.includes(c));
      if (grid[i].candidates.length < before) changed = true;
      if (grid[i].candidates.length === 0) return false; // contradiction
    }
  }
  return true;
}

Naked singles and hidden singles

Constraint propagation handles "naked singles" -- cells with only one candidate. But there is another pattern: "hidden singles." If a digit can only go in one place within a row, column, or box, it must go there, even if that cell has other candidates.

For example, if in row 3, the digit 7 has been eliminated from every cell except cell (3,5), then cell (3,5) must be 7, regardless of what other candidates it has. Adding hidden single detection to the propagation step solves most easy and medium puzzles without any backtracking.

Backtracking: the search fallback

For harder puzzles, propagation alone is not enough. You need to guess. Backtracking search works like this:

1. Find the empty cell with the fewest candidates (minimum remaining values heuristic).
2. Try each candidate.
3. For each guess, propagate constraints.
4. If propagation succeeds, recurse to the next empty cell.
5. If propagation finds a contradiction (a cell with zero candidates), undo the guess and try the next candidate.
6. If all candidates for a cell lead to contradictions, backtrack to the previous cell.

The minimum remaining values (MRV) heuristic is critical. By choosing the cell with the fewest candidates first, you minimize the branching factor at each step. A cell with 2 candidates creates 2 branches. A cell with 8 candidates creates 8 branches. Solving the most constrained cell first prunes the search tree dramatically.

function solve(grid) {
  if (!propagate(grid)) return null;

  const unsolved = grid
    .map((cell, i) => ({ i, count: cell.candidates.length }))
    .filter(c => c.count > 1)
    .sort((a, b) => a.count - b.count);

  if (unsolved.length === 0) return grid; // solved

  const target = unsolved[0].i;
  for (const candidate of grid[target].candidates) {
    const copy = deepCopy(grid);
    copy[target].candidates = [candidate];
    const result = solve(copy);
    if (result) return result;
  }
  return null; // no solution
}

Why this matters beyond puzzles

Sudoku solving is a miniature version of real-world constraint satisfaction problems. The same algorithmic pattern -- propagate constraints, then search with backtracking -- applies to scheduling, resource allocation, circuit design, and compiler register assignment.

Understanding backtracking search with constraint propagation teaches you the most broadly applicable problem-solving pattern in computer science. It is the backbone of SAT solvers, which power everything from hardware verification to package dependency resolution.

The practical tool

I built a Sudoku solver at zovo.one/free-tools/sudoku-solver that implements this algorithm with a visual step-through mode. You can enter any puzzle (or import one from a photo), and it solves it instantly while showing the propagation and backtracking steps. It is useful both as a solving tool and as a teaching aid for understanding constraint satisfaction algorithms.

I'm Michael Lip. I build free developer tools at zovo.one. 500+ tools, all private, all free.