How the Sudoku on This Site Makes Its Puzzles: A Bitmask Solver in TypeScript

A Sudoku puzzle is only fair if it has exactly one solution. With more than one solution the player is forced to guess at some point; with none, the puzzle can’t be finished at all. So a generator has two jobs: produce a random valid grid, then remove as many digits as possible without ever allowing a second solution.

The first version of my Sudoku did this by brute force and could take seconds, sometimes more than a minute, to produce a puzzle. The rebuilt one, in TypeScript, generates every puzzle in the browser in well under a tenth of a second. This is how it works.

Candidates as bits

The grid is an array of 81 numbers, in row order, with 0 for an empty cell. Row, column and box of each cell are precomputed once, so the hot loops never divide by 9.

The trick that makes everything fast is keeping, for every row, column and box, a 9-bit mask of the digits already used. Bit n set means digit n is taken. The candidates of a cell are then just the digits missing from all three of its units:

/** Bit mask of digits 1–9 (bit n set = digit n). */
export const ALL_DIGITS = 0b11_1111_1110;

const mask = ALL_DIGITS & ~(rows[ROW[i]] | cols[COL[i]] | boxes[BOX[i]]);

Placing a digit is an OR into three masks, and removing it is an AND with the complement. Counting candidates is a lookup in a 1,024-entry table of bit counts. Candidates never live in arrays or sets: only the cell the search branches on gets its digits listed.

A solver that picks the most constrained cell first

The solver is a classic backtracking search with one important rule: at each step, branch on the empty cell with the fewest candidates. A cell with one candidate is forced, so it costs nothing to fill. A cell with zero candidates means the current path is dead, and the search can back out immediately.

const search = (): boolean => {
  // Find the empty cell with the fewest candidates.
  let best = -1, bestMask = 0, bestCount = 10;
  for (let i = 0; i < CELLS; i++) {
    if (grid[i]) continue;
    const mask = ALL_DIGITS & ~(rows[ROW[i]] | cols[COL[i]] | boxes[BOX[i]]);
    const count = popcount(mask);
    if (count < bestCount) {
      best = i; bestMask = mask; bestCount = count;
      if (count <= 1) break;
    }
  }

  if (best === -1) {           // no empty cell left: a solution
    solutions++;
    solution ??= grid.slice();
    return solutions >= limit; // stop once we've seen enough
  }
  if (bestCount === 0) return false;

  for (const digit of digitsOf(bestMask)) {
    place(best, digit);   // set the cell and the three masks
    if (search()) return true;
    unplace(best, digit); // and undo it
  }
  return false;
};

(Slightly condensed: in the real code, place and unplace are inlined bit operations, and the digits are shuffled when an rng is passed.)

The limit is what turns a solver into a uniqueness checker. With limit: 2, the search stops as soon as it finds a second solution. When the puzzle is unique, it still has to explore every branch to prove there’s no second one, but thanks to the most-constrained-first rule that’s only about twice the cost of a plain solve here:

export const hasUniqueSolution = (puzzle: Grid): boolean =>
  solve(puzzle, { limit: 2 }).solutions === 1;

A random, reproducible full grid

To get a random complete grid, the generator runs the same solver on an empty grid and shuffles each cell’s candidates before trying them. The shuffle uses a small seeded generator (mulberry32) rather than Math.random, so the same seed always produces the same puzzle. That makes bugs reproducible, tests deterministic, and a “puzzle of the day” trivial to add.

Filling an empty grid takes about 0.2 ms with the most-constrained-first rule.

Removing clues, two at a time

Then comes the part that makes it a puzzle. The generator visits the cells in random order and tries to remove each clue together with its mirror, the cell rotated 180° around the centre (i and 80 − i). Printed puzzles have that symmetry, and it looks better than random holes. A removal is only kept if the puzzle still has a unique solution:

const tryRemove = (cells: number[]): void => {
  const saved = cells.map((i) => puzzle[i]);
  for (const i of cells) puzzle[i] = 0;
  if (hasUniqueSolution(puzzle) && (!singlesOnly || solvableWithSingles(puzzle))) {
    clues -= cells.length;
  } else {
    cells.forEach((i, k) => (puzzle[i] = saved[k])); // put them back
  }
};

It stops at a target number of clues (40 for easy, 32 for medium, 26 for hard) or when no more clues can be removed. Most removals take a pair, so a puzzle can end one below the target, and occasionally one ends a little above it.

Hard puzzles get one more pass: when the symmetric pairs run out before 26 clues, the generator goes through the remaining clues one at a time, keeping each removal that leaves a unique solution. That pass is what brings hard puzzles to about 26 clues on average (pairs alone stop at about 27.6), at a cost: most hard puzzles aren’t symmetric.

Difficulty is about technique, not only clues

Fewer clues usually means a harder puzzle, but not always. What really makes a puzzle hard is which techniques you need to solve it without guessing. The generator grades puzzles with the two techniques every player knows:

• Naked single: a cell with only one possible digit.
• Hidden single: a digit that fits in only one cell of a row, column or box.

solvableWithSingles applies both repeatedly, the way a person would. Easy and medium puzzles must be solvable that way from start to finish, which is the singlesOnly check in tryRemove above. Hard puzzles skip it, so they can require more advanced techniques.

Measuring the result was humbling. Over 300 generated puzzles per level (seeds 0 to 299, in Node on my laptop; times vary with the device):

About half of the “hard” puzzles still fall to singles alone. They’re hard in the sense of having few clues, but not in the techniques they demand. The next step is a grader that knows more techniques, such as naked pairs, pointing pairs and X-wings, and requires at least one of them for “hard”.

Medium is the slowest level to generate: like easy, it runs the singles check on every removal, but it removes more clues. That’s still fast enough to generate on the main thread without a Web Worker.

Testing something random

Random output doesn’t mean untestable output. The Vitest suite generates puzzles for several fixed seeds at every level and checks properties, not exact grids:

• the solution is a valid Sudoku, and every clue agrees with it;
• the puzzle has exactly one solution, and solving it gives back that solution;
• easier levels have more clues;
• the same seed produces the same puzzle, and different seeds produce different ones;
• generating ten hard puzzles takes less than a quarter of a second each, on average.

The last test is there to catch a regression back to seconds-long generation before any player does.

You can play the result here. It saves your game as you go and works offline.