How these puzzles are made

Difficulty has to be measured, not asserted. Here is what we measure on the Sudoku, Sokoban, Kakuro and Nonogram puzzles, and the puzzles it made us throw away.

A generated puzzle can be hard to solve and still be a bad puzzle. It can also be labelled "Expert" and fall apart in ninety seconds. Calling a deal hard costs nothing, so the label carries no information unless something independent checks it.

So each of these four games has a yardstick that is computed, not chosen, and a puzzle that misses the bar is discarded and regenerated. The measurements below are the actual gates in the code, with the numbers they produced.

Sudoku: the word "Expert" was doing no work

Sudoku difficulty is usually sold by clue count, and clue count is close to meaningless. Most of a Sudoku falls to two techniques that beginners learn in their first week: a naked single, where a cell has only one candidate left, and a hidden single, where a digit has only one place left in a row, column or box. If a deal can be finished with nothing but those two, it is an easy puzzle no matter how few clues it started with.

We wrote a solver that uses only those two techniques and then stops, and pointed it at the existing Expert deals.

Eight of twelve. The label was a lie, and the clue count was hiding it.

The fix is a gate rather than a tweak. singlesResidue runs the singles-only solver and counts the cells it cannot reach. Hard must leave at least 8 such cells and Expert at least 20, and a deal that fails is dealt again until one passes. Measured after the change: Easy still falls to singles 10 times out of 10 and Medium 8 times out of 10, which is exactly what those labels should mean, while Hard and Expert now fall 0 times out of 10.

Sokoban: search size measures grind, not difficulty

The obvious way to rate a Sokoban level is to solve it optimally and report how much search that took. Our previous levels scored well on that measure. Crossroads needed 300,000 search states and Gridlock 2.3 million.

They were still boring, and it is worth being precise about why. A level can force an enormous search while asking the player to do almost nothing interesting, because most of the work is walking the character around an open room rather than working out where the crates have to go.

So we measure detour instead:

detour = optimal pushes - sum over crates of straight-line distance to nearest goal

A detour of zero means every crate went straight home and the level had no idea in it. A high detour means the solution requires pushing crates away from where they are going, which is the thing that makes Sokoban a puzzle.

The old ramp had detours of 3 to 11 on levels of 15 to 60 pushes. Impressive search numbers, very little puzzle. What settled the argument: seven candidate levels that later blew the generator's state limit, so they were enormous searches, had detours of 0 to 4.

Building levels backwards

Generating a Sokoban level forwards and then checking whether it is solvable wastes almost all of its time on levels that are not. So the generator plays in reverse. Crates start on the goals and get pulled apart at random, which means every candidate it produces is solvable by construction, because the sequence that built it run backwards is a solution.

Each candidate is then solved optimally, filtered on detour and push count, and ranked by detour, search breadth and compactness. About 130,000 candidates produced the eight levels that shipped, alongside four hand-made tutorials.

The shipped set is Nook, The neck, Long way round, Two floors, Scatter, In the way, Musical chairs and The pillar. Musical chairs starts three of its five crates already sitting on goals, all of which have to move anyway.

Kakuro: a big random board is almost never a puzzle

Kakuro puzzles must have exactly one solution. Fill a large board at random and it will have many, so the obvious generator does not scale: every attempt at a 9x9 or 11x11 fails the uniqueness check and you never finish.

So the larger boards are grown rather than dealt. A finished 7x7 core is extended one domino or one 2x2 block at a time, and the whole board is re-proved unique after every single addition. A step that breaks uniqueness is discarded and another is tried. The board is therefore a valid puzzle at every moment of its construction, which is what makes the time budget below safe.

Two changes made this fast enough to run in a browser. The solver's candidate test was replaced with the exact digit-combination masks already tabulated in COMBOS, which prunes harder and allocates nothing, worth a factor of ten on an 11x11. And growth is biased outward until the white cells span the board, because an unbiased random walk huddles around wherever the core landed and leaves most of the grid black.

Those are Node timings and Chrome runs about twice as slow, which is why the page shows "Building puzzle" and defers the build so that message actually paints. A 2.5 second wall budget bounds the worst case, and because uniqueness is re-proved at every step, whatever has grown when the budget runs out is still a valid puzzle rather than a broken one.

Nonogram: stopped by thumbs, not by the generator

Nonogram sizes are 5x5, 10x10 and 15x15. A 20x20 also generates instantly, so the ceiling is not a performance limit. It is that 20 columns works out to roughly 14 pixel cells on a phone, and most people here are on a phone. The constraint was the screen.

Checking the checker

All of the above trusts a solver, so the solver has to be tested against something that is not itself. Every optimal Sokoban solution is replayed through the game's own keyboard handler in a real browser, and the level has to report itself solved in exactly the move count the solver predicted. That checks the game's rules and the solver's model against each other, and a disagreement means one of them is wrong.

The same set is re-proved on every deploy. Moving the solver to the combination masks brought that gate from 80 seconds down to 3.

If you find a puzzle that does not deserve its label, that is a bug worth hearing about, and the measurement above is the thing to argue with. Email games@yourfacewhen.org.