Sudoku, and Where Plain Backtracking Runs Out

Sudoku is the natural end of this section. The rules are three constraints, the search is the same template as every other page here, and a working solver is about twenty lines.

It is also where the template alone stops being enough, and the interesting decisions move somewhere else entirely.

The obvious solver

Find a blank cell. Try 1 through 9 in it. For each value that does not already appear in the same row, column or 3 by 3 box, place it and recurse. If nothing works, blank the cell and report failure upward.

That is correct and complete. Given enough time it solves any solvable grid, and given a nearly empty grid it will take a very long time indeed.

Which blank cell, though?

"Find a blank cell" hides the only decision that matters. Taking the next one in reading order is the obvious choice and a poor one.

The alternative is to take the blank cell with the fewest legal values remaining. If some cell has only one candidate, filling it is not a guess at all. If some cell has zero, the branch is already dead and you have just found that out without exploring it. This is the most constrained variable heuristic, and it is the same idea as colouring the most constrained node first on the previous page.

Switch between the two below on the same puzzle. The counters at the right report both.

Reading order fills 185 cells and hits 56 dead ends. Fewest candidates fills 49 and hits none, meaning it never once guessed wrong on this grid. Same algorithm, same finished grid, roughly a quarter of the work.

Step through the reading-order run and watch what a dead end costs. The solver commits to a value near the top of the grid, descends a long way on the strength of it, discovers a cell with no candidates, and unwinds everything in between. The heuristic version asks about that cell while the guess is still fresh.

In code

// board is a flat array of 81 numbers, 0 for blank.
function solveSudoku(board) {
  function candidates(cell) {
    const row = Math.floor(cell / 9);
    const col = cell % 9;
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 3;
    const taken = new Set();

    for (let i = 0; i < 9; i++) {
      taken.add(board[row * 9 + i]);                                   // row
      taken.add(board[i * 9 + col]);                                   // column
      taken.add(board[(boxRow + Math.floor(i / 3)) * 9 + boxCol + (i % 3)]);  // box
    }

    const out = [];
    for (let v = 1; v <= 9; v++) if (!taken.has(v)) out.push(v);
    return out;
  }

  // The heuristic: fewest options first. A cell with one candidate is
  // forced, and a cell with none kills the branch immediately.
  function pickCell() {
    let best = null;
    let bestCount = 10;
    for (let i = 0; i < 81; i++) {
      if (board[i] !== 0) continue;
      const count = candidates(i).length;
      if (count < bestCount) {
        best = i;
        bestCount = count;
        if (count === 0) break;      // nothing beats finding this out now
      }
    }
    return best;
  }

  function solve() {
    const cell = pickCell();
    if (cell === null) return true;  // no blanks left

    for (const v of candidates(cell)) {
      board[cell] = v;               // choose
      if (solve()) return true;      // explore
      board[cell] = 0;               // un-choose
    }

    return false;
  }

  return solve();
}

The heuristic costs a scan of all 81 cells per step, which sounds expensive and is not. Recomputing candidates 81 times is cheap next to descending forty levels into a branch that was doomed at the top.

Constraint propagation, the step beyond

There is a further idea that changes the character of the solver rather than tuning it.

Instead of searching and checking, keep a set of candidates for every cell and shrink those sets as facts arrive. Assigning a value removes it from every peer's candidate set. That removal can leave some peer with a single candidate, which is now forced, so assign it too, which removes more, and so on. The consequences cascade without any guessing at all.

On easy puzzles that alone finishes the grid. On hard ones it runs out, at which point you guess a value, propagate again, and back out if the propagation reaches a contradiction. Search becomes the fallback rather than the main strategy.

Peter Norvig's essay Solving Every Sudoku Puzzle is the standard treatment, and worth reading in full once this section makes sense. His opening claim is that it takes about a page of code using two ideas, constraint propagation and search, which is a fair summary of where this material ends up.

That last row is Knuth's Dancing Links again. Sudoku, n-queens and polyomino tiling all turn out to be the same exact cover problem underneath, which is a satisfying place for this section to land: six problems that looked different have been the same search the whole way.

Check yourself

Where to go next

The best way to make this stick is volume. The CSES Problem Set has a free graded collection with judged submissions, and its introductory section includes the classic grid-path and permutation-search problems this section prepares you for.