digg

Join DiggAbout

The Digg Crew wants to hear your thoughts!
Please take our short survey about Digg and potential feature ideas.

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.

show profanity settings
expand all
  • S7aind, on 06/24/2008, -11/+16So this is where my money goes when I pay tuition?
    • trevorh, on 06/24/2008, -0/+14No 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.
  • traveler19, on 06/24/2008, -2/+10*****, now i gotta play this stupid game.
  • thechr0nic, on 06/24/2008, -5/+23there 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
    • 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.
    • acatzr800, on 06/24/2008, -0/+13type xyzzy then press shift+enter
      • thechr0nic, on 06/24/2008, -1/+3this particular cheat only worked with Windows 3.X
        • gurudrew, on 06/24/2008, -0/+2Not true. I'm using it on XP right now.
        • pyro789x, on 06/24/2008, -0/+2It works with both my desktop and laptop, both running Windows XP. Whether that is 3.X or not, I'm not sure.
        • acatzr800, on 06/24/2008, -1/+1sadly... not in Vista... although the new graphic effects are worth it.
        • theaceoffire, on 06/24/2008, -0/+2@acatzr800
          What graphic effects? Minesweeper HD!
    • Elliuotatar, on 06/24/2008, -0/+3Spin the minesweeper field clockwise fast, and the head of Wil Wright appears.
    • 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 ...
    • 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.
    • iceman35, on 06/24/2008, -1/+1There is a cheat. First you have to open a big open spot then you put your cursor on and empty spot near a square unclicked. You press both the right and left mouse buttons and if the square stays unclicked then there is a bomb. If there is no bomb then the square will open automatically.
  • AcousticBoom, on 06/24/2008, -9/+79"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.
    • Davinator, on 06/24/2008, -3/+9Whoa, you're right. I never realized that.
    • rald84, on 06/24/2008, -5/+19you win a million internets.
    • swgbex, on 06/24/2008, -1/+19I 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
    • Thirtysixway, on 06/24/2008, -0/+20But starting position isn't a guess, so yeah it is possible. Your first guess is actually your 2nd move.
    • Elliuotatar, on 06/24/2008, -1/+7NOOOOOOOOOOOOOOOOOOOOOOOO!
    • magicalstephie, on 06/25/2008, -0/+1My first square has been a mine LOTS of times.
  • michaelwong38, on 06/24/2008, -2/+1interestingly interesting
  • Jo9100, on 06/24/2008, -3/+7Well, that'll get me maybe one or two tanks of gas...
  • Dumbledorito, on 06/24/2008, -1/+53I'd settle for a starring role in "Minesweeper: The Movie."

    http://www.collegehumor.com/video:1770138
  • dougmidkiff, on 06/24/2008, -0/+11really? already down?
  • whiteknives, on 06/24/2008, -2/+2542
  • sofaKing812, on 06/24/2008, -2/+2Do I automatically win because their page is down?
  • trigon77, on 06/24/2008, -5/+11"Now... we guess"
    http://www.collegehumor.com/video:1770138
  • justananomaly, on 06/24/2008, -0/+31What happens if we get an 8...?
    Then god help us all.........
  • 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?
    • diemunkiesdie, on 06/24/2008, -0/+1I just tried this a few times (Windows XP) and I couldn't get it to work.
      • Jwoey, on 06/24/2008, -0/+2the black pixel is in the top left, not top right as he said.
      • 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.
      • zip000, on 06/24/2008, -0/+1I've just tried it and it does work...though it's actually xyzzy, shift, then enter.
  • Rudegar, on 06/24/2008, -4/+0http://www.winsite.com/bin/Info?11500000036281
    not often we can get easy answers! :)
  • 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."
  • EggNogIceCream, on 06/24/2008, -0/+8http://failblog.org/2008/04/15/minesweeper-fail/
  • rphocke, on 06/24/2008, -2/+4I can barely beat Mine Sweeper....count me out on this million.
  • NoEasyWayOut, on 06/24/2008, -3/+26After reading about 5 paragraphs, all I can come up with to say is...

    "Huh?"
  • MrMax99, on 06/24/2008, -0/+1mirror?
  • donkz, on 06/24/2008, -3/+1If the page is down you can always check and see the link from exact same digg story that was submitted several times during last year.
  • shortyjacobs, on 06/24/2008, -1/+8Great, now I have to P
  • NathanMahdavi, on 06/24/2008, -0/+1http://66.102.9.104/search?q=cache:daXUqV0F3FkJ:ww ...
  • 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"
    • analogkid01, on 06/24/2008, -1/+4Is this your homework, Larry?
    • jchrome, on 06/24/2008, -0/+2Haha, I thought the exact same thing. Might as well have said "so don't order that double-wide trailer just yet" or "don't go hog-wild at Walmart just yet"...
  • Iluvator, on 06/24/2008, -0/+26Heh -
    "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?
    • skidmarks085, on 06/24/2008, -8/+1Most of modern cryptography is based on the difficulty in factoring large composite numbers. It isn't the same as the P=NP problem.

      I've spent some time researching this problem in a combinatorics class and I think that it is outside of our logic system. It can't be proven true and it can't be proven not true.

      • fas2, on 06/24/2008, -0/+15- 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.
        • 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.
        • 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.

          /;-)
        • 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.
        • 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.
        • Origin415, on 06/24/2008, -0/+1@CapeKid
          If you prove one NP-complete problem is not P, then you have proven them all.
          Proof: Assume A is NP-complete and not P. Assume B is NP-complete.
          If B is P, then A must also be P. Contradiction, therefore B is not P.

          And as to whether its undecidable, it took quite some time for the continuum hypothesis to be proven undecidable, it is in no means a trivial thing to do.
        • fas2, on 06/24/2008, -0/+2@CapeKid:

          If I say provable, I mean decidable in the mathematical sense. That means, it is possible to logically deduce whether P=NP. And that is probably the case.

          You say, proving one NP-complete problem to be in P does not imply P != NP. Can you give me a source/article/explanation? I always assumed that this does imply P != NP, so I'm curious now.
        • fas2, on 06/24/2008, -0/+2Alright, I looked it up. It is really the case that if you prove one NP-problem to be in P, then P=NP and if you prove on NP-problem not to be in P, then P != NP.

          http://www.ti.inf.uni-due.de/teaching/ss2007/b2/fo ... page 2 bottom right.
    • asleepy0, on 06/25/2008, -0/+2ALL cryptography is based on the assumption that P != NP.
  • ladon86, on 06/24/2008, -0/+17This 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.
  • Thirtysixway, on 06/24/2008, -2/+2Mirror!? come on it's been like 10 minutes and the site is down. Must be using IIS...
  • dishwashersafe2, on 06/24/2008, -0/+10http://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
    • fas2, on 06/24/2008, -0/+3Could? It would! Finding an efficient algorithm to any NP-complete problem would answer that question.
    • xkhaozx, on 06/24/2008, -0/+2No, its finding an algorithm to check whether a minesweeper game has a solution. Given a valid solution, its pretty trivial to solve it.
    • SushiCW, on 06/24/2008, -0/+1Not really misleading. Most people have never heard of P?=NP, and this is a pretty good introduction to it in terms people can understand.
  • flocktest, on 06/24/2008, -5/+3gah
  • eouhhohh, on 06/24/2008, -4/+3Is it possible to hit a mine on your first guess? I never have so I just assumed it didn't actually plant the mines until you choose your "starting position."
    • Thirtysixway, on 06/24/2008, -1/+3But starting position isn't a guess, so yeah it is possible. Your first guess is actually your 2nd move.
    • magicalstephie, on 06/25/2008, -0/+0yes. I've hit a mine as my first click on a new board.
  • flocktest, on 06/24/2008, -2/+1doh!
  • asspants, on 06/24/2008, -2/+3tl;dr
    • Jwoey, on 06/24/2008, -1/+2too complicated, started to read but aborted when I realized it was above my reading level.
  • beesaretasty, on 06/24/2008, -6/+3So N=1? Did I win anything?
  • trentrezn0r, on 06/24/2008, -8/+3Huh? I like to think I'm smrt, but WTF is P=NP?

    I know 'Friends of P' http://en.wikipedia.org/wiki/Friends_of_P
    I know 'P' http://en.wikipedia.org/wiki/P

    But, P = NP? Let me wikipedia that too http://en.wikipedia.org/wiki/P_%3D_NP_problem ... Wait, that confused me even worse.

    I know. It means:

    Probability_I_solve_this = Not_Probable

  • fadetoone, on 06/24/2008, -1/+3"If you wish, you can choose to mark a square as containing a mine: if you're wrong, you lose."

    Um... no.
    • Cyclozion, on 06/24/2008, -0/+6If you're wrong, you run out of flags before you run out of mines, so you can't win.
      • Origin415, on 06/24/2008, -0/+2Well you will probably stumble upon a unflagged mine before that.
        • CyclonusRIP, on 06/25/2008, -0/+1If you are writing an algorithm to solve the problem and it flags something that isn't a mine you lose because you're code probably lacks the ability to realize it made a mistake.
  • soomprimal, on 06/24/2008, -2/+9How about a million dollar prize for understanding the question?
  • krnldmp, on 06/24/2008, -2/+1Nevermind I get it.
  • Doznufus, on 06/24/2008, -0/+14I need my thinking grenades.
    • TonyLocNE, on 06/24/2008, -0/+11I dugg you because I have no clue what "thinking grenades" are but am quite intrigued..
  • mttyd, on 06/24/2008, -4/+1Burried... MS won't share the code so you have no way of analyzing the random number generator used to generate the minefields...
    • jonshipman, on 06/24/2008, -0/+1So this is why Bill Gates is retiring...
    • ExSlashdotter, on 06/24/2008, -1/+1You obviously have no real understanding of computer science. let me see if i can help.

      The random number gen is just used to place the mines. the problem isnt figuring out how to place the mines. The problem is coming up with an algorithm that can solve for the locations of the mines using the clues given.

      a good random number gen is as random as possible. many times its an algorithm seeded from something at random. for instance, the processor cycle that the cpu happens to be on at the moment it executes the line of code.
      • mttyd, on 06/24/2008, -0/+1And if the random number generator isn't random (which most are never truely random) then the algorythm can be written to exploit this and you have your tried and true solution... Yes I have no "real understanding of computer science" just a few degrees (;
        • CyclonusRIP, on 06/25/2008, -0/+1And figuring out how to hack the computer's random number generator is hardly a challenge, and certainly no one is giving away 1 million dollars for you to do that.
    • vdog, on 06/24/2008, -0/+1You don't need the code- even if you did have it, it wouldn't tell you how hard any given grid is to solve, which is the point of the problem, AFAIK.
  • alk509, on 06/24/2008, -0/+12So 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.
    • Origin415, on 06/24/2008, -0/+1How exactly? Mathematics is not a lucrative field by any means. I guess if P = NP thats pretty sweet, but I don't know how you would make money off of it.
      • ExSlashdotter, on 06/24/2008, -0/+1He's implying that if you can solve an arguably impossible mathematical problem, then you most likely posses the intelligence to make a decent living among the other morons on this planet.

        And comparatively, most of the other people on the planet *are* morons to the person that would win this prize.
        • CyclonusRIP, on 06/25/2008, -0/+2Not to mention the fact that if you can solve P=NP then you could develop a process to remove any type of encryption. Someone probably has some encrypted data lying around that they would be willing to pay for someone to help them read it IMO.
        • StaticThunder, on 06/27/2008, -0/+1Among other things. Showing P=NP is one of those things akin to turning lead into gold through alchemy. Something with such a huge payoff that it calls everything into question, not just cryptosystems.


          Its a class of problems where the size of the space you have to search increases much faster than your ability to traverse it. It may be hard to prove rigorously but its obvious WHY NP and P have to be different.

          And anybody who turns minesweeper into a boolean SAT problem is just annoying. Gah. I hate people who do things like that. Lets dumb-down a problem for the rubes by not dumbing it down.
      • alk509, on 06/25/2008, -0/+1Mathematics may not be lucrative by themselves, but their applications certainly can be. There's a lot of people in industry, banking, government, et cetera, willing to pay a lot of money for efficient ways of solving problems that just happen to be NP-complete.
    • tech42er, on 06/24/2008, -0/+1Yeah, but I guess making it into minesweeper might make it easier to wrap your head around. That seems to be the thinking/excuse for the mathematician to write a paper on it.
      • 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." :-)
      • StaticThunder, on 06/27/2008, -0/+2It makes it no easier for me. Its still an NP-hard problem. Thats the thing, they're all equivalent. Dolling it up and pouring chocolate on it isn't going to change that.
  • catcher6250, on 06/24/2008, -1/+1Rofl, these questions are impossible.
  • nonsequitor, on 06/24/2008, -2/+5Minesweeper is an imperfect information game, sometimes you will *ALWAYS* have to guess, meaning the problem is clearly NP, and will never ever be P.

    For instance, you have only 2 unmarked squares left in the game and 1 mine. All the numbers around those 2 adjacent squares tell you that the mine can be in either square. You now have 50/50 odds of winning or losing. There is no mathematical way to solve this, unless there is some non-random distribution of mines which can be deduced from attacking their random number generator.

    My best time on Expert was 47 Seconds.
    • 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.
    • mttyd, on 06/24/2008, -0/+1That's what I was trying to say before I was told I know nothing about computer science (:
    • cheesenuggets1, on 06/24/2008, -0/+1Like this?
      http://failblog.org/2008/04/15/minesweeper-fail/
  • TonyLocNE, on 06/24/2008, -0/+4Did anyone else see that 747 fly right over your head? WHOOOOSH....... went this article.
    • ExSlashdotter, on 06/24/2008, -0/+1Want to know what you learn about if you go to college for computer science? May i present to you, discrete mathematics.

      And when i say CS, i mean CS. Not software engineering or IT.
      • TonyLocNE, on 06/24/2008, -0/+1I think I'll stick with my business administration degree..
  • ExSlashdotter, on 06/24/2008, -0/+3"A true pwner pwns at *all* games." ~teh_masterer
  • vdog, on 06/24/2008, -0/+2Dugg for building logic gates out of Minesweeper.
  • jordanleegauci, on 06/24/2008, -0/+1brb to collect my prize
  • ajkrik, on 06/24/2008, -0/+1What is a good Minesweeper score for the "expert" level?
  • CapeKid, on 06/24/2008, -0/+1My mistake, I misspoke (mistyped?). I meant that in order to prove NP != P you have to prove that there exists no possible method to reduce that NP-complete problem to P. Which essentially means trying all infinity possible ways to reduce the problem. Something that is not really do-able.
    You can however eliminate certain ways to reduce NP to P, but that in no ways proves that NP != P. This is kind of like your virus scanning program, it can check for certain types of viruses, but not all types of viruses.
  • rancidpony, on 06/25/2008, -0/+2After reading the first seven paragraphs, I think I know why they have to throw out a million dollar prize to get people interested in math. Mathematicians should not try to write. They should stick to equations.
  • paulface12, on 06/25/2008, -0/+1This is quite a coincidence for me... My power went out yesterday, and all I had for entertainment was minesweeper on my laptop. Anyway, my friend remarked that minesweeper was a stupid game based purely on random luck.

    I just emailed her the article. PWN.
  • jimz, on 06/25/2008, -1/+2It's impossible to hit a mine on your first click, so this article has no credibility.

    If you happen to click on a mine on your first attempt, the application moves that mine to the top left corner. If there's already a mine in the top left corner, it attempts to put it on the next mine (to the right, or the leftmost mine of the next line if it reaches the end). Debug the program yourself.
    • magicalstephie, on 06/25/2008, -0/+1wrong. I've hit a mine on my first attempt many times.
  •  

    Login or register to add a comment

    Create a new account or login to join in the conversation on Digg. You'll also be able to Digg stories to help promote things you like.


© Digg Inc. 2008 — Content posted by Digg users is dedicated to the public domain.
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.