Ah, puzzles. There's no better way to waste a whole bunch of time trying to reconstruct a questionably artistic picture that you should have just bought in one piece in the first place. To the relief of frustrated people everywhere, there is now a new algorithm that can solve absurdly difficult 10,000 piece puzzles in under 24 hours.
What I call an "absurdly difficult" puzzle is one that eschews those handy interlocking pieces for square pieces that are all completely identical to each other. Ugh. But computers don't care about such conveniences: all they need is some image analysis software backed by a clever new puzzle-solving algorithm that relies solely on color matching. First, watch the video:
The algorithm is looking at the colors along the edges of each piece, and trying to find other pieces with edge colors that match. It can deal with pieces in any orientation, and since it just pairs up high matches, it can work on many different pieces of the puzzle at once. Gradually, pairs of pieces are assembled into larger chunks (kind of like how humans do it), and the chunks come together into a completed puzzle. Designed by Andrew Gallagher at Cornell University, this new algorithm can solve a 9,600 piece puzzle in 23 hours and 30 minutes, which means that's it's successfully pairing a puzzle piece every ten seconds or so. This is about three times as fast as any other algorithm has been able to manage.
Believe it or not, there are some potential practical applications to algorithms like this. For example, the anti-shredder tech that DARPA was looking for last year? This jigsaw puzzle solver is directly related to that sort of software, making it a valuable tool for generalized image recognition and feature identification. And childhood ruining.