Computational Jigsaw Puzzle Solving

Welcome
Solving a 10,000 parts puzzle

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

Download

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

Puzzle Data Sets

Selected Demos (Higher quality than YouTube)

Papers

Talk
  This work was presented at the 2011 Israel Computer Vision Day  
 
 
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.
 
 
 
Credits

Who and Where…

This research is a joint work by Dolev PomeranzMichal Shemesh and Ohad Ben-Shahar of the Computer Science DepartmentBen-Gurion University of The NegevBeer ShevaIsrael It was published in the Proceedings of the IEEE conference on Computer Vision and Pattern Recognition (CVPR), 2011, and was also presented in the 2011 Israel Computer Vision Day, and the Israel Machine Vision Conference (IMVC) 2012.

 

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.