Communications of the ACM
Algorithm Beats Jigsaw-Solving Record
Credit: Chris Pallatto/Getty
Cornell University's Andrew Gallagher has developed an algorithm that set a jigsaw puzzle-solving record by sorting through 10,000 pieces in 24 hours, surpassing last year's record of 3,300 pieces.
The algorithm also can simultaneously solve multiple puzzles, where pieces have been mixed up together. Gallagher designed the algorithm to mimic the way humans solve jigsaw puzzles by considering how color patterns spread across many pieces, such as how one piece becomes progressively lighter from left to right, and the likelihood that the piece fits between a lighter piece on the left and a darker one on the right.
The algorithm only works on puzzles that have square pieces, which are more difficult to solve because shapes cannot be used as a clue. The algorithm calculates a score for each pair, stores the best matches, and uses these to assemble the whole puzzle. Although the algorithm starts with the two pieces that match best, the matches do not have to be adjacent, which enables it to simultaneously work on multiple parts of the puzzle.
Other applications for the algorithm include piecing together shredded documents or archaeological artifacts.
From New Scientist
View Full Article
Abstracts Copyright © 2012 Information Inc. 
, Bethesda, Maryland, USA
No entries found