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 or had someone teach me a strategy. I arrived at this one by practice, and I've watched other people use similar moves.
So I started researching. Several familiar puzzle moves resemble named ideas from computer science: preprocessing, constraint reduction, grouping, and highest-confidence-first search. The comparison is an analogy, not a claim that a person solving a puzzle is executing those formal algorithms.
Several common puzzle moves have useful counterparts in algorithm design.
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
Computational solvers also moved from shape-only matching toward methods that use image data. That loosely resembles the way people combine physical fit with visual continuity.
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.
Across the examples, the recurring moves are constraint reduction, local confidence, subdivision, and backtracking. The papers formalize particular versions of those ideas; the living-room strategy is a practical resemblance, not the same procedure.
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