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 ;)
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.
...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!""History doesn't repeat itself, but it does rhyme." Mark Twain
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.
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.
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
and the issue isn't about PLAYing minesweeper - but deciding whether a particular position is self-consistant - a whole different thing
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.
The Cure of the ills of Democracy is more Democracy.
Erlang Developer and podcaster
Besides P = NP for N = 1 (:-).
It works like this. Minesweeper seems logical from the start. but your mind is actually haviong to make some intuitive jumps at critical points. Such as when you have three blocks and you know that teo of them have mines with in them. it takes an intuitive jump to come at the problem from another direction and try to solve one of the three blocks from a different edge. Straight Boolean logic chokes on this because there are not enough known values and to many unknown variables. Free Cell on the other hand can be solved easily by a computer simnply by using the brute force method. Because all of the components of the puzzle are layed out before it and it can plan each of its moves in advance... much like how a computer plays chess. it is figuring out how to get the computer to make these intuitive leaps that seperates a P from a NP problem.
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.
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.
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.
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---
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.)
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.
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 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.
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.