Forgot your password?
AI Programming Security Games News

A Faster Jigsaw Solving Algorithm 104

Posted by Unknown Lamer
from the computers-ruin-everything dept.
mikejuk writes "Andrew Gallagher at Cornell University in Ithaca, New York has improved the standard approach to automated jigsaw solving by copying what humans do in finding groups of pieces that best match and working outwards from there. With a speed of 10,000 pieces per 24 hours, it can solve large puzzles. Not only that, but the type of jigsaw it solves is more difficult than the usual in that the pieces are square and can be placed in any orientation. It is so good it can even solve problems consisting of a number of mixed up pieces without being told how many or their dimensions. Of course, as well as having fun beating humans at another recreational pastime, the technique could be used to unscramble shredded documents, as per the recent DARPA challenge."
This discussion has been archived. No new comments can be posted.

A Faster Jigsaw Solving Algorithm

Comments Filter:
  • Re:Seems slow. (Score:5, Informative)

    by ensignyu (417022) on Tuesday June 19, 2012 @04:11AM (#40367285)

    Inexact matches. In the puzzle described in the paper, the pieces are all square (no notches). So the algorithm has to decide which edge matches best based on the similarity of the pixels, but it could be wrong or there may be multiple pieces that look like they match equally well (e.g. sky pieces which look very similar).

    In the cases where it's wrong, it may have to throw out some of the fittings -- e.g. if you have a bunch of smaller groups of tiles that seem to fit together, but when you put it all together the puzzle isn't rectangular, then you have to break up the groups and try again. You can't just match one tile and be done with it.

  • by DNS-and-BIND (461968) on Tuesday June 19, 2012 @05:07AM (#40367437) Homepage
    Woman Throws Fit and Tears up 50,000 RMB Cash, Takes Bank 6 Hours to Piece Together Just 1 Bill []

    On the morning of May 3rd, Sichuan Chengdu city resident Lin Zhaoqiang carried 50,000 yuan in torn 100 yuan bills from Chengdu Jintang to the Bank of China Sichuan Branch, looking for help. May 1st, Lin Zhaoqiang's wife all of a sudden had a fit and tore the 50,000 yuan life-saving money into pieces. Facing thousands of pieces of cash, 12 bank employees sorted and spliced for 6 hours only to piece together a single 100 yuan bill. The remaining money, if unable to be pieced back together, face the unfortunate possibility of being declared null and invalid. Because this money is for treating his wife's mental illness, Lin Zhaoqiang said he won't give up.

    One of the commenters said they should just weigh the cash, but obviously that would be too simple. Nothing is simple when dealing with Chinese banks and their ridiculous rules. They'll flat-out refuse to take small bills or coins ("What the heck are we going to do with all these jiao notes? [] What are we, a bank or something?")

Work is the crab grass in the lawn of life. -- Schulz