DEV Community

SEN LLC
SEN LLC

Posted on

Solving Nonograms with Constraint Propagation — Memoized Placement Intersection, Fixpoint Sweeps, and No-Guessing Puzzles by Construction

#typescript #algorithms #constraintsolving #gamedev

Nonogram (picross), the Japanese picture-logic puzzle, built for the browser with a constraint-propagation line solver inside. Three hinges: (1) the line solver = enumerate and intersect — walk every legal run placement for a row/column with a memoized recursion over (position, clue index); cells filled in every placement are certain, cells empty in every placement are certain. The classic human "overlap" trick falls out automatically. (2) Every new certainty re-queues the crossing line; propagation runs to a fixpoint. (3) All five bundled puzzles are verified line-solvable (no guessing) and verified to reproduce their pixel art exactly — clues are derived from the art, so they can't drift apart. Solver-equipped puzzle #5.

🌐 Live demo: https://sen.ltd/portfolio/nonogram/
📦 GitHub: https://github.com/sen-ltd/nonogram

Nonogram

The line solver: enumerate and intersect

One line with clue [3,1] admits only finitely many run placements consistent
with the already-known cells. The solver walks them with a memoized recursion
over (position, clue index) — O(L·k) subproblems — recording per cell
whether it can be FILLED and whether it can be EMPTY in at least one placement:

if (canFill[j] && !canEmpty[j]) out[j] = FILLED;   // filled in EVERY placement
else if (!canFill[j] && canEmpty[j]) out[j] = EMPTY;
Enter fullscreen mode Exit fullscreen mode

That intersection formalizes every human picross technique. The famous
"overlap" opening — a run of 3 in 5 cells pins the middle — falls out
automatically, and is pinned as a test:

expect(solveLine([U, U, U, U, U], [3])).toEqual([U, U, F, U, U]);
Enter fullscreen mode Exit fullscreen mode

If no placement fits, the line is contradictory and the solver says so — which
is how the UI can tell you "your grid contradicts the clues" instead of
letting you dig deeper into a broken state.

Propagation to a fixpoint

When a line pass determines a cell, the crossing line becomes worth
re-solving. A dirty-queue loop runs line passes until nothing changes — that's
the whole board solver. Puzzles that finish this way are line-solvable: the
class humans solve without bifurcation. The solver also records the order in
which cells were determined, which is exactly what the demo's Solve button
animates — you watch the cat emerge from pure deduction.

No-guessing puzzles, by construction

The five bundled pixel-art puzzles (heart, arrow, house, cup, cat) are original.
The tests demand each one is line-solvable and that the solved grid
reproduces the art exactly:

expect(r.solved, `${def.name} must be line-solvable (no guessing)`).toBe(true);
expect(asBool, `${def.name} must reproduce the art`).toEqual(solution);
Enter fullscreen mode Exit fullscreen mode

Clues are derived from the art (fromPixels), so the art is the single source
of truth — clue/picture drift is structurally impossible. Same philosophy as the
Sokoban entry (#286): ship your levels through your solver.

Takeaway

A nonogram line solver is just enumerate and intersect, and it subsumes
every human technique; fixpoint propagation does the rest. That makes five
solver-equipped puzzles — Sudoku, Lights Out (GF(2)), the 15-puzzle
(parity + IDA*), Sokoban (pull-BFS), and Nonogram (constraint propagation) —
each wearing a different piece of mathematics. Hit Solve in the demo and watch
the cat appear from reasoning alone.

🌐 Live demo: https://sen.ltd/portfolio/nonogram/
📦 GitHub: https://github.com/sen-ltd/nonogram

Top comments (0)