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.