Algorithm beats jigsaw-solving record

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.

Shredder challenge

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

If you would like to reuse any content from New Scientist, either in print or online, please contact the syndication department first for permission. New Scientist does not own rights to photos, but there are a variety of licensing options available for use of articles and graphics we own the copyright to.

Have your say

Only subscribers may leave comments on this article. Please log in.

Only personal subscribers may leave comments on this article

Subscribe now to comment.

All comments should respect the New Scientist House Rules. If you think a particular comment breaks these rules then please use the "Report" link in that comment to report it to us.

If you are having a technical problem posting a comment, please contact technical support.

turkey pot pie southern university regenesis fanboys ucla usc ucla usc sean taylor