Computational Polygonal Puzzle Solving

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.

Demos

A complete reconstruction process of a 400 pieces apictorial crossing cuts puzzle.

A fast reconstruction of an 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.

Puzzle Datasets

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

Going Physical – A Robotic Solver

Why stop at physical pieces that are solved in the computer? Physical puzzles should be solved… physically. We implemented a demo system that seeks to close the loop, from acquisition of physical pieces, solution by our solver, and reconstruction back on the physical pieces using a robotic arm that automatically grabs the pieces, reorient position them, so the reconstructed puzzle is obtained. Credit goes to Idan Bandoil and Nir Barel who implemented this for their research project.

Papers

• P. Harel and O. Ben-Shahar, Pictorial and apictorial polygonal jigsaw puzzles: The lazy caterer model, properties, and solvers, arXiv:2008.07644v2, 2021.
• P. Harel and O. Ben-Shahar, Crossing cuts polygonal puzzles: Models and Solvers, In the Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), June 2021.

Acknowledgments

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No. 964854, the Helmsley Charitable Trust through the ABC Robotics Initiative, and the Frankel Fund of the Computer Science Department at Ben-Gurion University.