6
$\begingroup$

Suppose we have an $m\times n$ minesweeper grid containing $k$ mines (for example the beginner grid is $8\times 8$ with $10$ mines). I have the following related questions:

  1. What is the probability of solving the grid if we play optimally?
  2. What is the probability of being able to solve the grid without guessing, if we are given that the first click reveals an opening?
  3. What is the expected number of mines that would be hit if we had infinite lives, if again we were to play optimally?

I don't hold out much hope for an exact formula for any of these, but any kind of approximation or bound would be good. How would we approach such problems?

I am aware of the option of using a customized minesweeper solver to play many games and get approximate answers via this method, and may well try this one day, but for now I am interested in the mathematical approach.

Perhaps a reasonable simplification would be to treat the grid as infinite with a mine density of $\rho$ (normally $\rho\approx 0.2$) and attempt to calculate the above problems for an area of cells (not necessarily in a rectangle?).

It's simple for very small grids or numbers of mines, or when $k\approx m\times n$, but I would like to get a rough idea for the standard difficulty levels which are: Beginner $8\times 8$ with $10$ mines; Intermediate $16\times 16$ with $40$ mines; Expert $16\times 30$ with $99$ mines.

$\endgroup$
  • $\begingroup$ The answer to 1 is certainly less than $1-\frac k{mn}$ :) $\endgroup$ – Hagen von Eitzen Sep 6 '15 at 18:41
  • $\begingroup$ Based on the chance of success on the first click, indeed. I'm sure you're aware this is a very high upper bound! $\endgroup$ – Siwel Sep 6 '15 at 18:43
  • 1
    $\begingroup$ Joking aside, for $k\ll mn$ I suppose it is not that much higher than the true value $\endgroup$ – Hagen von Eitzen Sep 6 '15 at 18:45
  • 1
    $\begingroup$ Related question: math.stackexchange.com/questions/42494/… $\endgroup$ – Ravi Fernando Sep 6 '15 at 18:59
  • 1
    $\begingroup$ There are a number of show-stoppers: Assume in the $3\times 3$ in a corner we have three bombs: A1, B2, C3 or A2, B1, C3. Then you cannot distinguish these coming from "outside". These configurations occur with probability $2\rho^3(1-\rho)^6$ per corner, which makes $\approx1.7\,\%$ of all boards with $n,m>6$ unsolvable (for $\rho\approx 0.2$). - Another unsolvable corner situation is: Bombs in C1,C2, and one of A1,B1, which makes many more boards unsolvable ... $\endgroup$ – Hagen von Eitzen Sep 6 '15 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.