Slashdot Mirror
Using Minesweeper to Solve NP
Blue Leader writes "Boston.com is reporting that the answer to one of math's most vexing problems lies in Minesweeper. Figure it out, and render modern encryption useless." Its a discussion of NP/P, as well as an excuse to play minesweeper. Personally, I kinda prefer mahjongg or tetris tho ;)
John
John_Chalisque
I find it very hard to believe that Minesweeper could be won every time, at least on the Expert level, or similar "big" boards. Mostly I think this because it can be really unpredictable.
Consider: Minesweeper (at least the Windows version) seems to give you the first "click" free. In all my playing, I've never hit a bomb on the first click. Presumably the bomb locations are randomly located after this first click.
Now, sometimes on that first click, you get a "2" or "3", with no other spaces uncovered. What then? It comes down to luck, basically. You have no way of knowing for sure which of the 8 squares surrounding your numbers has mines, so you just have to click one and hope. Alternatively, you could click on a totally different area of the board. The odds of you not hitting a bomb are probably better if you do this, but in my experience you end up hitting a bomb enough times to make "winning almost every time" impossible.
Even throughout a game, you usually cannot avoid coming to these "decision points", where you are unable to logically deduce the locations of bombs, and are forced to make a blind pick.
It's worth pointing out that the Boston.com does gloss over some fairly important mathematics.
All that Kaye has done is show that Minesweeper is NP complete. He has not yet found a polynomial-time solution to it, which is necessary to prove that P=NP -- in a nutshell, he just shows that Minesweeper falls into an equivalence class that holds a hell of a lot of other algorithms.
And EVEN IF HE FINDS the polynomial solution to Minesweeper, that STILL doesn't say anything about RSA (or any other "hard" algorithm), other than that it can be solved in polynomial time SOMEHOW.
The only reason people focus on this conjecture is they hope that proving P=NP and solving some algorithm will give them some magic insight into speeding up some other algorithm that's equivalently hard, rather than working on the algorithm directly. Or, disproving P=NP once and for all, and ensuring the computational assumptions that make people pick algorithms like RSA.
I've been trying to find out if I am the fastest Minesweeper player in the world (a dubious honor at best). My best time on Expert level is 84 seconds. Obviously I can't prove that since no one was there, but can anyone report a lower time?
Ben
FREE WITH the operating system.
So yes it is free.
Just like the prizes in the cereal box is free, right?
It's not really free, you're paying for it by buying the product that it's bundled with.
Not sure if you are just a troll or what, but, have you ever heard of a LINKED LIST?
Why is the universe here? -Well, where else would it be?
Great minds and all that.
If you reduce the minesweep board to a single pair of squares that has a single mine in one or the other then the game would be won or loss with a single click...
This is the equivilant of flipping a coin.
So esentially the article is saying that if you can guess correctly heads or tail with every flip of any coin that you would win $1,000,000.
I am thinking that if you could guess that well that you could win significantly more than that amount of money.
-- Never make a general statement.
Some of our students are very bright, but let's not always see the same hands.
..but still understandable to most.d ollar-minesweeper.htm
http://www.claymath.org/prize_problems/million-
Why is this such a big deal anyway? I'd bet that the only new thing coming out of this is another approximation algorithm, which is nothing new.
Does anyone know the proof or reduction to the venerable 3-SAT for Minesweeper?
I'm new to this P / NP thing, so please don't flame me too bad if I'm a complete retard.
Can you give me another example of a problem that is NP? Factoring a number is definetly a P problem. The algorithm for factoring a number into two pieces is easily done in less than N^(1/2) steps. Doesn't this make it by definition a P solution?
Can someone explain this to me on a slightly lower level?
Thanks,
Captain_Frisk
So, write a program that can decode Minesweeper for any size board, and you will join the pantheon of mathematical greats, alongside Euler and Pythagoras.
Decode it? Does that just mean solve it?
I mean, given a minesweeper board of any size, there could be lots of potential solutions. If this is just a matter of writing a program to find a solution...i.e. unconver a square (the first one is never a mine), and go from there, looking at each surrounding square and the ones near that, etc, etc, etc...in other words, write a program to do what the player is trying to do...well...I don't think that is possible. There are probably lots of cases where such a program would work, but there have been so many times that I've, for instance, come down to a point where there are 2 squares left, 1 mine left, and EITHER ONE of them could be the mine. At that point, it's just a guess. There have been a few times where that foiled my attempt to beat my best time of 60 seconds for expert mode. Since a program cannot truly guess the correct answer every time, then this is not possible. If the program was written with knowledge of the algorithms used to place mines, or somehow actually knew where to look, well, it might be possible then, but it wouldn't be a guess then...that would be cheating.
"It is well that war is so terrible, lest we grow too fond of it."
Time is fun when you're having flies.
-Kermit the Frog
That's totally wrong. You may have just gotten lucky with your first picks. I find that about 20% of the time, my first click will find a mine, and end the game right there.
-
My own time is more like 250 seconds, but my conclusions are the same. There will be no bomb found on the initial move with M$ and some other versions. Only a very few games can be solved with pure logic. It helps if the initial move uncovers a sizeable space with several bombs clearly indicated. Midgame may force one or more guesses, and end game may force a 50 percent, or less probable guess, on four or more spaces.
On the bright side, a cheat of the "easter egg" type does exist. I did not copy or remember it, and forgot the URL in a few minutes.
*gasp*
You ... you .. you BASTARD!
;-)
---
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
Actually you can from the get go. NP-complete is closed under transitivity, so if you find a P solution of an NP-complete problem, you are pretty much done since the composition of two polynomial time reductions is itself polynomial! So, the proof of P=NP could definitely provide a direct solution, just compose the sequence of known reductions.
Since I only have a Master of Technology qualification, and the United States doesn't recognize it, apparently (maybe I'm wrong, I don't know...)
Everything is but a number spoken by itself.
Hence the easiest way to ensure you always win:
100-square board, 99 mines.
Chris Mattern
...was included with windows to give you something to favourably compare the 'bomb' rate to.
Comparisons:
Minesweeper:
- often explodes on the first click
- randomly explodes later on
- game is over quite quickly
- you have to press the reset button to restart
Windows:
- often explodes on the first click
- randomly explodes later on
- game is over quite quickly
- you have to press the reset button to restart
Its the same program!
Therefore- the Stability of Windows is NP complete! QED!
-WolfWithoutAClause
"Gravity is only a theory, not a fact!"Who's right?
Funnily enough, they turn out to be aspects of the same thing.
To solve minesweeper for any size board, you have to place where you think the mines are, then determine if the board is consistent. If it is, you got the mine placement correct. If it isn't, the mines are in the wrong place. This is all explained in the article.
---
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
"History doesn't repeat itself, but it does rhyme." Mark Twain
The article was cool except for this. Every single technology article has to be related to "e-commerce". Commerce this, commerce that. This has nothing to do with freaking COMMERCE! I'm sick of it. Take your stupid money and your stupid analysts and your STUPID EXECUTIVES and get them out of here!
</rant>
TO BUY A NEW CAR WOULD MAKE YOU SEXUALLY ATTRACTIVE.
While it is amusing that minesweeper is NP-complete, at least superficially, the problem of minesweeper consistency certainly seems no easier than the travelling salesman problem.
what about you starting in an area that is completely surrounded by mines?
XXXXX
X434X
X303X
X434X
XXXXX
You click on the 0 to start (numbers may be wrong, sorry). the Xs represent mines. To clear the rest of the board, you have to blindly guess on a square outside your cleared area.
That sounds "unsolvable" to me. So you need blind luck.
NB I realise that this is not the what the article is about.
"This is a problem that has me vexed for a long time" said Harvard Professor of Business, Prof Crack C. Pot. "I hadn't realized that solving this would crack the great P/NP challenge."
"I must admit I haven't thought of it that way before," says Mary Dense Airhead, a travel agent from New York. "I mean doesn't looking through all the routes solve this Travelling Salesman Problem? What is the problem?"
"This definitely a challenging problem," says Joe Smith, a mechanic from New Orleans. "Now I'll redouble my efforts into trying to solve it - I didn't know I could be famous if I tried!"
"Well I don't know," says the famed Computer Scientist from Stanford, Donald Knuth. "Personally, I have always found SAT just as challenging."
It is beyond the scope of this brief news digest to explain what SAT is. Presumably, this is too hard to explain and too esoteric. Why don't you try the Travelling Salesman Problem folks? We could all try a shot at that. After all, it's much easier!
The author of this paper has a web page here:
:)
He also has a page specifically about this Minesweeper business here.
I like the other paper proving that minesweeper, with a little variation, on an infinite board, is Turing-complete. Fun!
---
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
I checked their website, but couldn't find the article online.
you fucking dullard
comeontheni'lltakeyouallon
As with almost any mass media article about mathematics, this article is full of errors that nitpicky people like me feel the need to point out. First of all, some basic info you may be lacking. The basic P vs. NP problem is most simply stated as "P = NP?" P stands for Polynomial time, and NP stands for Nondeterministic Polynomial time, as in you can solve the problem is p(n) steps, where p is a polynomial and n is the size of the input file. Beyond that, some heinous mistakes they made: 1. P is a subset of NP, not a distinct set. Thus all P problems are NP (obviously, if you read the definition). 2. Internet encryption (at least RSA) is NOT KNOWN TO BE EVEN NP-COMPLETE. This is something I think a lot of people don't realize, and I have talked to many mathematicians who think that factorization will eventually be shown to be in P and thus RSA and all other such encryption schemes will collapse. All it takes is one brilliant hacker... 3. The answer has to do with determining consistency, which is very, very different from solving the game in a game theoretical sense. And some slightly more nitpicky issues: 1. NP-Complete problems are those problems whose solutions can be polynomial time transformed to solutions to _any_ other problem. That is why if you find a solution to the minesweeper problem, NP-Complete will cease to exist and P=NP. 2. No serious mathematician believes that P=NP. Anyone who wants to know more should read Sipser's book "Introduction to the Theory of Computation" which I highly recommend.
The best I could dig up was his e-mail address: hins@maths.warwick.ac.uk. The really curious might want to e-mail him.
-m
That is exactly what I did :)
It's difficult to express how I felt when I saw the birds working out the details of moving around and adjusting. Now presumably the birds were not sitting in any particular order ... they were just sitting. So the question becomes: how do we (as humans) build a device that can take arbitrary things and just stick them somewhere without having to find out the details of specifically where it goes, or if there is room. I think that's what I was really getting at -- not so much about how to improve sorting, but how to improve read-write access.
Another brain-bender: is it possible to know the size of a set S without counting it or counting the elements as they are added to the set?
anacron.
MineSweeper is not open-source so we'll never have the solutoin ;-(
--
Density Altitude Not Available
--
delete free(system.gc);
A completely blank board is a consistent Minesweeper configuration, as is a completely covered board.
The subject of the article is not about solving Minesweeper. It's more like debugging Minesweeper. Given a minesweeper board, can you find evidence of a flaw in the Minesweeper program? If the upper left corner of your minesweeper board looked like this:
1 1
1 1
...then you'd know that there was a bug in Minesweeper. If you wrote a program that would analyze arbitrary Minesweeper boards to look for inconsistencies in them, and if your program ran in polynomial time, then you'd be famous and possibly rich.
If it's free, I should be able to download it for free and distribute it freely. So don't say it's free unless you can provide a working link.
Factoring numbers is NOT in NP-complete. It is an NP-hard problem. It's one of those NP problems whose "certificate" is not linear in the size of the input.
to the Millennium Prize Problems page .pdf format)
to Ian Stewart's article on the problem.
to Stephen Cook's mathematical description of the problem (in
to Richard Kaye's Minesweeper Page
Do not taunt Happy Fun Ball.
Unless I'm misremembering my Algorithms class, the kind of factoring technique needed to break public key encryption has never been proven to be NP complete. It may reside solely in P.
What do you mean, you can't prove it? Either P=NP, or P!=NP. If you discover a polynomial-time algorithm to solve a problem which is NP-complete, and you can PROVE it always works and never takes more than polynomial time, then P=NP. Furthermore, the proof that such problem is NP-complete would give you a way to solve any NP problem in polynomial time, so it would be true in practice, not only in theory. This article just says that Minesweeper is NP-complete, which is not a major result.
More details of the maths involved can be found at The ClayMath Institute's webpage and some related papers at R.W.Kaye's webpage
-- Conexant/Rockwell Modem HOWTO http://linuxdoc.org/HOWTO/Conexant+Rockwell-modem
Does that mean that Rabin's probabilistic primality test has kill crypto already? ;)
Compare this to
Posted by CmdrTaco on Wednesday October 20, 1999 at 11:02AM EST
from the now-that-is-cool dept.
Yeah, they're both funny. But not very.
[
Heh, I never could grok Freecell till that one week of 'Advanced NT Server Administration' class way back when.
That Bill Gates will try to claim responsibility for this.
The solution lies in minesweeper.... and no real details..
It could just as easily lie in Freecell.
--Mike--
What, how can you call that a troll? When reading it, I was thinking that I wished I had mod points so I could moderate it up... obviously you didn't understand the point of it. Linked lists do not do what he asked... they do allow you to insert things into the middle of a list, but they do not change the memory locations of any of the other nodes. He wants to be able to insert something into a specific place in memory, and have anything currently in that place be shifted. Presumably that would allow you to have the advantages of linked lists but be rid of most of the disadvantages - it could behave like a resizable array.
There's an idea. An analog memory system that allows for overlaps of data points without data corruption. Build me that and I'll solve your NP vs P problem. That summarizes the original point, and I don't know how you could think a linked list is the solution. Maybe you didn't finish reading his post? In the future, please don't bash something that you don't understand. It's disrespectful and doesn't help anyone.
I think what they said was that the problem was checking to see if a set of clues (the numbers in the squares) was consistent, without knowing where the mines themselves are. Imagine a board that just had all of the squares with numbers in them. That seems like it would take a lot of work to verify. Sounds like it might be equivalent to one of those tiling problems that are common examples of problems in NP.
If you actually stop long enough to look at the game, it can be broken down into logical steps. A friend of mine (who is 15) has beaten minesweeper on Beginner skill in 7 seconds, and it a few minutes can conquer it on expert. I can see the troubles with the minesweeper problem, however. My friend has been in situations with 2 blocks left and neither of us could find any 'clues' to help us figure out the location of the last mine. In retrospect I think it's just impossible, that we had to miss something or the other, but it always lingers in my mind that under certain circumstances there is not enough information provided by the game to solve it right. Giving up all the Microsoft-bad-coding-practices crap, I believe the game was designed to be able to be beaten no matter what. They proclaim that every game of solitaire can be beaten, which as I think about it is also a sort of "NP" problem. If I knew how to program decently, I think I know enough about the game to write a "solving program" for it.
---
I read somewhere that if you played perfectly, you could win at Minesweeper almost every time. Is this true? Does it require a certain number of squares to be uncovered before this theory kicks in?
And just curious, what is everyone's (non-cheating) high score at expert level?
Reality has a liberal bias
Personally, I kinda prefer mahjongg or tetris tho ;)
I hope you mean mahjongg and not one of those patience games that uses the same tiles... not the same thing at all.
"don't fall into the fallacy of believing that Perl can solve social problems. Maybe Perl 6 can, but that's a ways off"
and the issue isn't about PLAYing minesweeper - but deciding whether a particular position is self-consistant - a whole different thing
not possible with Windows minesweeper - for a map H high by W wide, you can only have a maximum of (H-1)*(W-1) mines and a minimum of 10 mines.
Sorry...
-Karl
[root@kgutwin
msdos.sys: fsav (linux) virus (17518-87)
I see now... Minesweeper is the enemy of encryption. This just goes to show that Windows really is a security risk. (As if we needed more proof of that...)
--
Feminism is the wild notion that women are human beings.
A much more detailed story is found at The Clay Mathematics Institute Website
"Tomorrow's forecast: a few sprinkles of genius with a chance of doom!" - Stewie Griffin
I've always thought that one of the problems with math -- as taught at the secondary level -- was that you didn't actually learn any abstract math skills (well, you might, but you're not taught them). Just more algebraic manipulation, or, if you're luck, the foundations of calc.
I think games and optimization problems, though, could provide a fertile and interesting framework for teaching real mathematical thinking. Minesweeper. Knight's Tours. John Conway's games. Nim. Dominoes. Any small, discrete system with definable rules can get you thinking mathematically, though most people probably just play with heuristics....
Libertarianism is rich wolves and poor sheep playing gambler's ruin for dinner.
Actually part of proving a problem is NP complete is reducing it to another NP complete problem by showing how to encode the problem as another type of problem, and subsequently decode the answer. Hence, if you find the polynomial solution to minesweeper, just use the chain of encodings used to prove the NP completeness and you have a polynomial solution.
The Cure of the ills of Democracy is more Democracy.
Erlang Developer and podcaster
This is old hat. I read about it a couple months ago. Tell me something I don't already know.
Solve this one with a program, if you can...
111111
2*33*2
3*??*3
2*33*2
111111
Which '?' has the mine..... and remember NO GUESSING ALLOWED
sig. "I didn't do it."
`This is already enough... (0 marks yet unknown positions) 3?000... ??000... 00000... 00000... . . . So what?
Fight hunger. Filet a politician and send him to a 3rd world country of your choice.
3?000...
...
??000...
00000...
00000...
what next?
Fight hunger. Filet a politician and send him to a 3rd world country of your choice.
Now we finally know what a Microsoft Certified Professional (MCP) degree is good for. These people know how to determine whether a MineSweeper layout is consistent.
;-)
Is there an equivalent problem for the Solitaire Expert?
-- ESH
I did a search on boston.com for "minesweeper" and turned up nothing. Does anyone know the exact URL for the story?
--
--
I don't want to rule the world... I just want to be in charge of mayonnaise.
Ted
Now we know what Tron was *really* all about. It all makes so much sense!
---
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
hmm... looks like this article has been reposted on slashdot before... http://slashdot.org/articles/00/10/10/1222226.shtm l
Contrary to popular belief, minesweeper is not that difficult of a game to solve, but only after you have found your first mine. Up until that point, you HAVE to guess. the game, however, does not draw the board until after your first move, as your first move will ALWAYS be safe. However, unless your first move hits a spot that has no mines surrounding it, your next move will HAVE to be a lucky guess. However, once you have reached a certain point, like after successfully rooting out about 5 mines, the solution becomes pretty much a linear problem based upon the number of grids on the board.
There are a few "traps" however. Ones I have learned to avoid by always cleaning out the corners first on a large board. If I die, I want it to happen in the first few seconds and not on the last grid I'm trying to clear.
Encryption, as far as I've been able to deduce, does not allow for this strategy. While I know that it might take 2^56/2 average brute force comparisons to extract a DES key, there is no plateau I know of, say at 2^10 comparisons where I can safely say that the problem becomes a linear problem rather than an exponential one.
Take for instance a 10x10 minesweeper board. If I simply wanted to brute force out a solution, I have 2^100 possibilities (yes, this makes encryption look tame by comparison). However, we can break this problem down significantly without even knowing any tricks. Take a board. Guess at a grid. If the grid is clear, we go onto the next one, if the grid is occupied by a mine, we will know this instantly as well. This problem still has 2^100 possibilities IF the game restarts each time you die and you get a fresh board. HOWEVER, if the board remains the same, you have only 200 possibilities total and you will have the board complete. I can't do this with encryption. I can't guess at each bit of a key indifidualally to determine if it is right or wrong. If I could, then DES could be solved with no more than 112 instructions. And even 128 bit encryption would take no more than 256 iterations.
But minesweeper isn't that difficult. There are very few boards (especially on the 10x10 grid) that can't be solved with a predicable algorithm. While it is not possible to know with certainty if EACH grid location is definitely a mine or definitely not a mine, you are about 99% likely to know at least ONE of them at any one time, after the initial 2-3 guesses. This is better than we have for encryption, but still falls short of the rule as we need to be 100% sure for ANY board.
Encryption does not suffer. Even if for an encryption scheme with 2^N possibilities, I would be able to determine an absolute solution in less than 2^(N/10) possibilities, for DES this would be about 32 possibilities, the problem can be made more complex simply by increasing the bitsize of the key. A key with 1024 bits would, with this method, require 2^102 possibilities which is still out of the range of today's computers, or even tomorrow's.
-Restil
Play with my webcams and lights here
Sure if you find a P solution to an NP-complete problem, you're all set. But I'm allowing that some genious might find a quirky way to prove P=NP without actually showing that any particular NP complete problem can be solved in P time. Similar to how the pigeonhole theorem can tell you that there must be two people in New York with the exact same number of hairs on their heads, but it doesn't tell you which two.
Nope.
You're still PAYING for it, because you don't get it unless you pay the price.
You're paying less for the cereal.
You think the boxes are free too?
Besides P = NP for N = 1 (:-).
One day I swapped the bitmaps for the 3 and 4. About a week later, he was playing it while he was on the phone. When he hung up, he freaked out. He was convinced there was a bug in Minesweeper. He even said "there's no way you guys did this one." We managed to last about 5 minutes before we were laughing our asses off.
Check out http://www-inst.eecs.berkeley.edu/~cs70 I'm taking it now -- it's a great class. willis/
there is no thing
what else could you want?
There are better ways to achieve that.
The previous post should be moded up +1 Insightful, please take this step or I will be forced to sue, thank you...
Okay, so there's a journal article which discusses a problem contained within Minesweeper. In order for this to be interesting, he would have had to prove the problem NP-complete and provide a polynomial time solution for it. As far as we know he did neither. The gist of the article is, "There's a theoretical problem in Minesweeper, and gosh, isn't the P=?NP question interesting?"
Furthermore, even if a proof that P==NP were handed down by God encryption wouldn't become useless. Most of the fundamental problems in encryption are not provably NP-complete.
/* The beatings will continue until morale improves. */
It's Very challenging. I do it as a hobby, and currently have some amazing scores for it. Currently, I have a low of 107 for the regular level, with an 82 on my favorite level, crossed squares. It took me approx 4 months of solid play to get the 149 on Diamond, it's REALLY hard.
You can find the author, Bojan Urosevic's original web site. It's shareware, but I highly recommend you purchase it because it's such a great game.
--
Gonzo Granzeau
Gonzo Granzeau
"Nothing the god of biomechanics wouldn't let you into heaven for.." -Roy Batty
This article is mainly publicity - no realbreakthrough - which is okay if you want to inform the public about P vs. NP problems. Unfortunately, to the average reader of the article it would appear that there has been a new development just because someone has shown minesweeper to be equivalent to other known NP problems. The key to proving P=NP or P!=NP does not lie in the game minesweeper anymore than it lies in any of the many other known NP problems. The only real news here is that a problem stated in terms familiar to minesweeper players is an NP problem. Ho hum.
The first square chosen MUST be random. There are no clues as to what may lie under the first square clicked.
Not quite true, since Minesweeper will simply not allow you to click on a mine on your first attempt. It'll highlight the square when you click on it but it'll refuse to uncover it.
Still doesn't mean squat since your first click might be completely useless (just one "1" uncovered, nothing else), so once you again you're up shit creek without a paddle.
I have always concidered the factoring issue to be kind of misleading. Yes, the composite number can be retrieved from the public key, and assuming you could quickly generate a list of the factors, all you would have to do then is try each one of the factors to create a test key and try it. Some encryption programs such as PGP are even nice enough to provide a CRC to tell you if you got it right.
But concidering the time it would take to factor the composite number, and the number of factors that could potentially exist, would this really be faster than a smart brute force known / guessed message attack? Using PGP 2.6 as an example, it uses public key RSA to encrypt a session key and other settings type information for a stream cipher. The data structure of this information is well known, and several field have limited legal values, creating bits of the message that can be known. We already know who the message was intended for and assuming their public key is well published such that we can acquire a copy of it, then we have the tools needed to encrypt test messages to see if they match the final encrypted original message. Using the number of bits that end up matching the original we can potentially use that as feedback to determine which message bits contain the correct bits or not and try setting different bits. I may be missing a fundamental characteristic of modular arithmetic, but it would seem to me that such a smart brute force attack could be done in N-bit squared or cubed time rather than the reported 2 to the N-Bit power time.
If this will work, it is not an instantaneous solution, but it would greatly reduce the required work needed to crack a message.
then why, when I use xyzzy (mentioned above by yours truly), do I apparently have a valid minefield before I've even clicked? I've tried flagging bombs before I click a spot, and the squares indicated as bombs remain so after I start opening up the ones indicated as not being bombs. Then it's easy to beat 100 sec on expert, but then, that's why it's cheating to use it. Then again, it never seems to "see" all of the bombs that there are supposed to be on the field before I start. For example, with begginger level, and only 10 bombs, it's pretty easy to be sure that you got everything the cheat was telling you about, but there's usually only 8 indicated, and, just like I said in my previous post, if your first click is on one indicated as having a bomb, there are 3 places that "turn out" to be bombs that were previously indicated as not being them. whether or not this is actually not determined until the first click, or this is a flaw deliberately built into xyzzy, I have no idea.
Nope the prize is free. You pay for the cereal. The toy is a bonus. The price for the cereal is the same whether there is something extra in the box or not.
It really is possible to win at Minesweeper by defining and solving sets of simultaneous linear binary equations. I wasn't pulling your leg, and I wasn't bragging.
The solution is too simple to mention. I suppose that anyone who knows how to solve simultaneous equations would be able to solve them when the numerical base is binary.
I assume that whatever mathematical problem they are discussing actually has nothing to do with winning at Minesweeper.
20 percent of the people in the world don't have enough to eat. So, winning at Minesweeper hasn't seemed like an important pursuit to me. I discovered that it was possible to write binary equations that show where the mine cannot be. I presume many other people have discovered the same thing.
Actually, any NP problem can be reduced in polynomial time to any NP-complete problem. Solving any NP-complete problem in polynomial time proves that every problem in NP is in P.
The basic idea is, given the current displayed numbers and the number of remaining mines, generate all possible patterns of mines in the adjacent undisplayed squares and then figure out the probability that each undisplayed square has a mine. I am not sure I follow what I was doing, but I thought some might find it amusing.
*************
SOLUTION FOR MINESWEEPER
1. Read in minefield and translate into a code where each square is assigned a number between 0 and 10, with 0 through 8 representing the displayed number of adjacent mines, 9 representing an unknown square and 10 representing a displayed mine.
2. Iterate through each square in minefield (indexes: [x][y]). If such square has a value of 0 through 8, save value of square in nNetAdjMines and test adjacent squares for "unknowns" (indexes: [c][r]). If an unknown is detected, (i) increment nAdjUnk, (ii) increment AdjUnkTable[c][r] and (iii) add a [c][r] node to pointer in KnownTable[x][y]. If a mine is detected, decrement nNetAdjMines. If nNetAdjMines>nAdjUnk, an error has occurred. If nNetAdjMines==nAdjUnk, then all unknowns for square [x][y] are mines; in such case, add [x][y] to minelist, and, after processing the entire minefield, reveal all mines on minelist and go to step 1.
3. Count all known, non-mine elements of KnownTable (nAK). Create array of nAK pointer elements (KnownArray). For each known, non-mine element of KnownTable, set a pointer in KnownArray to such element.
4. Count all non-zero elements of AdjUnkTable (nAU). Create array of nAU integers (AdjUnkArray). For each non-zero element of AdjUnkTable, reset the pointers in the linked list of each element of KnownArray to point to the corresponding element of AdjUnkArray.
5. Place each possible binary pattern of mines/non-mines in AdjUnkArray. If more mines are used than available, junk pattern right off the bat.
6. Test each such pattern by checking whether, for each element of KnownArray, the sum of the dereferenced pointers on the linked list equals nNetAdjMine. If it does, then call FinalArray(x,y,nMines), which, for a [x][y] square, increments a counter of an element in an array (CountArray) which indicates, for a given number of mines contained in AdjUnk squares (nMines), the number of patterns in which [x][y] would contain a mine.
7. For each KnownArray element, a "Factor" (equal to the number of different patterns that could be made by placing totMines-nMines mines in the non-adjacent unknowns) is applied to each CountArray element to account for the relative numbers of occurrences of the different nMines. The Factored counts are added for each CountArray element for such KnownArray member and the totals are divided by the total number of all possible patterns.
8. The relative probabilities that each unknown is a mine is displayed and/or the least probably unknown is selected. All unknowns having a 0% chance of being a mine are selected and all unknowns having a 100% chance are flagged as mines.
You're confusing nondeterminism with randomness. They are NOT the same thing. Nondeterministic algorithms do not involve "guessing" at all. To prove that a problem is in NP you have to show that any solution can be verified in polynomial time. That's it. I recommend Sipser's book for a superior explanation of the topic. Taking his class is even better.
*grin*
--Fesh
"Citizens have rights. Consumers only have wallets." - gilroy
--Fesh
Kill -9 'em all, let root@localhost sort 'em out.
You are wrong ... first problem with your argument is that the number n would be given in binary ... and by applying blum's speedup theorem to this arguement ... it would be possible to colaspe the 100 to an arbitary number say 2. Theory kicks gnads.
Okay, I've read your other posts. I see your point about most of these posts having the wrong idea. However, could you please clarify what a P problem would be? Would that be one which is O(n^x) where x is any constant, and n is a parameter for the problem? For example, if this could be solved in O((length_of_board*width_of_board)^20) is that a P problem?
Surely there must be a better way to check consistancy than a brute force check of all mine positions possible in the unmarked squares. I think I have a new hobby now...
It may look like I'm doing nothing, but I'm actively waiting for my problems to go away.
--Scott Adams
I'm sure it's just that I haven't read enough comments to find someone else whose clarified this.
The actual GAME of minesweeper IS NOT NP Complete!!
Given a particular minesweeper board, except for times where no logical decision is possible, the game is COMPLETELY deterministic (you use deduction to figure out which box you click next). The "guessing" involved in NP is NOT the same as the guessing you do with the lack of information provided in some Minesweeper boards.
What *IS* NP complete is the CONSISTANCY of the Minesweeper board. Ie. Given a minesweeper configuration, is a solution POSSIBLE.
For example, a board with a 9 would be inconsistant because it can't possibly have 9 bombs around it. Likewise, a square with a 2, and all but one square uncovered would be inconsistant.
In short: Solving the game is not the problem. The problem is: Given a board, without making any more moves, is it possible that a solution exists.
That problem is NP-complete.
You can verify this using the xyzzy cheat documented in the Jargon File. If you're not familiar with it, it turns the a small area at the upper left of the screen either black or white depending on whether the mouse pointer is over a bomb or not. It doesn't exist in some versions of windows, but I happen to use one that does, on occasion, and if your first click is on a square indicated as a bomb it won't be anymore. I don't know whether the game completely regenerates the board or just randomly picks a different square that was previously bomb-free to replace it, however.
If you like mahjongg, check out xshisen. Slightly simpler, very addictive. ;)
http://www.techfirm.co.jp/~masaoki/xshisen.html
Ya see, GC has puzzled mathematicians for 258 years because it's easy to "see" relationships immediately, but each of them is difficult to prove. Once proof is offered, it will be easy to verify, much easier than Fermat's 150pg proof, just like P=NP solutions are quickly verified.
GC lends well to P=NP, because finding composite numbers (non-prime) is a classic example of one of those tasks that requires checking through every permutation. Minesweeper is a pattern-matching exercise that is not far from finding which prime patterns (twins, quartets) are workable and which are invalidated by congruencies (modulas) of other primes.
On my way to solving GC, I think I accidentally proved both the Hardy-Littlewood conjectures, and thus disproved the disproof against them! :-D
MOD THE CHILD UP!
Could then use it to predict the stock market?
hmmmm... where's my drill
E.
Build Your Own PVR/HTPC news, reviews, &
MSCE = Minesweeper Competent Solitaire Expert. I have sat through some of the classes (NT 4.0 Core, MS-SQL Server 7.0 Admin, etc) and yes, I have become a minesweeper and solitaire expert. So, we have plenty of people such as myself that have had training in these complex programs, since we had to do something while the instructor blabbered on about some corny jokes to try to liven up the classes. I'm not MCSE certified, but I am pretty damn good when it comes to solitaire and minesweeper. I have been improving on my freecell skills, and I have already mastered the pinball game that comes with NT. WOOHOO!
Mas vale cholo, que mal acompañado.
Consider the following situation, against the top edge of the board:
--------
01?10
13?31
1***1
12321
In my experience, this usually happens around the edge of the board, but there are times when it will happen smack dab in the middle as well.
It may look like I'm doing nothing, but I'm actively waiting for my problems to go away.
--Scott Adams
Unfortunately, this is not the minesweeper solving problem. It is the minesweeper consistency solving problem. 2 correct examples of the consistency problem:
X = MINE
O = COVERED EMPTY
NUMBER = BOARD CLUE
1 X
X X
The correct analysis of this board would be 'inconsistent'.
2 X
X O
The correct analysis of this board would be consistent.
The minesweeper consistency problem is a matter of checking the board and being able to declare whether or not the board is correct in all of its details.
The challenge is to construct a program which will process all generalized minesweeper boards and declare them correct/incorrect (accurately) in P. IF you can write such a program, then NP=P.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
RSA is only NP, or at least nobody's proven it to be NP-Complete yet.
Any NP-Complete problem can be transformed into any other NP-Complete problem via a polynomial time transformation. Thus, solving one solves all. I have no idea how to do it, it's over my head. But it can be done.
Anyway, more to the point, this isn't about Minesweeper, it's a problem called the "MineSweeper Consistentcy Problem" and it's important to remember that. Essentially, the MCP is: given a half finished minesweeper board, is it consistent? That is, is it a valid board within the rules of the game? It is possible to get this board through normal play?
That's a bit of a different beast than just playing the game, guys.
---
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
(plus Kuro5hin readers wisely voted this story section only, probably where it belongs)
--Robert
Arg! Do you realize what you've just done?
... Must... resist... attractive... problem...
This is just like the time a co-worker asked me to determine what the set of all points equidistant from a point and a line in 3 space is. Hours of work were lost (because you can't stop with a point and a line, no, you've got to do point-plane, line-plane, and then think about 4 space). All.... CPU Cycles... being... consumed
Plus, now Slashdot is simply going to lose everybody who makes quality posts. They'll be too busy writing their own java apps for "programmer's mineswepper" (no I'm not going to give you the URL). Slashdot will become a banal wasteland of first posts, trolls, and karma whores....
(oh, wait...)
Libertarianism is rich wolves and poor sheep playing gambler's ruin for dinner.
Huh?
Not so, unless I'm missing something. Take, for example, the 2-space equivalent of what he's talking about: the set of all points equidistant from a line and a point. This is a parabola. A point and a line qualify as subspaces of a plane, but a parabola ain't a single point (ever, I think).
In three space, the point-line thing becomes a parabolic cylinder, and so does the line-plane (I think). The point-plane is a parabolic dish, like you'd use for a satellite receiver. Four space... sigh. No idea.
Tweet, tweet.
I thought of a similar problem recently while driving along. There was a bunch of birds sitting on a telephone wire. It was pretty much a whole flock. A new bird would come along and sit on the wire, and if there wasn't room where he wanted to sit, he sat anyway -- the birds around him would shift appropriately, but it all happened so well.
... you want to put something in a particular location, you just place it there, and the "things" around it shift a little
.. the birds on the end of the wire don't have to shift at all. I want to be able to sort lists the same way --- it'd be much faster. Sure there's a physical limit to the number of birds that can be on the wire ... but remember that they can overlap a bit.
Extrapolate: Take the birds on a wire problem and turn it into a sorting problem. Given n things, put them in order. The problem with comptuters is that everything is digital. It wouldn't be possible to move the elements of a semi-sorted list down a little -- you always have to shift them by some number of spaces.
I think the NP problem could be more easily solved if there was some analog way to do things like sort a list. Think of it
The birds on the wire closest to the new bird have to shift the most
There's an idea. An analog memory system that allows for overlaps of data points without data corruption. Build me that and I'll solve your NP vs P problem.
anacron.
int known[][];
/* repeat for other edges */
int fuzz[][];
for (y = 0; y Y; y++) {
for (x = 0; x X; x++) {
if (board[x][y] == MINE) {
known[x - 1][y]++;
} else if (board[x][y] == COVERED) {
fuzz[edg][es]++;
}
}
}
now another n^2 loop to verify board[x][y] is between known[x][y] and known[x][y]+fuzz[x][y]
if so, board is consistent, if not, board is inconsistent. O(n^2).
That's not the whole problem, because that solution is far too easy. The fuzz[][] array is not entirely correct, since it would be possible to have:
XX10
2#20
0000
which is obviously NOT consistent, but would fuzz to be so with the above code. It would be another n^2 loop to determine that unknown is not a mine, but there would be cases where you couldn't establish it so easily, I'm sure, I just can't think of one right now.
A probablistic solution would be pretty simple, though.
--
bje
As a practical matter, solving the TSP is really easy.
-
1. Link all the nodes into some random order.
-
2. Pick two different links at random, cutting the chain into three chains.
-
3. Try all the possible ways the three chains can be reassembled. Keep the one with the shortest distance.
-
4. Repeat steps 2..3 until no improvement has been observed for a while.
This algorithm was developed at Bell Labs in the 1960s. It usually converges on the optimal solution quite quickly. Since the discovery of that algorithm, other semi-random algorithms have been discovered for related problems. This has made a big dent in some useful classes of tough problems.Ha, that will be a funny subject to see the next time I comment.
Without doing any more calculations, don't forget a 1000 bit number is really huge and you've got to basically factor against all 32 bit integers (2^32 * 2^32 = 2^1000ish). The problem with factoring problems is no matter how fast you search, you will reach your asymtote(sp?) where you just don't want to wait any more. This is because, even with a perfect brute force algorithm, you've still got to check on average 1 in 17 numbers. Once you get a good sized key, that's a LOT of computations.
Tell you what, give me a 40 bit key and a 56 bit key and I'll give you the pieces and the runtimes as proof by example.
Planning to be moderated ± 1: Bad Pun.
Do not support these criminals!
NightHawk
Tyranny =Gov. choosing how much power to give the People.
It is possible to win at Minesweeper by defining and solving sets of simultaneous linear binary equations.
Like the space war "simulation" in Ender's game, minesweeper is really just a distributed decryption tool... it makes all the unproductive workers productive!
There is a fine line between being a cultivated citizen and being someone else's crop. - A. J. Patrick Liszkie
This is fundamentally insolvable.
Consider a game board of any size, but in the upper-left hand corner, there sit four boxes:
[][]
[][]
If row 1, column 2; row 2 column 1; and row 2, column 2 are all mines, the four boxes look like this:
[]##
####
No data is known about row 1, column 1. Therefore, 2 possible solutions exist.
Extrapolate this, assuming similar situations on a game board consisting of billions of rows and columns, and an astronomical number of possible solutions begin to emerge.
Which, of course, is the whole problem with encryption. There are just too many possible answers (depending on key strength, etc).
In short, yes, maybe minesweeper does have something to do with encryption. However, it won't be offering solutions any time soon.
--M McCormick, Northwestern University
---sig---
I think I broke through the 120 barrier. IIRC, my best is 114. God knows how I did it though. I think it happened at about 2:30 in the morning, and my eyes had dried out. Since I was unable to blink, there was a greater percentage of the time that I was looking at the board.
I think I remember a competition on my floor in residence where the best time was 97. No telling if that was without cheating though...
It may look like I'm doing nothing, but I'm actively waiting for my problems to go away.
--Scott Adams
When I was an undergraduate, I wrote a program that would detect whether a particular move in Minesweeper was safe. It used a recursive search, and couldn't detect safe moves in certain late-game situations where the mine count was relevant, but its play was otherwise perfect.
Since the program could definitively tell whether or not a move was safe, it could detect when a player was *GUESSING*. And so we could hack the program to always reveal a mine in such cases, driving the game weenies insane. :-)
Okay, we never built the search into the game, but we did hack Tetris in a few irritating ways... (As I understand it, Tetris is a lost game anyway: with probability 1, if you play long enough, you will lose, no matter your speed or strategy.)
Well if it doesnt let you hit a mine the first time there is a chance that you could solve the game without even uncovering a block.
If you read the details, you don't have to solve minesweeper, you have to be able to check if the board is self consistent or not.
Ie:
2 MINE
MINE BLANK
is a self consistent board while:
2 BLANK
BLANK BLANK
is not.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
I'm imaginging writing a program to win minesweeper--the rules to play by are fairly clear (how to tell if certain squares are bombs not). The a program could very easily play by the same rules I do--only much much faster. And as some people have stated, no matter how good you are there are certain times where you are required to make a guess--again something a computer can do quickly. So I can very easily comprehend writing a program that in a fraction of seconds either wins or loses--if it loses, it plays again until it wins. I'm a pretty weak programmer and I think I could create such a program.
But this is basically just a rework and (slight) refinement of the brute force methods.
The problem in this is that in encryption, there is no indication of how close you are--like the numbers 1-8 indicate in minsweep. Is this what they're talking about and are looking for, uncovering some indication about quicker paths to take and eliminate unnecessary steps (like when a square has a 1 and you already know for certain of 1 bomb touching it so you can very quickly click all of the other open squares around the 1 square). This I what I don't get--how the encryption will provide any sort of feedback as to likely directions to go. And if it does, it seems like it would require a flaw of some sort.
Vote Quimby.
And, of course, there is that million-dollar prize. One question, though: wouldn't this be as simple as modifying basic human behavior? Would the first square be random (the only real option you have)? From there, solving the game is relatively easy, and a computer would be able to do it in a heartbeat.
- I don't care if they globalize against free speech. All my best free thoughts are done in my head.
Please note that if a solution to the minesweeper problem IS found that it demonstrates only that SOME solution will can be found for all NP problems.
.gif on a website or embeded in something as inocuous as a laundry list, and when decoded will be in 'code' anyway, such as " The eagle flies at midnight,' for which an actual key code is inherently neccessary.
It will not only NOT mean that the solution to all NP problems has been found, but it will NOT mean that a solution to any * particular* NP problem, other than minesweeper, has been found.
It will simply mean that a solution to any NP problem is * theortically findable.*
Finding the solutions to an *actual* NP problem is left as an exercise to the student, or FBI.
If NP problems do, in fact, prove to be solvable it will have an enormous impact on mainstream encryption of data transmission because such depends on having a *single,* or at least very small group, of encryption methods shared jointly by all.
Crack it once and you're into the whole system.
That be bad.
For the 'nefarious' types it won't have much impact at all, because such will be using multiple layers of multiple encryption techniques. The encrypted data will itself be hidden in non obvious places, like embeded in a minor
To sum up, if the NP problem is solvable electronic money transfers and your e-mail are inherently insecure, but terrorists, at least the smart ones, still will be.
That won't stop the FBI from playing the terrorist card to snoop YOUR e-mail though.
The problem is not solving minesweeper, it is checking the board for consistency, see some of my comments elsewhere.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
Actually, that's not the point. The problem is that your algorithm is recursive and scales very poorly. The point of the article was to find a way to solve NP problems in a a way that's similar to P problems. In order to solve the problem the way you are doing it, the computer has to brute force it, by looking at ALL the data. The challenge is to find a way to do it that doesn't involve traversing every path, which hasn't been solved yet, but will need to be solved yet. Many algorithms, are brute forcing things, and will fail to scale. Some examples are designing the fastest route through the internet so that traffic can be routed in the quickest way possible. Using the brute force approach of testing all possible paths, will not scale, and will eventually slow things such as the internet to a crawl as the number of paths increases.
have you considered the possibility that you might be the antichrist? you should be worried.
In Capitalist America, bank robs you!
...comes into play?
NP means that a solution to a problem can be checked in polynomial time, making it possible to bruteforce the solution. NP complete means that there is no deterministic algorithm to find such solution in polynomial time. Factoring numbers is approximately O(n^0.5) divides; simply divide the number n that you want to factor by all primes less than or equal to sqrt(n).
Will I retire or break 10K?
Or for those of us who are linux-heads, the answer can be found in gnomine (gnome) or kmines (kde).
So.... does this mean all I have to do to break any encryption is type "XYZZY"?
Any sufficiently advanced civilization is indistinguishable from Gods.
Actually, even if the exponent is large, it gives
us hope. I think you fail to see the difference
between exponential functions and large degree
polynomials. Given many processors, we can break
an O(x^n) into an O(x^k) problem where k n.
Parallel programming doesn't really help at
all for exponential problems.
In a nutshell, using many parallel processors,
we can lesson the degree of O(x^n) algos.
No hope of this for O(2^x) algos.
--wayne
Aha. That's a good, simple problem description... given a board where each square has either a number or a bomb in it, verify its consistency. Nothing to do with playing or solving the game itself. Thanks, rasbora.
Hey! Rather than fighting back and forth on this issue why don't you all try downloading my contribution! :-) I wrote an implementation of minesweeper that plays itself and tells you if you have to guess or not. You need GTK+ 1.2.3 (or later) and a thread library. Get it at mindsweeper.tgz
By the way: testing 1 million 30x16 games with 100 mines shows that 87.12% of all games require you to guess. So "NO", you cannot always solve minesweeper... not even close.
Isn't it? What am I missing?
www.HearMySoulSpeak.com
Dumb question, but couldn't a really, really, really fast monkey with a calculator theoretically take a 1000 bit number and start at 1 and work his way up, checking if each is a factor? If he was fast enough, he could do it in a second.
-Erik
I have discovered an amazing solution to the Minesweeper P=NP problem which unfortunately will not fit into this margin, but I am willing to accept venture captial in the meantime.
maybe the real secret to running windows successfully is being able to locate all those "trouble" areas just like you can find those "bombs" in the game. i guess, one could also say they are similar, throw everything you can at windows (like clicking randomly in minesweeper) and sooner or later... the games over. reboot.
Nice theory, no details, so I have a pretty good idea of what they are talking about. You analyze the numbers and use the patterns that numbers form to seek similar patterns in foward moves. Of course, the article makes it sound a lot dumber than that...
Eh...
Not quite true, since Minesweeper will simply not allow you to click on a mine on your first attempt. It'll highlight the square when you click on it but it'll refuse to uncover it.
;)
In MS Minesweeper it works like this: if you hit a mine on your first click that mine is moved to the top left square, and if that one is occupied it ends up in the square to the right of it and so on. (this is actually good to know when you get a situation where you have to make a guess up in that corner
They described (with pictures) how this Minesweeper thing works, something about OR gates ... possible and impossible configurations ... much more informative than boston.com's article. However, I don't have the magazine ...
Umm. Last I checked, factoring co-primes was not NP. Can anyone else back me up on that?
Well, if you measure N in terms of the magnitude of the number, it's polynomial. However when people say factoring is NP, they mean that it is NP in the number of digits.
...that Peter Schor came up with a quantum computing algorithm which factors large numbers in polynomial time, back in *1994*? For that reason, RSA encryption should be looked upon as insecure if being used to protect data for more than, say, five years. As soon as they build a quantum computer, RSA is effectively worthless. Sure it would be nice to have a P-class algorithm to run on a regular computer too, but that's beside the point if the cat is already effectively out of the bag. (For those suggesting that very very fast massively parallel computers can be used to factor v. large numbers, remember that adding a single decimal digit to the key increases the computational effort required to factor it by orders of magnitude.)
These sigs are more interesting tha
The first square chosen MUST be random. There are no clues as to what may lie under the first square clicked. This implies that there is always *some* chance that even an otherwise perfect algorythm may fail.
IMHO this implies that the analogy of minesweeper to P vs NP is a very good choice.
std::disclaimer<std::legalese> sig=new std::disclaimer; sig->dump(); delete sig;
And those who get caught screwing around on company time can tell their bosses, "I was just evaluating our encryption strategy."
"I call a baby goat a 'goatse.'" -- my non-Internet-savvy 6-year-old stepdaughter
The point of P/NP in crypto is that certain problems (such as the knapsack, or factoring large numbers, and such) are not proveably harder than other problems. Proving that P = NP would mean that there is a solution to the knapsack, and factoring large numbers, and so on, that is not demonstrably harder than solutions to much simpler problems. But it won't tell you what those solutions are. People have been searching for solutions to these NP (hard) problems for a long time... the fact that the solutions might make the problem quicker to solve doesn't make the solution any easier to find.
The NP problem is:
Given a grid of numbers determine whether the grid could form a valid minesweeper board.
Its easier to think of the problem as supplying a set of mines that are consistent with the given layout. This makes the P algorithm for checking a solution:
Is the board for this set of mines the same as the board under test?
Special Relativity: The person in the other queue thinks yours is moving faster.
Actually, I've heard of theorists working to prove that P=NP is unprovable (given a particular framework for proof). That was years ago, and I haven't seen anyone beating down their door to hand out awards, so I can only assume that these attempts have been a futile as attempts to decide the actual problem.
Anyone know what's going on with this kind of work these days?
When I was completing my honours year in Computer Science, the undergraduates spent a lot of time playing a multiplayer unix tetris game, where your own tetris board was displayed alongside that of the other players. If you made two or more rows at once, all the other players received a row of garbage blocks on top of their current boards.
Some of the other post-grads got the client source, and made a bot-player that would play for half a minute, then flood the other players, reporting that it had made lots of multiple rows.
Another time we made a hacked client that always gave the long skinny tetris peice whenever there was a need for one, and you could press a key to change the falling shape to another peice.
Thought we might get the sysadmin dudes irate for "hacking" a program on the system, but were actually encouraged to disrupt any undergrads wasting time (and spare terminals) in the computer labs.
Why is the universe here? -Well, where else would it be?
Simple, either reverse engineer minesweeper or buy the source code from the creator. Then write a program that searches for a running copy of minesweeper. Have it look at the memory the game is using, find the representation of the game grid and extract the locations of the mines. If coded right it will work everytime.
Ok, this is probably considered cheating but for a cool $1,000,000 it might be worth it!
The simple truth of the problem is that there is no one answer to it...
Not many people have a firm grasp of what this problem is really all about. Sure, you'll study it in your B.Sc or B.Tech...but really, even graduates fail to grasp some key concepts, although they study the tougher concepts....basically, this is how it goes:P is the set of problems that can be solved in deterministic polynomial time. That means for a problem with inputs of size N, there must be some way to solve the problem in F(N) steps for some polynomial F. F can be any polynomial, even N to the 10 millionth power.
NP is the set of problems you can solve in non-deterministic polynomial time. That means for a problem with inputs of size N, there must be some way to solve the problem in F(N) steps for some polynomial F just as before. In NP, however, the student is allowed to make lucky guesses, though it must prove the solution is correct. The standard format for a program in NP is: Guess the answer. Verify that the answer is correct in polynomial time. For example, factoring is in NP. Suppose you have a number A that you want to break into two factors. The NP program is: Guess factors P and Q. Multiply P times Q and verify that the results is A. This takes only two non-deterministic steps so the problem is in NP. Therefore, considering the differences between the two and the estimation involved, how is it possible to prove something like this?You can't "prove this". You can't disprove it either, but that's not the point - minesweeper is not going to help you with this.
Everything is but a number spoken by itself.
Yea, this is the problem they tell young researchers not to delve into. It is the Grendel of Mathematics, a lurking monster that crushes GAs in its jaws. Whenever you work on NP problems, never think about proving NP!=P or P=NP. Don't even consider trying to prove that it is unprovable. Stay away from this kind of thinking. Go study something harmless, like Godel's proof. Havent You People Seen PI???
So now I can walk up to people who don't grok minesweeper and say "Your NP matrix sucks".
Expect alot of dumb looks.
-Billco, Fnarg.com
Wrong. It would do nothing of the kind. Proving Riemann's Zeta hypothesis would do that.
Even if you proved prime factorization of large numbers can be done in polynomial time, you would need an algorithm that accomplished it in a reasonable amount of time (seconds). An algorithm that had time complexity O(n^100) would still be polynomial, but useless in practice.
paulb
Paul Bettner
Game Developer et al