Sudoku: Where Plain Backtracking Runs Out

Sudoku is the problem where which decision to make next matters more than anything else in the algorithm. The rules are simple, the template is the one you already know, and a single change to the ordering makes the solver about four times cheaper.

Sudoku is graph coloring

Before the algorithm, a framing worth carrying with you. Make each of the 81 cells a node. Join two cells with an edge when they share a row, a column or a 3 by 3 box, meaning they're not allowed to hold the same digit. Now solving the puzzle is coloring that graph with 9 colors, where some nodes arrive pre-colored.

The similarity runs deeper than a comparison. Coloring a graph and solving a puzzle board are the same search wearing different labels, which is why the previous page's algorithm works here with almost no changes. It also sets your expectations straight: coloring is hard in general, so don't go looking for a formula.

The decision that actually matters

The obvious way to pick the next blank is reading order: top-left to bottom-right. It's simple, and there's nothing wrong with it except that it ignores information sitting right there in plain view.

Consider a blank with 6 legal digits and another with 1. Filling the 6-candidate cell means branching six ways, and if the puzzle is doomed from here, you'll discover that six times over. Filling the 1-candidate cell means branching once, and the digit is forced, so no guess is being made at all.

So a better rule: always fill the blank with the fewest legal digits remaining. This is called the most constrained variable heuristic, and versions of it show up across the whole of constraint solving.

Two things happen at once. Forced cells get filled immediately and for free, which is exactly what a human solver does. And when a guess is genuinely required, it happens where the branching factor is smallest, so a wrong guess gets discovered after the least possible work.

What it is worth

On the puzzle bundled with the widget below, the two orderings differ like this.

                       cells filled    dead ends    frames

reading order              185            56          heavy
fewest candidates           49             0          light

Same puzzle. Same rules. Same finished grid.
The only difference is which blank the solver picks next.

Read the dead-ends column again. The most-constrained ordering hit zero dead ends. It never guessed wrong, not because it got lucky, but because it kept choosing cells where the answer was already determined, and by the time a real choice was needed, the grid had enough information to make it safely.

Nothing about the rules changed. No prune was added. The solver simply asked its questions in a better order, which is a genuinely different kind of optimization from the ones earlier in this section, and often the most powerful one available.

Compare them yourself

Switch between the two orderings and watch the counters, since the finished grid is identical either way.

The implementation

The solver itself is the template unchanged, and everything interesting has moved into pickCell.

function solve(board) {
  const cell = pickCell(board);            // the only interesting decision
  if (cell === null) return true;          // no blanks left, we are done

  const [row, col] = cell;
  for (let d = 1; d <= 9; d++) {
    if (!isLegal(board, row, col, d)) continue;

    board[row][col] = d;                   // choose
    if (solve(board)) return true;         // explore
    board[row][col] = 0;                   // un-choose
  }

  return false;                            // every digit failed here
}

// Naive: the first blank in reading order.
function firstBlank(board) { ... }

// Better: the blank with the fewest legal digits remaining.
function mostConstrained(board) {
  let best = null, bestCount = 10;
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] !== 0) continue;
      const count = countLegalDigits(board, r, c);
      if (count < bestCount) { bestCount = count; best = [r, c]; }
      if (count === 1) return best;        // cannot do better than forced
    }
  }
  return best;
}

The early return when a cell has exactly one candidate is a small but real saving. No cell can beat forced, so there's no point scanning the remaining blanks once you've found one.

Where solvers go from here

Two more ideas turn this into something that handles the puzzles marketed as impossible.

The first is constraint propagation. After placing a digit, update the candidate lists of every cell that sees it. If any cell drops to zero candidates, the branch is dead immediately rather than several placements later. If any drops to one, fill it at once and propagate again. Much of a hard puzzle solves itself this way with no guessing at all.

The second is the least-constraining value: among the digits legal for the chosen cell, try first the one that removes the fewest options from its neighbors. Choose the cell that constrains you most, then the value that constrains you least. That pairing is the standard shape of a good constraint solver.

Where it goes wrong

Recomputing candidate counts from scratch on every call. Correct, and it can cost more than the search it's supposed to save on large grids. Keep the counts updated as cells are filled and cleared.

Forgetting the box check. Row and column are easy to remember, and the 3 by 3 box is easy to leave out. The solver then produces grids that look almost right and violate the one rule everyone checks last.

Not undoing on failure. Same bug as everywhere else in this section, and here it leaves stale digits that make later branches look illegal, so the solver reports an unsolvable puzzle that's perfectly solvable.

Assuming one solution exists. A proper Sudoku has exactly one. A puzzle with too few givens has many, and a solver that stops at the first will happily hand you back one of them. If uniqueness matters, keep searching after the first success and count.

Check yourself