Many real-life challenges can be abstracted as jigsaw puzzles – the construction of a coherent whole from a set of unordered visual fragments. Applications range from archeology and biology, through security and forensics, to direct image editing and many more and for this reason jigsaw puzzle problems have intrigued computer scientists since the 1960’s, The field, however, evolved to cover various variations of the problem, and curiously, most of the literature in the last two decades (2000-2020) has focused on less realistic and more limited puzzles whose pieces are identical squares. We too have worked in this area and were even proud to suggest the first-ever fully automatic square Jigsaw puzzle solver that provided a leap in the scale of solvable puzzles). But at the same time it was clear that this type of abstraction is extremely limited in its potential applications to real-life problems. Consequently, we started to explore polygonal jigsaw puzzles, using formal generation models that are also allow rigorous analysis.
The Crossing Cuts Puzzle model is a puzzle generation model inspired by (but nevertheless different than) the Lazy Caterer sequence. Taking a general convex polygon, one obtains a Crossing Cut puzzle by cutting through it with multiple straight cuts of arbitrary positions and directions. Unlike the Lazy Caterer sequence, the cuts in Crossing Cuts puzzles are completely random without trying to maximize the number of pieces, a property that entails numerous compelling stochastic properties, including on the number of pieces. To make the story even more interesting, we allow the pieces to erode, a particular geometrical noise that is inspired from real life applications (in particular, in archeology).
Crossing Cuts puts puzzles can be apictorial, but they can also be pictorial once the original convex polygon is covered with an image before the cuts are applied. The following illustrates one puzzle of each type.
Apictorial Polygonal Puzzle Pictorial Polygonal Puzzle
Bag of pieces Ground Truth Solution Bag of Pieces Ground Truth Solution
As mentioned above, Crossing cuts puzzles have plenty of interesting properties that you will find in the papers. One of their important properties is that once geometrical noise is introduced to the fragments, they are extremely difficult to solve. The problem is intractable and the challenge include not only how pieces are paired, but also how they are re-positioned in the workspace to reconstruct the puzzle. To cope with such difficulties and obtain tractable solutions, we abstract the problem as a physical mechanical system (as demonstrated below) endowed with hierarchical loop constraints and a layered reconstruction process. The result is a fully automatic solver that can also use pictorial information to solve pictorial puzzles, a capacity of progressively growing importance the more geometrical noise is introduced.
We also introduce several evaluations measures that quantify both overall success rate but also the spatial quality of solutions, and part of our contribution are several databases of puzzles that can also be used for benchmarking of future algorithms.
Following are several demos and visualizations, as well as the paper, code, and puzzle datasets.
Demos
A complete reconstruction process of a 400 pieces apictorial crossing cuts puzzle.
A fast reconstruction of a 18 pieces pictorial crossing cuts puzzle
Code (Python 
)
The code is free to use for academic purposes Under the GNU Licence terms, and with proper citation to the paper shown on this page. You can download it here.
You can view and download our puzzle datasets from this portal, in which they are separated into 5 different databases:
- DB1: Apictorial puzzles with a circular shape for measurement of statistical properties (220 puzzles).
- DB2: General apictorial puzzles for solvers evaluation (15 puzzles).
- DB3: Perturbed square pictorial puzzles (40 puzzles).
- DB4: General pictorial puzzles (62 puzzles).
- DB5: Square pictorial puzzles (181 puzzles).
Underlying the datasets is a procedure for selecting a random global shape and the random cuts. The former is based on the convex hull of a set of random sample points and the cuts are selected by pairs random points in the interior of this convex hull.
An example of one apictorial synthesized polygonal puzzle (30 cuts, 200 pieces) is shown in this figure. On the left are the random points and their convex hull, in the middle column are the cuts and the ground truth solution, and on the right are the pieces after randomly scrambling them both in position and orientation, or what we call the bag of pieces. This bag is also the riddle to be solved, and thus the input provided to potential solvers. If the puzzle is intended to be pictorial, the global polygon is covered with a random image selected from a public domain repository.
Here are selected examples from the different DBs. More detailed depiction is in the DBs portal.
Real-Life Puzzle Pieces
Crossing Cuts puzzles can also be real, not only synthesized in the computer. To cope with these we first need to produce a proper digital representation of its pieces with minimal loss of relevant information. Acquired with a digital camera, a vectorial vectorial representation is generated by properly fitting boundary segments to lines, allowing subpixel accuracy in the digital pieces and facilitating solutions by the same solver mentioned above. Credit goes to Roy Hershfinkel who developed the acquisition process for his research project and the following is a photograph os the pieces on the left next to the puzzle solution on the right.