Introduction

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.

Paint the Picture

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">The numbers are run-length clues: each row and column lists the lengths of its filled blocks, in order, with a gap between blocks. Click cells to fill them so that <b>every</b> clue matches. Checking is instant — finding a solution is the hard part.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Click cells to paint, then check.</div>
<div class="btns">
  <button id="check" type="button">Check picture</button>
  <button id="solve" type="button">Solve it</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Nonogram "consistency": given row + column run-length clues, is there a way to fill the grid so every line's blocks match its clue? Checking one grid is a quick scan; finding one in general is NP-complete (Ueda & Nagao, 1996) — brute force here tries 2^(N*N) grids.
const N = 5;
// Clues for the hidden picture (a small "plus / cross" shape).
const ROW = [[1],[1],[5],[1],[1]];
const COL = [[1],[1],[5],[1],[1]];

let cells = Array.from({length:N},()=>Array(N).fill(0));

// Run-lengths of filled blocks in a 0/1 line.
function runs(line){
  const out=[]; let c=0;
  for(const v of line){ if(v){c++;} else if(c){out.push(c);c=0;} }
  if(c) out.push(c);
  return out;
}
const eq = (a,b)=> a.length===b.length && a.every((x,i)=>x===b[i]);
// Empty line: no filled cells -> empty clue [].
function lineOK(line,clue){
  const r=runs(line);
  const cl=(clue.length===1&&clue[0]===0)?[]:clue;
  return eq(r,cl);
}
function gridValid(g){
  for(let r=0;r<N;r++) if(!lineOK(g[r],ROW[r])) return false;
  for(let c=0;c<N;c++) if(!lineOK(g.map(row=>row[c]),COL[c])) return false;
  return true;
}

function render(){
  const grid=document.getElementById('grid');
  grid.style.gridTemplateColumns = '60px repeat('+N+', 40px)';
  grid.innerHTML='';
  // top-left corner
  const corner=document.createElement('div'); corner.className='corner'; grid.appendChild(corner);
  // column clues
  for(let c=0;c<N;c++){ const d=document.createElement('div'); d.className='colclue';
    d.innerHTML=COL[c].join('<br>'); grid.appendChild(d); }
  // rows
  for(let r=0;r<N;r++){
    const rc=document.createElement('div'); rc.className='rowclue';
    rc.textContent=ROW[r].join(' '); grid.appendChild(rc);
    for(let c=0;c<N;c++){
      const cell=document.createElement('div');
      cell.className='cell'+(cells[r][c]?' on':'');
      cell.addEventListener('click',()=>{ cells[r][c]=cells[r][c]?0:1; render();
        setStatus('Click cells to paint, then check.',''); });
      grid.appendChild(cell);
    }
  }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function check(){
  if(gridValid(cells)) setStatus('✓ Every row and column clue matches — solved!','ok');
  else setStatus('✗ Some line does not match its clue. Keep deducing.','bad');
}
// Brute force: try all 2^(N*N) fillings until one satisfies every clue.
function solve(){
  const total=N*N, limit=1<<total; let steps=0, found=null;
  for(let mask=0; mask<limit; mask++){ steps++;
    const g=Array.from({length:N},()=>Array(N).fill(0));
    for(let i=0;i<total;i++) if(mask&(1<<i)) g[(i/N)|0][i%N]=1;
    if(gridValid(g)){ found=g; break; }
  }
  if(found){ cells=found; render();
    setStatus(fmt('Found a solution after checking %steps% grids.', { steps: steps.toLocaleString() }),'ok');
    console.log('Solved after',steps,'of',limit,'grids');
  } else setStatus('No grid satisfies these clues.','bad');
}
document.getElementById('check').addEventListener('click',check);
document.getElementById('solve').addEventListener('click',solve);
document.getElementById('reset').addEventListener('click',()=>{ cells=Array.from({length:N},()=>Array(N).fill(0)); render(); setStatus('Click cells to paint, then check.',''); });
render();
Result
Console

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 2252^{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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/nonogram/Content licensed under CC BY-NC 4.0.