Computational Jigsaw Puzzle Solving

Welcome

It is quite likely that you, the reader, have tried to solve jigsaw puzzles before. Could computers do the same once given the bag of pieces? This problem has been studied progressively (though sporadically) since the 1960’s, but only recently could algorithms began to handle problems of reasonable size at reasonable success rate. In 2011 we were proud to be the first group to have devised a computational solution which is both fully automatic, requires no manually provided hints, operates on puzzles having thousands of pieces, and does not with near perfect performance. As has become common in the field, we too focus on square pieces, if nothing else then for the elimination of shape cues that sometimes assist us (humans) when we solve such puzzles.

In the page below you will find and download material related to our research, including all the code, papers, image databases, and demos. But as a teaser, here on the right we are proud to present the first ever solution to the latest puzzle ever attempted by an automatic solver to date (July 2011) – no less than 10,000 pieces! A different visualization of this solution is also shown later on.

 

Download Matlab Code (please refer to the Programmer’s Manual for additional documentation and instructions)

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.

Download Puzzle Data Sets

Selected Demos (Higher quality than YouTube)

Papers

Talk

  This work was presented at the 2011 Israel Computer Vision Day  
 
 
 

Inline Demos

While our solver is available for download and experimentation, below you will find several demos covering a range of puzzle sizes and complexity. Each row in the table below shows on the left a visualization of the solution from an initial scrambled state to the final state obtained at the end of the computation, and on the right the actual progression of the solution from the single seed piece till the final state. All demos are available also in YouTube, but you may also download better quality videos in the Download section below.

 

A 432 piece puzzle

 
The solver in action.

A 805 piece puzzle

 
The solver in action.

A 3300 piece puzzle

 
The solver in action.

A 10000 piece puzzle

 
The solver in action.

 

Robotic Solver

  Why stop at puzzles inside the computer? Indeed, physical puzzles present new challenges, especially when it comes to the robust acquisition of
piece appearance in the presence of noise, loosely controlled illumination, and aliasing due to pieces that are not aligned with the camera grid. We’ve made the first step, though, and the video below presents our prototype system.
 
 
 

Acknowledgments

This work was funded in part by the US Air Force European Office of Aerospace Research and Development (grant number FA8655-09-1-3016), the Israel Science Foundation (ISF grant No. 1245/08) and the European Commission in the 7th Framework Programme (CROPS GA no 246252). We also thank the generous support of the Frankel fund, the Paul Ivanier center for Robotics Research and the Zlotowski Center for Neuroscience at Ben-Gurion University.