A sudoku generator: digging holes, unique solutions, and the bug that froze the page

The puzzles in sudoku are not hard-coded. Every new game builds one in the browser: fill a complete solution, then dig cells out while checking that the puzzle stays unique.

Step one: fill a complete solution

A backtracking search with MRV, minimum remaining values: pick the cell with the fewest candidates, shuffle its candidate order. On an empty grid the first cell has nine candidates, the second eight, and so on. Since any complete assignment is a solution, the greedy path almost never hits a wall, and it finishes in milliseconds.

Step two: dig, keeping uniqueness

Shuffle the 81 cells, then try to remove each one: blank it, count solutions with a solution counter, and restore it if the count exceeds one. The number of holes left behind is the difficulty:

Difficulty	Target holes
Easy	42
Medium	50
Hard	56

Seventeen clues is the theoretical minimum for a unique puzzle, and nobody uses that as a difficulty starting point.

The bug: zero did not mean unlimited, it meant the wrong thing

The counter and the solver share one backtracking function and differ by a single argument. The solver passes zero to mean find one solution; the counter passes two to mean stop at two. The problem was that search read limit <= 0 as no limit:

export function solve(grid, rng) {
  if (conflictSet(grid).length) return null;
  return search(grid, rng, 1).board;
}

// limit 是「数到几个就停」：0 不是「不限」，而是「一个就够」
const cap = limit > 0 ? limit : 1;

So solving an empty grid became enumerating every sudoku solution. There are about 6.7 times 10 to the 21st of those. The new-game button spun forever, stuck on step one and never reaching the digging.

The fix normalises limit <= 0 to one, which also reads better: the semantics of solving are one is enough. Only counting needs a cap.

Why 981 assertions did not catch it

Because none of them solved an empty grid. They all ran on known puzzles, and a known puzzle happens to have exactly one solution, so the difference between enumerating and stopping early was a little slower, not visibly wrong. The assertion that now covers it is the one asserting that generated puzzles solve, that the solution is complete, and that it is unique.

When one parameter carries two meanings, zero, null and unlimited are where infinite loops hide.