PUZZLE
The Algorithm You Already Know
How a jigsaw puzzle with my five-year-old led me down an NP-completeness rabbit hole.
I'm on the floor with my daughter. Puzzle pieces everywhere. 25-piece butterfly thing she picked out. And without thinking about it, I run the same routine I've run since I was a kid:
Dump the box. Flip every piece face-up. Find the four corners. Find the edges. Loosely group by color. Freestyle from there.
She's watching me and trying to copy the system. She gets the corners part. She doesn't know why, but she knows those pieces are important. She's five.
Why do I do it in that order? Who taught me that? Did anyone?
I've never read a "how to solve jigsaw puzzles" guide. Nobody sat me down and explained the optimal strategy. I just... converged on it. And so did you. And so did everyone I've ever watched do a puzzle.
So I started researching. And it turns out, the strategy you use to solve a jigsaw puzzle on your living room floor maps almost perfectly to named algorithms from computer science. Algorithms that took decades to formalize. You've been running them since you were a kid.
Every step of the "standard" puzzle strategy has a formal counterpart.
Goldberg et al. (2004) — "A global approach to automatic solution of jigsaw puzzles" coined "highest-confidence-first" search
Each step doesn't just organize pieces — it eliminates possibilities.
Jigsaw puzzles are formally NP-complete. Erik Demaine at MIT proved it. Same complexity class as the Traveling Salesman Problem — problems no known algorithm can solve efficiently as they scale.
If someone hands you a completed puzzle, you can instantly verify it's correct. But finding the solution? As puzzles grow, possible arrangements don't just increase — they explode.
So why can you solve them in an afternoon? Because you're not solving the NP-complete problem. You're solving a much easier version. You cheat — you use the box image, color continuity, shape matching. Information the formal problem definition doesn't include.
You are the heuristic.
Demaine, Demaine (2007) — "Jigsaw Puzzles, Edge Matching, and Polyomino Packing Puzzles are NP-complete" — paper
The history of computational puzzle solving recapitulates the human strategy. Shape-matching to image-matching mirrors "does this piece physically fit?" to "does this look right here?"
Freeman & Gardner (1964) IEEE / Wolfson et al. (1988) Annals of OR / Huroyan et al. (2018) arXiv:1811.03188
Sixty years of research on a problem most people consider a rainy-day activity. Freeman built the first computational solver in 1964. Goldberg formalized "highest-confidence-first" search in 2004. Demaine proved puzzles are NP-complete in 2007.
Not everyone solves them the same way. Some people start with edges. Some start with color clusters. Some work outward from a single anchor. The specific sequence varies a lot.
But the shape of the approach is consistent: reduce constraints, exploit local confidence, subdivide, backtrack when stuck. That structure shows up in the papers, in the solvers, and on the living room floor. It's what happens when a search space is too large to brute-force and you have to find shortcuts.
Fissler et al. (2018) found that puzzles tap visuospatial reasoning, cognitive flexibility, working memory, and processing speed — simultaneously. Not one algorithm. Several, running concurrently, switching based on what's in front of you.
A 25-piece butterfly puzzle is an NP-complete problem. My daughter is on the floor, working out her own heuristics for it.
Demaine, Demaine (2007). "Jigsaw Puzzles, Edge Matching, and Polyomino Packing Puzzles are NP-complete." — PDF
Freeman & Gardner (1964). "Apictorial jigsaw puzzles." IEEE Trans. Electronic Computers.
Wolfson et al. (1988). "Solving jigsaw puzzles by computer." — Springer
Goldberg et al. (2004). "A global approach to automatic solution of jigsaw puzzles." — ScienceDirect
Huroyan et al. (2018). "Solving Jigsaw Puzzles By The Graph Connection Laplacian." — arXiv
Fissler et al. (2018). "Jigsaw Puzzling Taps Multiple Cognitive Abilities." — PMC