Forgot your password?
typodupeerror
Math

$50,000 To Solve the Most Complicated Puzzle Ever 180

Posted by samzenpus
from the gather-the-edge-pieces dept.
An anonymous reader writes "A team from UC San Diego is using crowd-sourcing as a tool to solve the most complicated puzzle ever attempted, which involves piecing together roughly 10,000 pieces of different documents that have been shredded. (The challenge is designed to reveal new techniques for reconstructing destroyed documents, which are often confiscated by troops in war zones). The prize for solving this jigsaw puzzle is $50,000, which the UCSD team has decided to share among the people who participate. If they win, you would also receive cash for every person you recruit to the effort! The professor leading the team, Manuel Cebrian, won the challenge two years ago, so his odds of winning again are great"
This discussion has been archived. No new comments can be posted.

$50,000 To Solve the Most Complicated Puzzle Ever

Comments Filter:
  • by Anonymous Coward on Wednesday November 16, 2011 @08:47PM (#38080972)

    only 50k for a problem that complex? If you could solve this problem, I say copyright and make millions off of the algorithm.

    • by tomhudson (43916) <`moc.nosduh-arab ... `nosduh.arabrab'> on Wednesday November 16, 2011 @09:01PM (#38081096) Journal

      To complete this new challenge, it could take as many as 100,000 people

      So, it's essentially worth less than a pack of gum.

      • Hey, it's a month's wage in some poor countries, start building a document rebuilding plant somewhere in backwater Africa.

        • by cowboy76Spain (815442) on Thursday November 17, 2011 @04:44AM (#38083222)

          Hey, it's a month's wage in some poor countries, start building a document rebuilding plant somewhere in backwater Africa.

          Sorry to mix actual data in your First World prejudices, but the GDP per capita of the poorest country is over $300 [wikipedia.org], so monthly it would be around US 18$.

          There are only 15 countries with a GDP per capita inferior to 100$ month

          • Re: (Score:3, Insightful)

            by Anonymous Coward

            Hey, it's a month's wage in some poor countries, start building a document rebuilding plant somewhere in backwater Africa.

            Sorry to mix actual data in your First World prejudices, but the GDP per capita of the poorest country is over $300 [wikipedia.org], so monthly it would be around US 18$.

            There are only 15 countries with a GDP per capita inferior to 100$ month

            Right, because income is evenly distributed there, and there aren't dirt poor people living off almost nothing. Plus, you're using PPP GDP per capita, rather than GDP per capita at nominal exchange rates. If I pay someone in another country $1, they get to buy what $1 buys in their country, not what $1 buys in the USA.

            Sorry to mix actual facts into your misrepresented data.

    • This is almost the same as the DOD $50,000 "challenge" to recover shredded docs remember?

      So what did they do, spin it from the "Bad Dept of Defense" to "a college group"?

      AC nailed it, tech that can do that is "worth" billions in lifetime revenue, so what's with this $50,000 a piece?

    • Copyright is automatic. What prevents them from taking the $50000 and then making millions off of it?

      • Copyright is irrelevant, this is a patent situation. And if the technique (in this case crowdsourcing) is obvious and pre-existing then you can't patent it.

        This solution is a bit of a hack - it's not what the $50,000 is actually meant for, they're looking for an everyday computer-based method. Fair play to them and all though.
        • It's all about who has the fastest gun^W lawyer in the West these days. The right team of lawyers will make any patent or copyright, no matter how insane it is, hold up in court. Yes, sure, SCO made a booboo there, but there are plenty of examples to support this.
    • by Forbman (794277)

      Better send the $50K to Iran, as they were able to do it in 1978...Oh, wait, that involved computors, not computers.

      Doesn't IBM have some algorithmic tech that can help with this? I imagine it involves scanning each strip, and figuring out a way to do some sort of edge analysis of each strip, for each side. Do some sort of FFT or DCT for the edges, and then come up with a way to join similar strips' edges for each side of the strip together. Then, run the joined images of likely sets of strips through an OC

      • by Relayman (1068986)
        You've got the method, now implement it. My understanding is that you are provided with TIFF files of the scans. However, there may be smudges and oil from the shredder.
      • by CmdrPony (2505686)

        Better send the $50K to Iran, as they were able to do it in 1978...Oh, wait, that involved computors, not computers.

        Actually, people were called computers before computers started meaning actual machines. They did the same job, and were usually woman.

    • I'm not sure copyright would give you the protection you'd want. Copyrighting an algorithm is almost impossible, depending on which national legal jurisdiction you're in. And patenting could be expensive, and that too is not full-proof either (especially for a little guy like myself).

      Personally, I'd offer this as a paid service online, and I'd let whichever government had jurisdiction over me -- buy me out (before they just confiscate it away from me without proper compensation).

      • On second thought, if I had the software for doing that, I'd offer it as a paid service online, but then I'd pretend I had a thousand low wage workers in India printing out each little strip of paper and reassembling it painstakingly by hand. This way I could count each worker as a separate contractor on my invoices and charge a corresponding large commission for each.

      • by Fluffeh (1273756)

        Copyrighting an algorithm is almost impossible, depending on which national legal jurisdiction you're in. And patenting could be expensive

        Oh yes, we developed this lovely little algorithm, we want to patent it. Can someone spot us $50k to pay for patent bills?

        Hey, maybe that's where you could use that $50k in prize money?

    • by Sulphur (1548251)

      only 50k for a problem that complex? If you could solve this problem, I say copyright and make millions off of the algorithm.

      Or it could be like a paper on pursuit curves that gets classified quickly.

      In Falcon and Snowman, there was a scene of paper and water being put in a blender to shred the paper.

    • by c0lo (1497653) on Wednesday November 16, 2011 @11:35PM (#38082120)
    • by fluffy99 (870997)

      Except crowdsourcing isn't really an algorithm. You're just getting thousands of eyeballs helping to mix/match the piece like a giant jigsaw puzzle. Not exactly something you can sell as a product.

    • by Relayman (1068986)
      Actually, the rules say that you do not have to reveal your method or give up any intellectual property to claim the prize.
  • Doesn't scale (Score:4, Insightful)

    by Anonymous Coward on Wednesday November 16, 2011 @08:48PM (#38080992)

    The rules should require that the same method that solved the initial puzzle be successfully applied to 10 more shredded documents, to weed out methods that don't scale.

  • by GoodNewsJimDotCom (2244874) on Wednesday November 16, 2011 @08:51PM (#38081016)
    If there is an offline version of this, it involves a garbage bag full of shredded 5$ bills and some scotch tape.
    • by zill (1690130) on Wednesday November 16, 2011 @11:35PM (#38082116)
      For those who didn't get the reference [moneyfactorystore.gov].
      • by Dogtanian (588974)

        If there is an offline version of this, it involves a garbage bag full of shredded 5$ bills and some scotch tape.

        Yeah, but the question is whether they shred each bag separately, or more likely shred the notes en masse, jumble them up, then fill each bag with 5lbs of arbitrary shredded bits. That'd mean that unless each note was lined up with the shredding edges identically you'd be unlikely to have all the bits required to complete the vast majority of notes.

        (I know, I'm overthinking the reply to what was a joke!)

        For those who didn't get the reference [moneyfactorystore.gov].

        Do you reckon this is why they're charging a whopping $45 for what is otherwise (and still is, really)

  • by Anonymous Coward on Wednesday November 16, 2011 @08:53PM (#38081040)

    I never really understood the purpose of shredding documents. If your documents are that sensitive, why not just burn them, leaving no trace of legible text? It seems like it would be cheaper, easier and faster too. Just throw them in a barrel outside, put a little lighter fluid in, and drop a match. Why is this not common?

    • Really, you could do both. And you should use a setup similar to a cremation device instead.
      • by GumphMaster (772693) on Wednesday November 16, 2011 @10:02PM (#38081604)

        Indeed that is what became of classified material I have dealt with. Shredded using a military cross-cut shedder (output pieces smaller than 1x10mm), mixed thoroughly, and then incinerated using a purpose built belt-fed, gas fired machine.

        • Indeed that is what became of classified material I have dealt with. Shredded using a military cross-cut shedder (output pieces smaller than 1x10mm), mixed thoroughly, and then incinerated using a purpose built belt-fed, gas fired machine.

          I bought a cheap home shredder about a year ago, and it crosscuts. Makes reassembly unimaginably more difficult. (I think mine produces more like 2mm wide, but still.)

          And if you don't have an incinerator, just pour the crosscut confetti into a recycle bin where all your other documents go. If you think reassembling one document would be difficult, consider starting from a bucket where the scraps of dozens or hundreds of documents are mixed indiscriminately.

        • by dakohli (1442929)

          Indeed that is what became of classified material I have dealt with. Shredded using a military cross-cut shedder (output pieces smaller than 1x10mm), mixed thoroughly, and then incinerated using a purpose built belt-fed, gas fired machine.

          Actually, a quick check of online regs [doe.gov] states that the maximum size must be 1mm x 5mm. When you use an approved shredder, the pieces are very small, producing thousands of bits per page. The magnitude of this challenge is huge.

          In some cases the challenge will be to determine just which side is up. If the document was double sided, then the order of difficulty will increase greatly.

    • by arth1 (260657) on Wednesday November 16, 2011 @09:38PM (#38081422) Homepage Journal

      I never really understood the purpose of shredding documents. If your documents are that sensitive, why not just burn them, leaving no trace of legible text? It seems like it would be cheaper, easier and faster too.

      What happens is that the top and botom pages and edges get scorched, but the middle part with the print remains largely intact.

      Just throw them in a barrel outside, put a little lighter fluid in, and drop a match. Why is this not common?

      Thus speaks someone who hasn't tried to burn more than a couple of sheets of paper.
      It takes time to burn more than a few pages at a time. Or an extremely hot fire. Sorry, Mr Bradbury, 451 F won't do it, unless you can wait for weeks.

      • by dakohli (1442929)

        I have operated a purpose built incinerator designed to burn documents. We collected the material in burn bags, operators were encouraged to crumple up the paper. Each night, the bags were fed into the incinerator, which used diesel fuel to start the burn. A couple of time per hours, the ashes were mixed, and more bags introduced. It took time, but I can assure you, that all of the docs were destroyed each night.

        Eventually, environmental issues shut down the incinerators, and we moved to shredding. It

      • by Hatta (162192)

        What happens is that the top and botom pages and edges get scorched, but the middle part with the print remains largely intact.

        Problem solved [amazon.com].

    • by DRJlaw (946416) on Wednesday November 16, 2011 @10:23PM (#38081732)

      I never really understood the purpose of shredding documents. If your documents are that sensitive, why not just burn them, leaving no trace of legible text? It seems like it would be cheaper, easier and faster too. Just throw them in a barrel outside, put a little lighter fluid in, and drop a match. Why is this not common?

      1. Burning is inconvenient for small volumes of paper.
      2. Burning is essentially illegal for large volumes of paper (business scale; Clean Air Act permits).
      3. Fireplaces are not as common as they used to be; outdoor burning is illegal in most cities.
      4. People can be idiots [insweb.com] when using fire outside of a fireplace or permanent fire pit.
      5. DIOXIN! [ny.gov]

      Shredding is like a residential door lock -- good enough to discourage a casual person who is too curious for their own good. Secure commercial shredders rely upon sheer volume and decent mixing (300 "particles" per page x 3 tons of paper dumped at a recycler is a decent level of obscurity) or "hydro-pulping" for the demanding (shred then pulp at paper mill -- good luck reassembling the fibers even if you get to them before bleaching).

    • by fatphil (181876)
      Better - pulp them into bricks that can be used as logs for a fire and burnt at your leisure in your weekend cottage. Paper burns slowly in bulk - turn that into a feature.
  • Don't the warlords have access to fire? I'm pretty sure that brings about a thoroughly unrecoverable destruction of the documents...
    • by Meshach (578918)

      Don't the warlords have access to fire? I'm pretty sure that brings about a thoroughly unrecoverable destruction of the documents...

      Impractical: I am pretty sure that most offices where this would actually be used have rules against lighting fires indoors. Shredding provides a way to dispose of any document in any circumstance.

      • by arth1 (260657)

        Impractical: I am pretty sure that most offices where this would actually be used have rules against lighting fires indoors.

        And rules like that are so important to follow when the enemy is at the gates. Make sure you wipe your feet too, so they won't come to a dirty floor.

      • Don't the warlords have access to fire? I'm pretty sure that brings about a thoroughly unrecoverable destruction of the documents...

        Impractical: I am pretty sure that most offices where this would actually be used have rules against lighting fires indoors. Shredding provides a way to dispose of any document in any circumstance.

        If we're talking about warlords and other such types, who don't see a problem with using rape as a tool for war, I don't think they would be that worried about lighting a fire in a place where others might think it to be less-than-kosher. Hell if a warlord is trying to run away from something, they may well just set the entire building alight in hopes that the documents and everything else inside will go up in smoke.

    • SHHH!! (Score:5, Funny)

      by jensend (71114) on Wednesday November 16, 2011 @09:10PM (#38081172)

      Everyone in the civilized world is worried about what will happen if terrorists gain access to this technology. That's why most nations have signed the Fire Non-Proliferation Treaty, and it's why the International Combustive Energy Agency is working round-the-clock to keep this technology from falling into the wrong hands (while somehow also promoting civilian use of combustive energy).

      You've got to be a lot more careful about talking about such restricted technology and its possible uses.

      • Re:SHHH!! (Score:5, Funny)

        by jensend (71114) on Wednesday November 16, 2011 @09:13PM (#38081198)

        See also United States v. Prometheus for more about the penalties for divulging such classified information.

        • by Namarrgon (105036)
          Geez, the penalties are steep.. "not less than an eternity of eagle-based liver removal" for a first offence :-/
          • Fineprint: In times when the Department of Corrections is out of suitably trained eagles, a chicken hawk (*) may be substituted.

            (*) named Henery.

          • by a whoabot (706122)

            Eternal aquiline palinauxohepatectomy (eagle-based[aquiline] removal [ectomy] of a regrowing[palinauxo-] liver[hepat-]).

      • The major problem in the plans to keep fire out or terroist hands is the standard practice of dropping incendiaries on their houses, which essentiall gives them fire.

        They are working on plans to combine blimp technology and water for a more childish approach. We will have to wait and see how that works out. It may spur innovation in the area of massive lift fans to lift the ballon and transport it over the hundreds of miles to target. Or the worlds lagest catapult. Either way new science and technology will

    • by artor3 (1344997)

      Only if you do it right. A sloppy burn job leads to entire pages of recoverable data. A confetti cut shredder will make the data damn near unrecoverable no matter how the paper is fed in.

    • by tukang (1209392)
      You've obviously never watched MacGyver [scribd.com]
    • by mollymoo (202721) on Wednesday November 16, 2011 @10:19PM (#38081710) Journal
      I burn my old bank statements etc. and it's actually pretty time consuming and labour intensive to completely burn anything more than a few sheets. Just throwing a stack of papers on a fire doesn't work - the middle pages don't burn and are completely legible. Even when burnt, undisturbed paper ash still has legible text on it. You need to do a lot of stirring and separating of sheets to ensure complete destruction. It's much more time consuming than shredding.
      • The machine we have at home shred the paper in fine line, throw it on a fire, it burns very VERY well. Maybe I should patent that : a portal incinerator connected to a shredder.
      • Try one of these [paperlogmaker.co.uk]

        You can shred the documents, make some briquettes, and put them on the bonfire come Bonfire Night. Or, if you have a wood burning stove or hearth, you get free fuel.
    • Re: (Score:3, Funny)

      by Trevorm7 (1082535)
      Or just run it through an HP printer, the process of trying to rip it out after it jams should do the trick.
  • Confused? (Score:5, Insightful)

    by wisnoskij (1206448) on Wednesday November 16, 2011 @09:21PM (#38081276) Homepage

    Is it just me or does this make little to no sense.
    You cannot scale putting together puzzle pieces because the same person needs to both see two pieces that go together and recognize that they match.
    So yes more people help, but if there are 10 million pieces then the average person would have to look at over 1 million pieces before they have even seen two that go together.

    And this seems like a very easy thing to computise.
    You digitize the shredded documents.
    You run a program that looks for similarities around the edges.
    You stick likely candidates together and either ask for human confirmation or run a text recognition algorithm to see if the result makes sense.

    Now this becomes harder if the direct edge of many of the shredded parts are blank, but still more then doable if you use spacing recognition(calc how big a space is in this document and look for the correspond amount of missing space on the other side), line up the text rows, and some basic word statistic (if you see "he ...", for example you are likely looking for a "T" on the right side of another strip).

    • by wvmarle (1070040)

      If it were so easy to computise, why haven't you done it yet and taken the prize?

      My guess it's not that easy. And that it also doesn't have to do with computing horsepower as such.

      Then about the text recognition and analyses: don't forget that there are more languages than just English. As a matter of fact most people in this world use a language other than English in their daily life. I for one use four languages, of which three daily and the fourth at least weekly. And English is my second language. You

    • by wagnerrp (1305589)

      I think the idea is that you use the software to churn out tons of small patches of potential matches, which then get passed out to the humans for verification. If the humans score the patch highly, those used pieces are considered spent, and down-weighted from any further matches, while the software bumps up to the next level and starts weaving together the larger patches.

      Since the software is only making small patches, the number of combinations stays within manageable levels, and the humans are better a

    • by Nemyst (1383049)

      I'm fairly sure this problem is NP-complete, which makes it anything BUT trivial to compute. It might be easy to represent computationally, but to actually calculate the result is extremely hard. In fact, finding an efficient algorithm for it would make you incredibly rich and possibly dead.

      • It very well might be NP-complete (but probably more of a fuzzy NP complete as there a certain assumptions you can make about the content and it cannot be compressed down to a purely simple mathematical problem) but I think that if that were so that it would be NP-complete for humans as well as there is no best guess and good enough solution. And no human could even hold enough of the puzzle in their head to attempt any kind of effective solution.
        So yes it might be hard to solve in a reasonable time with a

      • by Intropy (2009018)
        It's not NP-complete. You can determine whether two pieces fit together in constant time so you can find a match for a given piece in O(n) time. The paper is planar, so the number of "matchings" is linear in n. Find a match in O(n) time O(n) times and you got yourself a quadratic problem.
        • by Surt (22457)

          I would like evidence for the claim that you can check the fit of two pieces in constant time. This would seem to be the primary difficulty involved in the contest, if it were straightforwardly clear that you could do it in constant time I think the contest would be over.

    • by edgr (781723)
      A lot of research has been done on the second step of this algorithm in bioinformatics. When sequencing a genome, generally all you get are millions of short sequences that need to be stuck together. The algorithms work by calculating probability scores for various pieces to be adjacent and then doing some funky statistics. It's a non-trivial problem to calculate those probabilities for the document reconstruction problem, and then the reconstruction is in 2d instead of 1d, but the bioinformatics algorith
    • by westyvw (653833)

      Would it be possible to get information from the scan beyond that of the text itself? Perhaps each cut has a unique edge, so you could line up the columns of likely candidates. Or maybe the grain in the paper could be revealed, adding another potential edge. Maybe thickness of the paper could be compared or opaqueness. Put all this extra information together and maybe a computer could then work on the construction of the actual text.

    • by fluffy99 (870997)

      I agree some computer pre-sorting is needed to pare the problem down a bit first.

      If this involves multiple pages, perhaps the computer can distinguish which pieces belong to which pages based on the angle of cut versus the font? Or top face versus bottom face. I doubt every piece goes through the shredder exactly the same angle. You'd need pieces large enough to determine the font angle with respect to the edges

      Each cutting blade and cross-cut tooth isn't identical. It may be possible to distinguish what

    • by Surt (22457)

      Looking for similarities around the edges breaks down when most of the edges look very similar (each edge might be a good match for hundreds of other pieces). Asking for human confirmation on tens of thousands of samples requires a lot of patience, and with such small pieces, it may even be difficult for a human to judge.

      The last puzzle looks really challenging. It's clear that there are bits missing (even sub-bits of pieces), and some curled or torn edges on some of the shreds.

    • From a computer perspective I think the problem might be in tracking the possibilities, rather than in the matching. IE I think you could quite quickly take once piece and compare it with the other 9999 pieces and see which ones will line up reasonably well with it. The trouble is that you might find many plausible matches and have to track them all going forward.

      In some way it might be analogous to chess in the sense that the immediate effect of individual moves are easy for a computer to consider but i
    • And this seems like a very easy thing to computise. You digitize the shredded documents. You run a program that looks for similarities around the edges. You stick likely candidates together and either ask for human confirmation or run a text recognition algorithm to see if the result makes sense.

      This sort of approach has been used before, as far back as 1969, as described in this excerpt from an issue Popular Mechanics [google.ca]:

      The job of reassembling 30,000 pieces of an Egyptian temple at Karnak is being given an assist by an IBM computer... The pieces are coded and photographed, and the photos matched with the help of the computer.

      More recently, software developed at Tel Aviv University [bloomberg.com] is being used to piece together thousands of hand-written document fragments.

  • by Anubis IV (1279820) on Wednesday November 16, 2011 @09:34PM (#38081386)

    ...remember the days when /. had actual editors that could catch related or duplicate summaries [slashdot.org] and either tie them together or throw them out? No? Me either.

  • Just another example of college kids not getting paid enough for their skills. A puzzle solver fresh out of college should be making three times that at least.
  • Didn't even ask to set up a password after clicking "sign up"
  • by MSTCrow5429 (642744) on Wednesday November 16, 2011 @11:47PM (#38082190)
    "The professor leading the team, Manuel Cebrian, won the challenge two years ago, so his odds of winning again are great[.]"
    • So, you don't think there can be a correlation between expertise and odds of winning in a contest that is NOT DECIDED BY RANDOM CHANCE?

      Talk about Statistics Fail.

    • Uhhh... No. Someone who has a demonstrable skill in a specific area can be expected to excel in that area in the future. That's a statistical fact.

      Or do you expect him to start again from scratch, forgetting everything he learned the first time around? Proven solutions are just too easy, right?
  • Perhaps the most complicated puzzle ever in the board-game sense, but for a real puzzle will somebody solve the Riemann Hypothesis so we can all enjoy the beauty of the solution in our lifetime. Now that would be amazing.
  • it takes less effort, and less time, and less technology, to burn documents than to shred them. If shredding ceases to become useful, it'll take eight seconds before the new fangled algorithm will be useless.

  • Wasn't the Human Genome Project a much more complicated puzzle with a bigger reward?
  • >> which are often confiscated by troops in war zones

    Translation: confiscated by the IRS when visiting your office.

  • by zazzel (98233) on Thursday November 17, 2011 @03:52AM (#38083068)

    As far as I know, German Fraunhofer Institute has a solution for this kind of problem: http://www.ipk.fraunhofer.de/component/content/category/167-autsicherheitstechnikstasischnipsel [fraunhofer.de] (p.8ff, German language).

    Looks like they have few problems assembling torn pages, and geometrically correct results for shredded paper (yet not necessarily correct content).

  • The real problem the government is trying to solve is of course putting together the shredded pieces in such a way that suits them most :)

    I guess that will be the next challenge.

  • A German company solved this exact problem years ago, when trying to find a way to reconstruct documents of the former East German Staatssicherheit that had been shredded.

    Oh, and they're not dealing 10000 pieces various documents, they're dealing with 10000 bags full of pieces of shredded documents. Crowd-source that.

If you're not part of the solution, you're part of the precipitate.

Working...