You have probably seen a Nonogram even if the name means nothing. It is the grid puzzle where numbers sit along the top and down the left, and by filling in the right squares a little picture slowly appears. It goes by Picross, Griddlers, Hanjie and a dozen other names. For Day 25 of GameFromZero I rebuilt one from scratch, and what looks like a gentle colouring activity turned out to be a proper constraint-satisfaction problem wearing a friendly costume.
You can play it here: https://dev48v.infy.uk/game/day25-nonogram.html
The rules are almost embarrassingly simple to state. Every cell is either filled or empty. The numbers beside a row, or above a column, are the lengths of the consecutive runs of filled cells in that line, listed in order, with at least one empty cell between neighbouring runs. A clue of "2 1" means a block of two, then a gap, then a single filled cell. Solve every row and every column at the same time and the hidden picture is complete. In the demo you left-click to fill a cell and right-click to mark one as a definite empty with an x, which sounds like a nicety but is actually half of how you reason your way through.
Under the hood the whole thing rests on one tiny function. The puzzle is stored as a hidden grid of ones and zeros, and a clue is just the run-lengths of a line. You scan the line left to right, count a run of ones, and record its length whenever the run ends; an all-empty line gets the clue "0". Run that same function over every row and you have the row clues, run it over every column and you have the column clues. That is the entire clue system. There is no special case, no separate code for rows versus columns, just one scan pointed in two directions.
Winning is the part people get wrong, and it is worth being careful about. The lazy approach is to compare the player's grid cell-by-cell against the hidden picture. That works, but it is not really the puzzle. The honest win condition is to recompute the run-lengths of the player's own filled cells and check that they match every row clue and every column clue. That is what I did, and it matters because it correctly accepts any arrangement that satisfies the clues, which is the actual definition of a solved Nonogram. It also gives you the live green ticks for free: the same per-line check tells you the moment a row or column is done.
Then there is the question of where puzzles come from, and here the lesson mirrors the one from Lights Out yesterday. Do not try to invent clues directly, because random numbers rarely describe any real grid. Instead start from a picture. Generate or draw a grid of filled and empty cells, compute its clues with the run-length scan, and you instantly have a puzzle that is solvable by construction, because the picture you started from satisfies every clue you just produced. My generator makes a random bitmap and rejects the two degenerate cases of an all-empty and an all-full board. To go further and guarantee a puzzle has exactly one solution, you would run a solver on the clues alone and keep only the pictures it can uniquely recover.
That solver is where the real computer science lives, and I spent most of the UNDERSTAND tab on it. The classic first move is the overlap method: imagine sliding a run as far left as it will go and as far right as it will go, and any cell covered in both extremes must be filled no matter what. A run of eight in a ten-wide line forces six cells immediately, turning an empty line into a foothold with zero guessing. A full line-solver goes further by enumerating every legal placement of the runs that fits what you already know, then keeping only the cells that agree across all of them. You alternate that across rows and down columns, letting each discovery constrain the crossing line, and you sweep until nothing changes. For most published puzzles that pure logic finishes the board. When it stalls, you hypothesise a cell, propagate, and backtrack if it leads to a contradiction, which is exactly the propagate-then-search loop behind Sudoku, scheduling and map colouring. A Nonogram is just an unusually pretty instance of a constraint-satisfaction problem.
The demo has the usual three tabs. LOOK is the playable puzzle with New, Reset and Check buttons and a 5x5 or 10x10 toggle. UNDERSTAND breaks the ideas into ten steps, from the clue model through the overlap trick to the CSP view. BUILD walks you through writing it yourself in about a hundred lines of vanilla JavaScript, no frameworks, no build step. I verified the clue generation and the win check in Node before shipping, and every generate-then-solve round-trip passed.
Tomorrow is Day 26: Match-3, the swap-and-cascade puzzle behind Bejeweled and every mobile game you have ever guiltily played on a train.
Top comments (0)