Introduction

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.

Assemble the Pieces

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">Each square piece has four colored edges. A placement is valid only when <b>every shared border has matching colors</b>. Click a piece in the tray, then click an empty cell to drop it in. Checking a board is instant — finding a layout that fits is the hard part.</p>
<div class="wrap">
  <div>
    <div class="label">Frame (3 × 3)</div>
    <div id="board" class="board"></div>
  </div>
  <div>
    <div class="label">Pieces</div>
    <div id="tray" class="tray"></div>
  </div>
</div>
<div class="status" id="status">Pick a piece, then a cell.</div>
<div class="btns">
  <button id="check" type="button">Check borders</button>
  <button id="solve" type="button">Auto-solve</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Edge-matching jigsaw "assembly": given square pieces whose only signal is their four edge colors, place them in a 3x3 frame so every shared border matches. Checking one arrangement is a quick scan of the borders; finding one in general is NP-complete (Demaine & Demaine, 2007). Auto-solve runs a backtracking search.
const N = 3;
// Internal border colors that define the intended solution (1,2,3 are colors; 0 = outer).
const V = [[1,2],[2,1],[3,2]];        // vertical borders, V[row][k] between col k and k+1
const H = [[2,1,3],[3,2,1]];          // horizontal borders, H[k][col] between row k and k+1
const B = 0;                          // outer-frame color
const PALETTE = ['#cdd9e3','#e63946','#2a9d8f','#e9c46a']; // index by color id

function buildSolution(){
  const g=[];
  for(let r=0;r<N;r++){ const row=[];
    for(let c=0;c<N;c++){
      const t = r===0 ? B : H[r-1][c];
      const b = r===N-1 ? B : H[r][c];
      const l = c===0 ? B : V[r][c-1];
      const rr = c===N-1 ? B : V[r][c];
      row.push({t, r:rr, b, l});
    } g.push(row); }
  return g;
}
const SOL = buildSolution();
// Pieces: one per solution cell, given stable ids, then shuffled for the tray.
const PIECES = [];
for(let r=0;r<N;r++)for(let c=0;c<N;c++) PIECES.push({id:PIECES.length, ...SOL[r][c]});
const tray = PIECES.slice();
// deterministic shuffle so the puzzle is the same each load
let seed=20251212;
const rng=()=>{ seed=(seed*1103515245+12345)&0x7fffffff; return seed/0x7fffffff; };
for(let i=tray.length-1;i>0;i--){ const j=Math.floor(rng()*(i+1)); [tray[i],tray[j]]=[tray[j],tray[i]]; }

const board = new Array(N*N).fill(null); // board[pos] = piece object or null
let selected = null;

function pieceEl(p, size){
  const d=document.createElement('div'); d.className='piece';
  const w=size, h=size, th=Math.round(size*0.18);
  const mk=(css)=>{ const e=document.createElement('div'); e.className='edge'; e.style.cssText=css; return e; };
  // top
  d.appendChild(mk(`top:0;left:0;width:${w}px;height:${th}px;background:${PALETTE[p.t]}`));
  // bottom
  d.appendChild(mk(`bottom:0;left:0;width:${w}px;height:${th}px;background:${PALETTE[p.b]}`));
  // left
  d.appendChild(mk(`top:0;left:0;width:${th}px;height:${h}px;background:${PALETTE[p.l]}`));
  // right
  d.appendChild(mk(`top:0;right:0;width:${th}px;height:${h}px;background:${PALETTE[p.r]}`));
  // center label
  const ctr=mk(`top:${th}px;left:${th}px;width:${w-2*th}px;height:${h-2*th}px;background:#fff;display:flex;align-items:center;justify-content:center;font:700 12px ui-monospace,monospace;color:#1d3557;border-radius:3px`);
  ctr.textContent=p.id+1;
  d.appendChild(ctr);
  return d;
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }

function render(){
  const b=document.getElementById('board'); b.innerHTML='';
  for(let pos=0;pos<N*N;pos++){
    const cell=document.createElement('div'); cell.className='cell'+(selected!==null&&!board[pos]?' target':'');
    if(board[pos]) cell.appendChild(pieceEl(board[pos],56));
    cell.addEventListener('click',()=>place(pos));
    b.appendChild(cell);
  }
  const t=document.getElementById('tray'); t.innerHTML='';
  tray.forEach(p=>{
    const el=pieceEl(p,48);
    const onBoard=board.some(x=>x&&x.id===p.id);
    if(onBoard) el.classList.add('placed');
    if(selected&&selected.id===p.id) el.classList.add('sel');
    el.addEventListener('click',()=>{ selected=(selected&&selected.id===p.id)?null:p; render(); });
    t.appendChild(el);
  });
}
function place(pos){
  if(board[pos]){ // pick a placed piece back up
    const p=board[pos]; board[pos]=null; selected=p; render(); setStatus(fmt('Picked piece %id%%v% back up.', { id: p.id, v: 1 }),''); return;
  }
  if(!selected){ setStatus('Pick a piece from the tray first.',''); return; }
  board[pos]=selected; selected=null; render();
  check(true);
}
// Valid iff every shared border has matching colors AND all 9 cells are filled.
function borderViolations(){
  const bad=new Set();
  for(let r=0;r<N;r++)for(let c=0;c<N;c++){
    const pos=r*N+c, p=board[pos]; if(!p)continue;
    if(c<N-1){ const q=board[pos+1]; if(q&&p.r!==q.l){ bad.add(pos); bad.add(pos+1); } }
    if(r<N-1){ const q=board[pos+N]; if(q&&p.b!==q.t){ bad.add(pos); bad.add(pos+N); } }
  }
  return bad;
}
function check(quiet){
  const bad=borderViolations();
  // mark
  const cells=document.getElementById('board').children;
  for(let i=0;i<cells.length;i++){ const pc=cells[i].querySelector('.piece'); if(pc) pc.classList.toggle('bad',bad.has(i)); }
  const filled=board.every(x=>x);
  if(bad.size===0&&filled){ setStatus('✓ Every border matches — solved!','ok'); }
  else if(bad.size>0){ setStatus('✗ Some borders clash (highlighted in red).','bad'); }
  else if(!quiet){ setStatus('Borders match so far — keep going.','ok'); }
  else { setStatus(fmt('Placed. %length% / 9 pieces down.', { length: board.filter(Boolean).length }),''); }
}
// Backtracking solver over the tray order, no rotation, fill-order top-left to bottom-right.
function solve(){
  const g=new Array(N*N).fill(null), used=new Array(tray.length).fill(false);
  let moves=0;
  const fits=(pos,p)=>{ const r=Math.floor(pos/N),c=pos%N;
    if(c>0){ const lf=g[pos-1]; if(lf&&lf.r!==p.l) return false; }
    if(r>0){ const up=g[pos-N]; if(up&&up.b!==p.t) return false; }
    return true; };
  function bt(pos){
    if(pos===N*N) return true;
    for(let i=0;i<tray.length;i++){ if(used[i])continue; const p=tray[i]; moves++;
      if(fits(pos,p)){ g[pos]=p; used[i]=true; if(bt(pos+1)) return true; g[pos]=null; used[i]=false; } }
    return false;
  }
  const ok=bt(0);
  if(ok){ for(let i=0;i<N*N;i++) board[i]=g[i]; selected=null; render();
    check(false);
    setStatus(fmt('✓ Solved by backtracking after %moves% placement attempts.', { moves: moves }),'ok');
    console.log('Auto-solve: solved in', moves, 'attempts. Borders ok:', borderViolations().size===0);
  } else setStatus('No arrangement fits these pieces.','bad');
}
document.getElementById('check').addEventListener('click',()=>check(false));
document.getElementById('solve').addEventListener('click',solve);
document.getElementById('reset').addEventListener('click',()=>{ board.fill(null); selected=null; render(); setStatus('Pick a piece, then a cell.',''); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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

Conclusion

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.

Share this article

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

Comments

Loading comments...

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