28
$\begingroup$

This is just a question I thought of while playing minesweeper. I think that finding the solution might be kind of fun, so I'm sharing it with you guys. If you have no concept of what minesweeper is, this question might be kind of tough. Also, if you have no concept of what minesweeper is go play it. It's fun.

It's an expert board. That means you have a grid of 16 by 30, for a total of 480 squares. A random 99 of these squares have a mine hidden under them.

When you click a square, three things can happen. You can click a mine, resulting in an instant loss. You can click on a square next (diagonal included) to at least one mine, resulting in a number being shown under the square. Or you can click on a square that isn't a mine and isn't next. When this is done, all 8 surrounding squares are revealed. If any of those squares are also not next to any mines, all of the surrounding squares that are not yet revealed become revealed.

That should make sense if you've played minesweeper before.

You're playing expert mode. The mines are spread randomly. What is the average number of squares revealed by your first click?

I would count clicking a mine as 0 squares revealed.

Have fun!

  • 0
    I am just speculating but in the last or the last 2 versions of Windows, minesweeper is patched for not allowing the first click detonation or number 8 cells. So the problem gets even more complicated. By the way, expert minesweeper is a nice sounding career choice. :)2011-09-07
  • 0
    @Thijs Laarhoven Absolutely. I specified that the first click would be random. Of course, it'd be even cooler if you could solve the question for all the different places you could click, and find the best one.2011-09-07
  • 8
    (+1) This seems like it is essentially a [percolation-model](http://en.wikipedia.org/wiki/Percolation_theory) problem.2011-09-07
  • 1
    This is probably easier to solve on an infinite board where the probability of any given cell being a mine is $99/480$ independently. In which case you have $99/480 * 0 + 381/480 * (1 - (381/480)^8) * 1 + (381/480)^9 * x$, where x is the average number of cells revealed given that the first cell is not adjacent to a mine. $x>9$, but figuring out the exact value will be tricky.2011-09-07
  • 1
    @Craig, that is essentially getting close to how the problem would be formulated in the percolation-theory framework. The problem of interest there essentially becomes whether there is positive probability $\theta$ of an *infinite* number of cells being revealed, especially when we generalize further to the case where the probability of any given cell being a mine is parametrized by $p \in (0,1)$, so that $\theta(p)$ is now a function. [Here](http://www.statslab.cam.ac.uk/~grg/papers/perc/perc.html) is a good starting point.2011-09-07
  • 1
    Yes, I'm aware. And since this is a 2-d problem, and p < 1/2, the probability $\theta$ is essentially zero, and the probability that n cells are revealed falls off exponentially as a function of n. But I don't know how to calculate the exponential fall-off rate, and I don't know how to correct that for fall-off for small n.2011-09-07
  • 1
    After 25 tries using the corner square, the mean number of squares uncovered was about 16 and the standard deviation was 10. After 15 tries with one of the 4 middle squares, the mean was 45 and the standard deviation was 13. More squarea are uncovered at the centre because each square has 8 meighbours and the adjacent squares, and squares adjacent to the adjacent squares.. are also more likely to have 8 neighbours rather than 7 or 6.2011-09-07
  • 1
    @Angela: The mean in the corner should be a little over 9.1 and the mean in the middle should be about 8.8. More to follow...2011-09-07

1 Answers 1