Jigsaw Puzzle Problem? It’s No Problem
John Spilsbury, a British cartographer and engrave, is credited as the inventory of jigsaw puzzles around 1760 which at the time were made by painting a picture on a flat rectangular piece of wood and then cutting it into small pieces with a jigsaw. Since then, many people have spent a countless amount of hours taking a puzzle piece, finding similar pieces, seeing if they fit, and doing this over and over until you have a complete picture. Doing these steps require you to consider things like the shape, size, color, which direction to rotate the piece, and so on. When I found out that it is possible to solve jigsaw puzzles using computer programming, I was amazed to say the least. I then came across the “jigsaw puzzle problem,” which is to be able to have puzzle pieces fit together into one region, with no significant gaps in area or overlapping pieces. The attraction to this problem is due to its possible applications in image processing, pattern recognition, and computer vision such as restoration of archaeological artifacts. Here I’ve decided to describe some of the different ways developers have gone about solving this problem.
Puzzle Types (Gallagher, 2012)
Type 1: Puzzles with only piece location unknown
Type 2: Puzzles with piece location and piece orientation unknown
Type 3: Puzzles with piece location known and unknown orientation
Type 4: Two-sided puzzles of two images of unknown location, orientation, and face — highly representative of real-world applications
Using Genetic Algorithms
A genetic algorithm (GA) is a randomized numerical optimization method. Which means it gives the parameters which optimize a particular function. Genetic algorithms start with several randomly choosen parameters and retain the set of parameters which give a lower loss. Solutions are combined (crossover) and random mutation giving a biological analogy. For more information about GA: https://towardsdatascience.com/introduction-to-optimization-with-genetic-algorithm-2f5001d9964b
Sholomon, David, and Netanyahu (2014) presented a GA based solver that can solve Type 2 puzzles and introduced Type 4 puzzles (and solved those as well). The largest Type 2 puzzle that had been attempted before was a 9,600 piece puzzle and Solomon et. al. (2014) were able to solve puzzles of up to 22,755 pieces! The average run-time of the solver on the Type 4 puzzles was 80.89 minutes, which is a considerable improvement over the 23.5 hours reported by Gallagher (2012) for a 9,600-piece Type 2 puzzle.
Using Neural Networks
Dery, Mengistu, and Awe (2017) presented a neural network based solution for tackling the jigsaw puzzle problem. Given the past successes at tackling the problem in different fields, Dery et. al. (2017) believed that neural network based approaches have the potential to achieve the same accuracies and speed up test time performance. They found that their best model was able to achieve 77% accuracy on 2x2 puzzles and 49% on the 2x3 puzzles using Resnet_50 as a feature extractor.
Sholomon extended their findings from their previous study (2016) study used a neural network metric which predicted given two puzzle piece edges whether or not they should be adjacent in the correct assembly of the puzzle, using nothing but the pixels of each piece. By adding this metric to their previously formulated GA based solver, there was an improvement in the overall accuracy of the solution and the number of perfectly constructed puzzles.
Computer Vision
So far we’ve discussed the reconstruction of an image from shuffled pieces, but what about actual jigsaw puzzles? How can we use computer programming to solve 3D jigsaw puzzles? Past research using algorithms discount the shape of puzzle pieces as a discriminant entirely by using square pieces and relied instead on the underlying image properties to find a solution. Allen (2016) decided to formulate a jigsaw puzzle solver that relies on concepts from computer vision as well as past work in the area to assemble puzzles from a single image of the scrambled pieces. Allen’s puzzle solver is specifically tailored to solve only rectangular puzzles with canonical pieces (see below). Using the Mat-lab Image Processing Toolbox, the solver created was successfully used on 5 separate puzzles of different sizes and different images.
Final Thoughts
With all of the advancements that have been made in solving the jigsaw puzzle problem, if the problem has not been solved yet, I believe developers are rather close!
