Is Minesweeper P or NP? A Fascinating Look into the Popular Computer Game

[Diffy]

Here is a great little article that talks about P=NP and the computer game that comes standard on most PCs with windows

http://www.claymath.org/Popular_Lectures/Minesweeper/

What do you think? Is minesweeper P or NP?

 

[D H]

The article doesn't talk about Minesweeper being NP. Showing what results when a user clicks on a Minesweeper square is easy -- and obviously in P.

The article talks about the "Minesweeper Consistency Problem" being NP. This problem is one that Minesweeper itself doesn't play. Suppose the Minesweeper program was modified to lie. How would it be to determine whether the Minesweeper program had lied? This is the Minesweeper Consistency Problem.

 

[BryanP]

I don't think it's a matter of if Minesweeper is P or NP, but more of a question about WHY is it P or NP.

Of course, if that were the case, I think it wouldn't be posted in here.

 

[D H]

There should be no doubt that the Minesweeper Consistency Problem is NP; the article states this explicitly. The question, then, is whether this new problem helps determine whether or not P=NP. I doubt it. It might, however, help newbies understand the nature of the problem.

 

[LukeD]

So I don't know if this is what the Minesweeper Consistence Problem is, but

Given a minesweeper board with some blank spaces, determining whether the blank spaces have an answer that can be found from the information given, the board is inconsistent, or the board has several possible solutions is an NP-Complete problem. My roommate actually had to prove this for one of his courses. The typical method of proof of that is reduction to 3-sat (which he tried to explain to me, but I couldn't figure out what he exactly it was)

 

[D H]

So I don't know if this is what the Minesweeper Consistence Problem is, but

Given a minesweeper board with some blank spaces, determining whether the blank spaces have an answer that can be found from the information given, the board is inconsistent, or the board has several possible solutions is an NP-Complete problem.

That is exactly the Minesweeper Consistency Problem, and the approach taken by your roommate is exactly that taken in the article cited in the OP.

The boolean satisfiability problem involves determining whether or not there exist assignments to variables in a boolean expression makes the expression true. For example, the expression $x_1 \wedge x_2$ is true if x₁ and x₂ are both true; this expression is satisfiable. On the other hand, $(x_1 \wedge \lnot x_1) \vee (x_2 \wedge \lnot x_2)$ is false no matter what truth values one uses for x₁ and x₂; this expression is not satisfiable. Both of the expressions I gave as examples have two arguments in each clause. For example, $(x_1 \wedge \lnot x_1)$ is an example of a clause with two arguments.

The problem is a 2-satisfiability (2SAT) problem if every clause has exactly two arguments. The 2SAT problem is provably in P. The problem is a 3-satisfiability (3SAT) problem if every clause has exactly three arguments. The 3SAT problem cannot (as of date) be proven to be in P. It is provably in NP and even more importantly, is NP-complete.

 

[BryanP]

Learned something new today.

 

[DeaconJohn]

Thanks, DH. Like Bryan, I also learned something new today. And interesting. And important (to me, anyway). It is such a simple and satisfying fact. One could say, "That'll teach!" -- i.e., that'd be a good example to use in a class. DJ