Ben-Gurion Researchers Crack Polygonal Puzzles That Square Jigsaws Could Never Solve
Researchers formalize a new class of jigsaw puzzles cut by arbitrary straight lines, then solve them using physics simulation and loop constraints.
Takeaways
- New puzzle class defined: crossing cuts polygonal puzzles, inspired by the Lazy Caterer's sequence.
- Solver abstracts pieces as a multi-body spring-mass system solved with Box2D.
- Hierarchical loop constraints progressively build consensus from 4-piece junctions upward.
- Pictorial ranking uses Telea inpainting plus Stable Diffusion to extrapolate piece content across noisy boundaries.
- Five open datasets released at icvl.cs.bgu.ac.il/polygonal-puzzle-solving, spanning apictorial and pictorial variants.
- Closed-form theory: expected pieces grow as a^2/6, and only 1 in 3 random cut pairs intersect.
Two decades of computational jigsaw puzzle research have been dominated by one flavor: identical square pieces stitched back into a rectangular image. That constraint made the problem tractable but stripped it of most real-world relevance. A team from Ben-Gurion University has introduced a puzzle class that sits between toy squares and fully unrestricted fragments, along with open datasets, evaluation metrics, and a working solver.
Their paper, published in the International Journal of Computer Vision, defines crossing cuts polygonal puzzles: convex polygons sliced by an arbitrary number of straight lines, producing convex polygonal pieces of varying shapes and sizes. The generation model draws on the Lazy Caterer's sequence, the classic combinatorics problem about the maximum number of pie slices you can get from N straight cuts.
Why square puzzles were a dead end
Puzzle solving was proved NP-complete decades after Freeman and Garder's seminal 1964 paper, pushing the literature toward heuristics that cannot guarantee optimal solutions in tractable time but still work well in practice. The field then split into three disconnected tracks, none of which map cleanly onto real applications.

The authors point out an awkward truth: most Square Jigsaw studies cite archaeology as a possible application, yet archaeological puzzles are virtually never square, and there is essentially one case in the computational archaeology literature where Square Jigsaw solvers might apply. Unrestricted puzzles, meanwhile, are so loosely defined that you cannot prove anything statistical about them, such as the expected number of pieces or the worst-case count of false-positive matches.
Crossing cuts puzzles thread the needle. They stay constrained enough to permit rigorous probabilistic analysis, while allowing pieces to have any number of edges, any size, and any orientation, unlike the uniform grid of a square jigsaw.