7
$\begingroup$

This paper shows that it is NP-hard "to determine if there is some pattern of mines in the blank squares that give rise to the numbers seen."

If there is a way to "lead a perfect player into" such positions, then it would easily follow that it is also NP-hard to play minesweeper perfectly. However, I do not see any way to rule out the possibility of an algorithm that plays minesweeper perfectly by never going into the sort of positions that would be produced by applying that paper's reduction to hard instances of SAT.

Is playing minesweeper perfectly known to be NP-hard?

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ What do you exactly mean with "play minesweeper perfectly"? Don't forget that "real" minesweeper often has more than one consistent mine configuration for a given a position. As a trivial example pick the starting position, in which ALL mine configurations are consistent. So, what are the "tools" that must be available to a player at the start of a game to play it perfectly and avoid guessing? $\endgroup$
    – Marzio De Biasi
    Mar 1, 2014 at 23:42
  • $\begingroup$ I mean "follow a strategy that maximizes the probability of winning, given the number of mines and board size in unary, where the mines are uniformly distributed". $\:$ The only way to avoid guessing at the start of the game is if the number of mines is either zero or equal to the number of squares. $\:$ I think a PSPACE oracle is a big enough "tool" so that, if it's available at the start of a game then the game can be played perfectly, although I don't have any better idea of what "tools" must be available for that. $\;\;\;\;$ $\endgroup$
    – user6973
    Mar 2, 2014 at 0:10
  • $\begingroup$ Is the computational problem to output a strategy given board size and number of mines in unary? If that is the case, it is not even clear to me that a strategy can be compactly represented. I guess you can also define a computational problem based on "conditional on current board set up, compute a next move consistent with some optimal strategy". What do you have in mind? $\endgroup$
    – Sasho Nikolov
    Mar 2, 2014 at 18:32
  • $\begingroup$ No. $\:$ I was implicitly imagining that the player might be stageful, and I believe the claims in the Michiel de Bondt paper link to in Marzio's answer imply NP-hardness even in that case. $\:$ However, that paper's argument for those claims is far from clear, which I will probably address in a later question. $\;\;\;\;$ $\endgroup$
    – user6973
    Mar 2, 2014 at 20:13

1 Answer 1

Reset to default
6
$\begingroup$

Just an extended comment; in

Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper May Not Be NP-Complete but Is Hard Nonetheless

the authors face the problem I mentioned in my comment above.

From the abstract:

In volume 22 of The Mathematical Intelligencer, Richard Kaye published an article entitled "Minesweeper is NP-Complete." We point out an oversight in Kaye's analysis of this well-known game. As a consequence, his NP-completeness proof does not prove the game to be hard. We present here an improved model of the game, which we use to show that the game is indeed a hard problem; in fact, we show that it is co-NP-complete.
....
In this article, we investigate the complexity of the deterministic part of playing Minesweeper. In our analysis, we assume that the player is given a consistent Minesweeper board configuration. That is, when completely revealed, the board presented has in each square either a mine or a numeber corresponding to the correct number of neighboring mines. Further, we assume an ideal player who makes no mistakes in reasoning. Note that these assumptions imply that the player can only lose (try to open a square containing a mine) when forced to guess. Therefore, our optimal player who follows the strategy described previously will avoid guessing whenever possible. However, to do so he must be able to decide whether it is possible to make progress on the board without guessing. This problem is what we call the Minesweeper Inference problem.
...

There is also a recent paper on arXiv that seems relevant (I just found it now):

Michiel de Bondt, The computational complexity of Minesweeper

Abstract: We show that the Minesweeper game is PP-hard, when the object is to locate all mines with the highest probability. When the probability of locating all mines may be infinitesimal, the Minesweeper game is even PSPACE-complete. In our construction, the player can reveal a boolean circuit in polynomial time, after guessing an initial square with no surrounding mines, a guess that has 99 percent probability of success. Subsequently, the mines must be located with a maximum probability of success.
Furthermore, we show that determining the solvability of a partially uncovered Minesweeper board is NP-complete with hexagonal and triangular grids as well as a square grid, extending a similar result for square grids only by R. Kaye. Actually finding the mines with a maximum probability of success is again PP-hard or PSPACE-complete respectively.
Our constructions are in such a way that the number of mines can be computed in polynomial time and hence a possible mine counter does not provide additional information. The results are obtained by replacing the dyadic gates in [3] by two primitives which makes life more easy in this context.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.