Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
Mathematical Minesweeper

By vinay in MLP
Wed Nov 01, 2000 at 01:13:05 PM EST
Tags: Science (all tags)
Science

This link over at the Boston Globe is about a british mathematician has demonstrated that the P vs. NP conjecture would be false if one could write a program that can beat any minesweeper board.

If anyone recalls, The Clay Mathematics Institute is offering 1 million dollars to anyone who can solve this problem. (Description here). It's a little freaky that Minesweeper of all things might be the key to one of Computer Science's most difficult dilemmas.


Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Related Links
o This link
o The Clay Mathematics Institute
o here
o Also by vinay


Display: Sort:
Mathematical Minesweeper | 9 comments (9 topical, editorial, 0 hidden)
Not as big a breakthrough as all that... (4.88 / 9) (#1)
by BlaisePascal on Wed Nov 01, 2000 at 12:18:30 PM EST

I've looked at the guy's work when it was reported elsewhere. It's not that huge of a deal.

The problem that was shown to be NP-Complete is not "how do I solve this mine-sweeper layout", but "Is there a solution to this mine-sweeper layout".

If you look at a mine-sweeper layout, you sometimes see conditions where you have to say "A mine must be at one of these two locations, but not both", and would just have to guess which is right in order to solve the puzzle. The puzzle is consistant with either solution. On the otherhand, if you look at a mine-sweeper layout, and say "This configuration forces a mine to be here, but that would mean that that square labeled "3" would have 4 mines next to it, which is impossible", then the puzzle is not consistant with any solution.

Basically, he discovered layouts that act as wires (if there is a mine here, then -way- over there, there must be a mine, and vice versa), inverters (if there is a mine here, then -way- over there, there must NOT be a mine, and vice versa), conjunctions (all of these locations must be mined), and disjunctions (at least one of these locations must be mined).

Using these layouts, you can convert any problem in SAT (a known NP-complete problem) into a mine-sweeper layout, such that the layout is consistant if and only if the SAT problem can be satisfied.

But knowing how to solve minesweeper is not going to help.

Perl patter matching is also NP-Complete, but you don't hear anyone saying what an advance that is, do you?

Slight Correction (4.60 / 5) (#2)
by Ryan Koppenhaver on Wed Nov 01, 2000 at 12:18:47 PM EST

The challange is not simply to beat any minesweeper board. For one thing, that's not always possible. You have to pick your first square at random, so there's always a chance you'll die right away, regardless of your algorithm. (MS Minesweeper cheats in the users favor on this, BTW.)

Second, it's not all that hard to write an algorithm to play minesweeper correctly. The dificulty is to do it in polynomial time, which is the foundation of the P[?] vs. NP[?] problem.



What? (2.60 / 5) (#3)
by 11223 on Wed Nov 01, 2000 at 12:23:02 PM EST

Excuse me, but this must be a hoax. Anybody who plays Minesweeper for any period of time knows that, under some implementations, you can lose even on your first click! And, if not, your board could look like this:

2 _ _
_ _ _  .....
_ _ _
(_ = covered space). How do you beat that? There's no way to tell what to click.

Somebody please explain this to me. Or is the "minesweeper consistency problem" not the same as the game itself?

Hrmn, if a large number of office workers played a modified game of Minesweeper at work, could we use it ala distributed.net to break discrete log then?

--
The dead hand of Asimov's mass psychology wins every time.

My bad. (2.66 / 3) (#4)
by vinay on Wed Nov 01, 2000 at 12:30:09 PM EST

It is the Minesweeper consistency problem. But it still remains that if you find a polynomial time solution for minesweeper, then you've demonstrated that P=NP.

Not that that's easy or anything ;-)

-\/


-\/


[ Parent ]
You don't have to solve minesweeper.... (5.00 / 4) (#5)
by BlaisePascal on Wed Nov 01, 2000 at 01:10:54 PM EST

Here's an example of a minesweeper-consistancy-problem:

Given a mine-sweeper layout that looks like so (| and - being walls, * being unexposed spaces, and numbers being counts):

-----------------------------
|111111111111111111111111111|
|1**1**1**1**1**1**1**1**1**|
|111111111111111111111111111|
-----------------------------
is there a set of mines that is consistant with the layout given? In this case, "Yes". Note, however, that there is not enough information there to say what the actual solution is. I have two choices.

The following layout has no solutions

------------------------------
|1111111111111111111111111111|
|1**1**1**1**1**1**1**1**1**1|
|1111111111111111111111111111|
------------------------------
When I play minesweeper on my PC, I can assume that the layout is consistant. I don't have to worry about there being no solution. The solution is there to begin with, I just have to find it.

But just given an arbitrary layout, I can't assume that it is already consistant. I've shown two layouts, both look similar, one consistant and the other not. If I want to know if it is consistant, I have to reason it out -differently- than I would to solve it. I also have to work with the information given. I can't uncover a known "safe" square and get more information. That info just isn't available.

The NP-complete proof shows how to convert a known NP-Complete problem (SAT) into a minesweeper layout, such that the SAT problem is satisfiable if and only if the minesweeper layout is consistant. A solver won't be able to solve it if there is not one unique solution. So solving and consistancy checking are not the same at all!

[ Parent ]

Does this mean..... (2.75 / 4) (#6)
by 11223 on Wed Nov 01, 2000 at 02:16:25 PM EST

That if we got a large number of people playing (potentially) inconsistent minesweeper games, and the program reporting on whether they are consistent or not, that we could use this ala distributed.net by equating it to Discrete Log to break people's PGP keys?

--
The dead hand of Asimov's mass psychology wins every time.
[ Parent ]

No, it won't help... (2.00 / 1) (#7)
by BlaisePascal on Wed Nov 01, 2000 at 03:27:56 PM EST

Take a look at the author's site for more details as to what he's talking about.

[ Parent ]
This was in Scientific American (4.66 / 3) (#8)
by mwright on Wed Nov 01, 2000 at 07:36:36 PM EST

This was in Scientific American a while ago, in the mathematical recreations section... August or September, I think, although I can't find it on the website. Essentially, finding out how a given circiut will work is one of these problems, and that it is possible to make a minesweeper configuration to match any circuit of certain components; this was done my making minesweeper representations of varoius components, wires, wire crossings, etc. This is the reason that there are so many problems that could prove P=NP: many have been proven to be equivalent, by methods like this.

Gauss and Incompleteness (none / 0) (#9)
by acestus on Thu Nov 02, 2000 at 02:38:03 PM EST

One of my `fortune` answers is:
Computer Science is merely the post-Turing decline in formal systems theory.


From what I remember of my formal logic and AI class, one of Gauss's big contributions to formal logic was the Incompleteness Theorem, which says that no system of formal logic can ever completely define itself. Now, I will spare you the long explanation -- and thereby spare myself of remembering it incorrectly -- but the basic idea is that there will always be a case in a formal, logical system which describes a case incomprehensible to the system itself. It's (one of the reasons) why computers aren't great at geometry, but they are good at arithmetic.

Acestus
This is not an exit.
[ Parent ]
Mathematical Minesweeper | 9 comments (9 topical, 0 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!