Nonogram (Picross)

You have probably met a nonogram under one of its many names — Picross, Griddler, Hanjie, Paint by Numbers. The idea is irresistible: a blank grid, a list of numbers along each row and column, and a hidden picture that emerges as you fill in squares.

The numbers are run-length clues. A row labelled 2 1 means: somewhere in that row there is a block of exactly two filled cells, then a gap, then a block of exactly one filled cell — in that order. Get every row and every column to agree, and the picture appears.

It feels like quiet, meditative logic. But hidden in that grid of clues is a question that the smartest algorithms in the world cannot answer quickly: does this puzzle even have a solution? That little question lands squarely among the hardest problems we know.

Here is a small 5×5 nonogram. The numbers above each column and beside each row are run-length clues: they list the lengths of the filled blocks, in order, with at least one empty cell between blocks. Click the cells to fill them until every clue is satisfied.

<p class="hint">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.grid { display: inline-grid; gap: 3px; margin: .4rem 0; }
.corner { width: 100%; height: 100%; }
.colclue, .rowclue { display: flex; align-items: flex-end; justify-content: center;
        font: 700 12px ui-monospace, monospace; color: #1d3557; padding: 2px;
        line-height: 1.15; text-align: center; min-width: 40px; min-height: 28px; }
.rowclue { align-items: center; justify-content: flex-end; padding-right: 6px; }
.cell { width: 40px; height: 40px; border-radius: 6px; background: #d7dde3;
        border: 1px solid #b9c2cb; cursor: pointer; transition: background .08s; }
.cell:hover { background: #c6cdd4; }
.cell.on { background: #1d3557; border-color: #14233b; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Checking a finished grid is effortless: read each row and column, list its blocks, compare to the clue. Finding a grid that satisfies all the clues at once is the hard part — press Solve it and the computer simply tries every way to fill the grid. A 5×5 grid has $2^{25}$ ≈ 33 million possibilities; every extra row roughly multiplies the count by 32. This is the same easy-to-check, hard-to-solve tension at the heart of P vs NP.

How hard is a nonogram, really? Not the colouring — the deciding.

• Checking a candidate grid is trivial: list the blocks in each line and compare them to the clues. This runs in time proportional to the size of the grid.
• One line in isolation is easy. Given just one row's clue, you can decide what fits it in polynomial time. This is why human-friendly puzzles are "line solvable" — they never force a guess.
• The whole puzzle is NP-complete. In 1996, Nobuhisa Ueda and Tadaaki Nagao proved that deciding whether a general nonogram has any solution is NP-complete, by a reduction from 3-SAT. The rows and columns can be wired so that satisfying all the clues is equivalent to satisfying a Boolean formula.
• And it can have many solutions. Counting how many solutions a nonogram has is even harder — it is #P-complete.

That is the punchline: the moment a nonogram stops being "line solvable" and forces a genuine guess, you are looking at an instance of the same intractable family behind SAT and graph coloring. The picture is friendly; the question underneath is not.

"Reconstruct a pattern from a handful of summary counts" is a shape that shows up far beyond the puzzle page, and the nonogram is its playful face:

• Discrete tomography: reconstructing an object from the number of solid points along each scan line is, mathematically, a nonogram-like problem — relevant to medical and industrial imaging.
• Constraint satisfaction and SAT solving: because nonograms reduce to 3-SAT, real puzzle solvers lean on the same engines that attack scheduling, routing and verification.
• Puzzle design and testing: generating a good nonogram means guaranteeing a unique, line-solvable solution — itself a hard search problem.
• Teaching complexity: nonograms are a vivid way to show that "easy to check" and "easy to solve" are not the same thing.

Learn why nonograms are hard and you have met constraint satisfaction — the engine under SAT and countless reconstruction and scheduling problems.

A nonogram hides a beautiful secret: the same numbers that guide your pencil into a tidy little picture can be wired into a Boolean formula, and through it into any problem in NP. Checking a finished grid stays instant; deciding whether the clues are even solvable is as hard as anything in computer science.

So the next time a Picross puzzle leaves you stuck, unable to place a single sure cell, take comfort — you have not lost your touch. You have simply bumped into P vs NP wearing a coat of pixel art, and there may be no clever shortcut around the guess.