June 16, 2012
We have met our match at the genteel pastime of jigsaw puzzles. It seems an algorithm can now whiz through 10,000 pieces in 24 hours. The speedy solver could also help piece together shredded documents or archaeological artefacts.
Andrew Gallagher at Cornell University in Ithaca, New York, wrote the algorithm while working at photography firm Kodak. By mimicking the way a human solves jigsaws, it beat last year’s record of 3300 pieces. The algorithm can even solve multiple puzzles at the same time, where the pieces have been mixed up together.
Unlike other software that only analyses the edges of the pieces, Gallagher’s looks at how colour patterns spread across many pieces. For example, if one piece becomes progressively lighter from left to right, it is likely that the piece nestles between a lighter piece on the left and a darker one on the right.
The algorithm only works on jigsaws with square pieces, which are harder to solve because the shape offers no clues. The algorithm calculates a score for each pair, stores the best matches, and uses these to assemble the whole puzzle.
It starts with the two pieces that match best, then the next two and so on, but crucially these matches don’t have to be adjacent, allowing the algorithm to work on multiple parts of the puzzle at once. Previous methods worked only on a single part, making it harder to spot when it is going wrong. The system will be presented at the computer vision and pattern recognition conference in Providence, Rhode Island, later this month.
In addition to solving puzzles, Gallagher also used elements of his algorithm to enter last year’s DARPA Shredder Challenge, in which participants had to piece together a series of shredded documents . Gallagher’s attempt came in at 17 overall – he says because the puzzle pieces in the challenge were digital images of shredded documents made it harder for the algorithm, as the jagged edges did not line up perfectly and some pieces were missing.
Ohad Ben-Shahar, a computer scientist at Ben-Gurion University in Beer-Sheva, Israel, whose team holds the previous puzzle-solving record, says that Gallagher’s algorithm is impressive because it can handle puzzles in which the orientation of the pieces is unknown, a more challenging problem.
In terms of performance, Ben-Shahar says their algorithm can match Gallagher’s, although they haven’t yet published the results, but both algorithms could probably be improved. “With little effort, the time to solution could drop significantly below a day.”