digg

Facebook Connect Join Digg About

Million Dollar Math Prize: Solve Questions About Minesweeper

claymath.org — It's not often you can win a million dollars by analysing a computer game, but by a curious conjunction of fate, there's a chance that you might. However, you'll only pick up the loot if all the experts are wrong and a problem that they think is extraordinarily hard turns out to be easy. So don't order the Corvette yet.

Who dugg this? Made popular Jun 24, 2008

Digg DudeWhat is Digg?

Digg is a place for people to discover and share content from anywhere on the web. Digg surfaces the best stuff as submitted and voted on by the community. Take the Tour to learn more.

127 Comments

show profanity settings
expand all
  • AcousticBoom, on 06/24/2008, -9/+77"If your first guess hits a mine, you're unlucky: you get no information except that you've lost."

    Your first square is NEVER a mine.
  • Dumbledorito, on 06/24/2008, -1/+52I'd settle for a starring role in "Minesweeper: The Movie."

    http://www.collegehumor.com/video:1770138
  • justananomaly, on 06/24/2008, -0/+30What happens if we get an 8...?
    Then god help us all.........
  • Iluvator, on 06/24/2008, -0/+25Heh -
    "And the problem is one of the most notorious open questions in mathematics, which rejoices in the name 'P=NP?'. "

    If you can show P=NP (by, say, solving this problem in polynomial time), the million dollars with be relatively minimal in terms of your concerns. It's been a while since my CS Theory class, but isn't most of modern cryptography based around that problem?
  • whiteknives, on 06/24/2008, -2/+2442
  • Thirtysixway, on 06/24/2008, -0/+19But starting position isn't a guess, so yeah it is possible. Your first guess is actually your 2nd move.
  • NoEasyWayOut, on 06/24/2008, -3/+24After reading about 5 paragraphs, all I can come up with to say is...

    "Huh?"
  • thechr0nic, on 06/24/2008, -5/+22there used to be a cheat code for mine sweeper that you could use, it would put a pixel in the corner of the screen if your cursor moved over a mine.
    From this I learned that it is impossible to hit a mine on the first try.

    you can add this to your long list of useless trivia
  • swgbex, on 06/24/2008, -1/+18I dont think thats true in all versions of minesweeper, i've hit one on the first try in vistas minesweeper. At least I swear its happened to me once... damn minesweeper
  • ladon86, on 06/24/2008, -0/+16This is just another problem related to P=NP, so there's actually millions of other problems with a million dollar prize. Solve one, solve them all.
  • rald84, on 06/24/2008, -5/+19you win a million internets.
  • fas2, on 06/24/2008, -0/+14- Most of modern cryptography is based on the difficulty in calculating the discrete logarithm.
    - Factoring numbers is known to be NP-complete. So yes, it is the same as the P=NP problem.
    - It probably is provable. If it was known to be undecidable, no one would bother any more.
  • Doznufus, on 06/24/2008, -0/+13I need my thinking grenades.
  • trevorh, on 06/24/2008, -0/+12No it isn't if you read the article you would have seen that the money for the prize is being put up by a business man named Landon T Clay. You can rest assured that your money is not being taken to fund this prize.
  • Antonton, on 06/24/2008, -0/+12So now if my boss catches me playing minesweeper, I can just say I'm working on a "big project."
  • acatzr800, on 06/24/2008, -0/+12type xyzzy then press shift+enter
  • alk509, on 06/24/2008, -0/+11So this is really a prize for solving P=NP?, they just wrapped minesweeper around it to make you go and read about it... Lame.

    Besides, if you solve P=NP?, you can do a lot better than a mill.
  • diggit83, on 06/24/2008, -1/+12Lol, million dollar price and the best they could come up with was "So dont order the CORVETTE yet"
  • dougmidkiff, on 06/24/2008, -0/+11really? already down?
  • TonyLocNE, on 06/24/2008, -0/+10I dugg you because I have no clue what "thinking grenades" are but am quite intrigued..
  • dishwashersafe2, on 06/24/2008, -0/+9http://www.geek.com/minesweeper-math-1-million/

    misleading title: it's just the P vs NP problem
    The real news is that finding an algorithm to solve minesweeper could help in solving P=NP
  • Kyan, on 06/24/2008, -1/+10I don't see what's so hard about it - if P=NP, just divide by P and N=1.

    /;-)
  • traveler19, on 06/24/2008, -2/+10*****, now i gotta play this stupid game.
  • Kyan, on 06/24/2008, -0/+8And it's a "very small pixel", not one of those regular sized pixels. So, watch out for that, too.
  • EggNogIceCream, on 06/24/2008, -1/+8Mine Sweeper cheat,Type xyzzy, press Enter and Left Shift as soon as the game loads. Moving your mouse over a square with a hidden mine will result in a very small black pixel appearing in the top right corner of the screen when there is no mine it is white. Is it me or the servers down?
  • shortyjacobs, on 06/24/2008, -1/+8Great, now I have to P
  • EggNogIceCream, on 06/24/2008, -0/+7http://failblog.org/2008/04/15/minesweeper-fail/
  • S7aind, on 06/24/2008, -9/+16So this is where my money goes when I pay tuition?
  • Davinator, on 06/24/2008, -3/+9Whoa, you're right. I never realized that.
  • trigon77, on 06/24/2008, -5/+11"Now... we guess"
    http://www.collegehumor.com/video:1770138
  • CapeKid, on 06/24/2008, -0/+6"- It probably is provable. If it was known to be undecidable, no one would bother any more."
    Actually, it probably isn't provable, most computer scientists don't think P=NP. The problem is to prove this you have to prove that every single NP complete problem is unable to be reduced down to P. Whereas to prove that P=NP all you would have to do is prove that a problem that is NP-complete is reducible to polynomial time. Since all NP-complete problems are reducible to other NP-complete problems, solving one would essentially solve every other one.
  • Tebixan, on 06/24/2008, -0/+6If you make a custom game and put in the maximum number of mines, there will only be a few spaces on the grid that are safe. However, you will always get one of those few space spaces with your first click. Of course the second click always ends in disaster.
  • soomprimal, on 06/24/2008, -2/+8How about a million dollar prize for understanding the question?
  • Elliuotatar, on 06/24/2008, -1/+7NOOOOOOOOOOOOOOOOOOOOOOOO!
  • fadetoone, on 06/24/2008, -0/+5http://en.wikipedia.org/wiki/NP_%28complexity%29

    The abbreviation NP refers to "Non-deterministic Polynomial time".

    This is a pretty big concept in computer science.
  • Elliuotatar, on 06/24/2008, -0/+5...but not a million dollars.
  • Cyclozion, on 06/24/2008, -0/+5If you're wrong, you run out of flags before you run out of mines, so you can't win.
  • versionist, on 06/24/2008, -1/+6You can also unlock the "infinite mode" using this tutorial. I did it and it works great.

    http://www.marksinfinitesolutions.com/tutorials/de ...
  • Jo9100, on 06/24/2008, -3/+7Well, that'll get me maybe one or two tanks of gas...
  • TonyLocNE, on 06/24/2008, -0/+4Did anyone else see that 747 fly right over your head? WHOOOOSH....... went this article.
  • Modiga, on 06/24/2008, -0/+4Ah, but Kyan there is a mistake with your reasoning. What happens if P = 0. Scientists hope to solve whether P = 0 or N = 1 using the Large Hadron Collider.
  • DragoonWraith, on 06/24/2008, -0/+3Uhhh... you are right that sometimes you'll have to guess, but that doesn't make it "clearly NP, and never ever P" - actually, if you could prove that something WAS NP and WASN'T (and couldn't be) P, then you win.

    But since you don't even actually understand what they're talking about, you just lose.

    Nice time though, lot better than I've ever wasted my time to do.
  • ExSlashdotter, on 06/24/2008, -0/+3"A true pwner pwns at *all* games." ~teh_masterer
  • noahhoward, on 06/24/2008, -0/+3I'm pretty sure I've died on the first click... but now you've raised doubt and I'm addicted to minesweeper again.
  • analogkid01, on 06/24/2008, -1/+4Is this your homework, Larry?
  • fas2, on 06/24/2008, -0/+3Could? It would! Finding an efficient algorithm to any NP-complete problem would answer that question.
  • Jackar00, on 06/24/2008, -0/+3heh, I know what you're talking bout
  • Elliuotatar, on 06/24/2008, -0/+3Spin the minesweeper field clockwise fast, and the head of Wil Wright appears.
  • jemka, on 06/24/2008, -1/+4-Actually you're all wrong.
    -I would explain it to you, but I don’t have the technology OR the steady hands to pull off a procedure like that.
  • alk509, on 06/25/2008, -0/+3Dude, did those crazy minesweeper gates really help you wrap your head around SAT any better than regular old logic gates would have? That whole minesweeper to SAT reduction is so contrived, it's almost funny (and, in a way, I'm sure it's supposed to be). The only reason minesweeper is mentioned is because everybody knows what minesweeper is, but only mathematicians and computer folk know SAT. A title like "Solve SAT in P-time and win a million" would get a lot fewer hits than "The million dollar Minesweeper prize." :-)
  • Fetching more discussions...
    Show 51 - 100 of 129 discussions

  • Add a Comment

    Login or register to comment!
    Or, sign-in super fast with your Facebook account ...


© Digg Inc. 2009 — Content created and posted by Digg users is dedicated to the public domain | Terms of Use Updated | Privacy Policy
DIGG, DIGG IT, DUGG, DIGG THIS, Digg graphics, logos, designs, page headers, button icons, scripts, and other service names are the trademarks of Digg Inc.