Jigsaw Puzzles

A thousand-piece jigsaw puzzle is the picture of a calm afternoon: dump the box, sort the edges, and slowly fit shape to shape until the image appears. The picture on the lid is your guide, and that guide is doing far more work than it seems.

Strip the picture away. Imagine the pieces are plain squares, each side painted a color, and the only rule is that touching edges must match. No image, no corner tabs, no hints — just colors that have to line up. Now where does each piece go?

That harmless-looking question is the same kind of question that separates the easy problems from the hardest ones in all of computer science. When the picture disappears, the calm afternoon turns into a brutal search.

Below is a 3×3 frame and nine square pieces. Each edge carries a color, and a placement is valid only when every shared border has matching colors. Click a piece, then click an empty cell to drop it in. Get all nine to agree and you've solved it.

<p class="hint">{{hint}}</p>
<div class="wrap">
  <div>
    <div class="label">{{label_board}}</div>
    <div id="board" class="board"></div>
  </div>
  <div>
    <div class="label">{{label_tray}}</div>
    <div id="tray" class="tray"></div>
  </div>
</div>
<div class="status" id="status">{{status_init}}</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_reset}}</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; }
.wrap { display: flex; gap: 1.4rem; flex-wrap: wrap; align-items: flex-start; }
.label { font-size: .8rem; font-weight: 700; color: #1d3557; margin-bottom: .35rem; }
.board { display: grid; grid-template-columns: repeat(3, 56px); grid-template-rows: repeat(3, 56px); gap: 3px; }
.tray { display: grid; grid-template-columns: repeat(3, 48px); gap: 6px; }
.cell { width: 56px; height: 56px; position: relative; background: #eef2f6; border: 1px dashed #b8c4d0; border-radius: 6px; }
.cell.target { outline: 2px solid #1d3557; outline-offset: -2px; }
.piece { position: relative; border-radius: 6px; cursor: pointer; }
.cell .piece { width: 56px; height: 56px; }
.tray .piece { width: 48px; height: 48px; box-shadow: 0 1px 3px rgba(0,0,0,.18); }
.tray .piece.sel { outline: 3px solid #1d3557; }
.tray .piece.placed { opacity: .18; pointer-events: none; }
.edge { position: absolute; }
.bad { box-shadow: 0 0 0 3px #c92f3c inset; }
.status { font-size: 1rem; font-weight: 600; margin: .7rem 0 .5rem; 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 board is effortless: walk the shared borders and confirm the colors agree. Finding an arrangement that satisfies every border at once is the hard part — press Auto-solve and the computer runs a backtracking search, placing a piece, checking it fits, and undoing the move when it hits a dead end. Watch the move counter climb: even nine pieces can force thousands of attempts.

How hard is a jigsaw puzzle, really? Not the relaxing version with a picture — the bare-bones one where pieces are squares and only the edge colors matter.

• Checking a finished arrangement is trivial: scan every shared border and confirm the colors match.
• Brute force tries every way to place and rotate the pieces — for n pieces that is roughly n! arrangements times 4 rotations each, hopeless past a couple dozen pieces.
• It's NP-complete. In 2007 Erik Demaine and Martin Demaine proved that deciding whether a set of square "edge-matching" pieces can tile a frame so all touching edges agree is NP-complete. The colors act like wires and constraints, letting any logic problem be encoded as a pile of pieces — the same trick behind reductions from SAT.
• So even asking "can these pieces fit together at all?" belongs to the whole NP-complete family, right next to thousands of other notoriously hard problems.

That is the punchline: the moment the picture on the lid is gone and only the edges guide you, the puzzle is a genuine instance of the same difficulty behind P vs NP. The picture is not decoration — it is the hint that quietly tames an intractable problem.

"Fit these pieces together so every boundary agrees" is a shape that real problems take all the time, and the jigsaw is its friendly face:

• Reconstruction: reassembling shredded documents, torn manuscripts, or broken pottery is literally an edge-matching jigsaw with no picture on the lid.
• Genome assembly: stitching short DNA reads into a full sequence is matching overlapping fragments — close kin to genome assembly.
• Tiling and packing: laying out tiles, fabric, or circuit blocks so neighbors are compatible is the same satisfy-every-border puzzle.
• Teaching complexity: because everyone has done a jigsaw, it is one of the clearest on-ramps to what NP-completeness means.

Learn why jigsaw puzzles are hard and you've met constraint satisfaction — the engine under SAT and countless matching and packing problems.

A jigsaw puzzle hides a beautiful secret: take away the picture, keep only the edges, and you are left with an NP-complete problem (Demaine & Demaine, 2007). Checking a finished board stays instant; deciding whether the pieces can fit together at all is as hard as anything in computer science.

So the next time you spend an afternoon hunting for the one piece that fits, take comfort — you are not slow. You are wrestling with P vs NP hiding inside a cardboard box, and without the picture to guide you, there may be no clever shortcut at all.