Sudoku Solver, in depth: bitmask candidates, MRV, hidden singles, exact cover with Algorithm X, uniqueness and generation

State: three arrays of bitmasks

A grid has 81 cells, 27 units (nine rows, nine columns, nine 3 by 3 boxes) and every cell sits in exactly three units. The rule is that each unit contains each digit once. The naive solver tries digits 1 to 9 in the first empty cell, checks the rule by scanning the row, column and box, and recurses. It works, but each check costs 27 reads and it branches in whatever order the cells happen to appear.

A better state is three arrays of nine 9-bit masks: rows[r], cols[c] and boxes[b], where bit d - 1 is set when digit d is already used in that unit. The candidates for a cell are then one expression:

ALL = 0x1FF                                  # nine bits: digits 1..9
box = (r // 3) * 3 + c // 3
candidates = ALL & ~(rows[r] | cols[c] | boxes[box])

Placing a digit sets one bit in three masks; undoing it clears the same three bits. Counting candidates is a popcount, and iterating them uses m & -m to peel off the lowest set bit. The whole state fits in 27 small integers plus the grid itself, so undo is trivial and no copying is needed.

Worked example: candidates in a hard puzzle

Take the puzzle Arto Inkala published in 2012 and promoted as the hardest Sudoku, which has 21 givens:

8 . . | . . . | . . .
. . 3 | 6 . . | . . .
. 7 . | . 9 . | 2 . .
------+-------+------
. 5 . | . . 7 | . . .
. . . | . 4 5 | 7 . .
. . . | 1 . . | . 3 .
------+-------+------
. . 1 | . . . | . 6 8
. . 8 | 5 . . | . 1 .
. 9 . | . . . | 4 . .

Consider the cell in row 0, column 1. Row 0 uses {8}. Column 1 uses {7, 5, 9}. The top-left box uses {8, 3, 7}. The union is {3, 5, 7, 8, 9}, so the candidates are {1, 2, 4, 6}, the mask 0b000101011, decimal 43. Four is the most common count among the 60 empty cells, and not one cell starts with a single candidate; the minimum is two. That is precisely what makes it hard: there is nothing to propagate at the start, so the solver must branch immediately.

The solver: MRV and dead-end detection

The solver below chooses the empty cell with the fewest candidates at every node, the minimum remaining values rule, and stops early if any cell has none. It collects solutions up to a limit, which is how the same function both solves and checks uniqueness.

ROW = [i // 9 for i in range(81)]
COL = [i % 9 for i in range(81)]
BOX = [(i // 27) * 3 + (i % 9) // 3 for i in range(81)]

def solve(grid, limit=2):
    rows, cols, boxes, cells = [0] * 9, [0] * 9, [0] * 9, [0] * 81
    for i, ch in enumerate(grid):
        if ch in "123456789":
            bit = 1 << (int(ch) - 1)
            if (rows[ROW[i]] | cols[COL[i]] | boxes[BOX[i]]) & bit:
                return []                          # givens already clash
            rows[ROW[i]] |= bit; cols[COL[i]] |= bit; boxes[BOX[i]] |= bit
            cells[i] = int(ch)
    solutions = []

    def search():
        best, best_mask, best_n = -1, 0, 10
        for i in range(81):
            if cells[i]:
                continue
            mask = ALL & ~(rows[ROW[i]] | cols[COL[i]] | boxes[BOX[i]])
            n = bin(mask).count("1")
            if n < best_n:
                best, best_mask, best_n = i, mask, n
                if n <= 1:
                    break
        if best == -1:                             # grid full
            solutions.append("".join(map(str, cells)))
            return len(solutions) >= limit
        if best_n == 0:
            return False                           # dead end
        r, c, b, m = ROW[best], COL[best], BOX[best], best_mask
        while m:
            bit = m & -m
            m ^= bit
            rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit
            cells[best] = bit.bit_length()
            if search():
                return True
            rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit
            cells[best] = 0
        return False

    search()
    return solutions

Two details matter. The validation of givens rejects puzzles that are already contradictory; without it the solver can report a "solution" to an invalid input. And best_n == 0 is the cheapest possible dead-end test: one cell with no candidates means the whole subtree is empty, so you prune it without trying anything.

Propagation: hidden singles and the cost per node

MRV handles naked singles for free: a cell with one candidate is chosen first and its "branch" is forced. It misses hidden singles, where a digit has only one possible place in some unit even though that cell still shows several candidates. The fix is to widen the branch choice: for every unit and digit, count the places the digit could go, and branch on whichever option list is shortest, a cell's candidates or a unit-digit's places. A unit-digit with zero places is also a dead end, often detected earlier than an empty cell.

On a laptop, in CPython, counting every node until uniqueness is proved, we measured:

The node count falls sharply in both cases. Wall time falls only for the 17-clue puzzle: on Inkala's puzzle the extra scanning per node costs more in Python than the branches it saves. That is the usual trade-off in constraint search. Stronger propagation shrinks the tree but makes each node more expensive, and the right balance depends on the language and on how incremental your bookkeeping is. Fast solvers keep per-unit digit counts up to date as they place and undo, so hidden singles cost almost nothing to find.

Sudoku as exact cover

Sudoku is an exact cover problem. Make one column for each constraint that must be satisfied exactly once: each cell is filled (81), each row has each digit (81), each column has each digit (81) and each box has each digit (81), 324 columns in all. Make one row for each possible placement (cell, digit), 729 rows, each covering exactly four columns. A solution is a set of rows that covers every column exactly once. Knuth's Algorithm X searches this directly: pick the column with fewest remaining rows, try each row, remove every conflicting row, recurse, and restore.

def exact_cover_sudoku(grid):
    Y = {(r, c, d): [("rc", r, c), ("rn", r, d), ("cn", c, d), ("bn", (r // 3) * 3 + c // 3, d)]
         for r in range(9) for c in range(9) for d in range(9)}
    X = {}
    for row, cols in Y.items():
        for col in cols:
            X.setdefault(col, set()).add(row)     # 324 columns, 729 rows

    def select(row):
        removed = []
        for j in Y[row]:
            for i in X[j]:
                for k in Y[i]:
                    if k != j:
                        X[k].remove(i)
            removed.append(X.pop(j))
        return removed

    def deselect(row, removed):
        for j in reversed(Y[row]):
            X[j] = removed.pop()
            for i in X[j]:
                for k in Y[i]:
                    if k != j:
                        X[k].add(i)
    ...  # select every given, then search: min column, try rows, select, recurse, deselect

Choosing the column with fewest rows is MRV and hidden singles at once, because the four column types cover both "this cell has few digits" and "this digit has few places in this unit". That is why the exact cover form is so effective with no Sudoku-specific rules. Knuth's dancing links (2000) implements the same idea with doubly linked lists so removal and restoration are O(1) pointer swaps. The dictionary of sets version above is shorter and was verified to return the same solution as the bitmask solver on Inkala's puzzle.

Uniqueness checking

A proper puzzle has exactly one solution. Checking this is the reason the solver takes a limit: search with limit=2 and stop as soon as a second solution appears. A puzzle with zero solutions is invalid, two or more is ambiguous. Note that proving uniqueness costs more than solving, because the search must exhaust the tree after finding the first answer; the node counts above include that work.

Two facts frame the search space. There are 6,670,903,752,021,072,936,960 completed grids (Felgenhauer and Jarvis, 2005). And no puzzle with fewer than 17 givens has a unique solution, proved by McGuire, Tugemann and Civario in 2012 with an exhaustive computer search. A 16-clue input will always fail a uniqueness check.

Generating puzzles

Generation reuses the solver. Fill an empty grid with the digit order shuffled per cell to get a random complete grid. Then visit the cells in random order, remove each clue, and keep the removal only if the puzzle still has exactly one solution.

def generate(rng, solve_random, count_solutions):
    grid = list(solve_random("0" * 81, rng))       # random full grid
    for i in rng.sample(range(81), 81):
        keep = grid[i]
        grid[i] = "0"
        if count_solutions("".join(grid), limit=2) != 1:
            grid[i] = keep                         # removal broke uniqueness
    return "".join(grid)

This yields a minimal puzzle, where no single clue can be removed. In twenty seeded runs of this generator, filling the grid with a randomised digit order, the results had between 22 and 27 givens. Difficulty is a separate question. Node count is a poor proxy because it depends on the solver. Graders instead solve with a ladder of human techniques, singles first and then pairs, fish and chains, and rate the puzzle by the hardest technique it needs.

Failure modes

• No validation of givens. Contradictory inputs produce nonsense or hang.
• First-empty-cell order. Correct but can be orders of magnitude slower than MRV on hard puzzles.
• Copying the grid at each node. Allocation dominates; use in-place updates with undo.
• Forgetting to undo on every path. An early return that skips the undo corrupts sibling branches. In the code above the only early return is on success, when state no longer matters.
• Stopping at one solution when checking a puzzle. Reports ambiguous puzzles as valid.
• Judging difficulty by runtime. Measures your solver, not the puzzle.

Where the ideas go next

Everything here transfers. Bitmask state with undo is the pattern in permutation and combination generators; dead-end bounds are the core of subset sum with pruning; and grid search with in-place marking appears in word search on a grid. For larger constraint problems, the same instincts point to SAT and constraint-programming solvers, which add learning from failures on top of propagation and smart branching.

What to do next

1. Write the naive solver, then switch to bitmask state and measure the speed-up on one hard puzzle.
2. Add MRV and a node counter; compare node counts before and after.
3. Add hidden singles and measure both nodes and wall time, to see the propagation trade-off yourself.
4. Implement Algorithm X with the 324 by 729 cover and check it agrees with your bitmask solver.
5. Add limit=2 uniqueness checking and build the generator; confirm every output has one solution.
6. Reread the backtracking deep dive and apply the same choices to N-Queens or graph colouring.