In a typical minesweeper setup, we have:
Beginner: 10 mines in 9x9 Intermediate: 40 mines in 16x16 Expert: 99 mines in 16x30
That means mines occupy ~12.35%, ~15.63%, and ~20.63% of the board, respectively. It is possible to increase the numbers of mine and still win, albeit some guessing may be needed to win.
Experimentally, it seems that higher than 30% board coverage becomes unwinnable because the useful information we can gain from each uncovered square decreases. But does it hold? Can we show a probability graph that for a given % of mine coverage, the game will be winnable (or not) the % of time?
We need to define the "winnability". A perfectly winnable game would be one that for any given numbers of clicks, the information revealed are deterministic and do not require any guessing to win. As the mine coverage increase, the chances of being force to guess due to ambiguity also increase and thus it becomes less and less deterministic. Thus, minesweeper becomes less and less a logical puzzle and more and more a gambling game.
Using a beginner's board as an example, we have a maximum of 71 moves to clear the board. We can imagine that For each move, the revealed tiles has a probability of yielding deterministic vs. ambiguous information. As we know more and more, the chance of getting an ambiguous information also drop. With more mines covering the board, there are more opportunities for revealing a tile yielding ambiguous information, necessitating guesses. We want to count how many guesses are required to win the game for a given mine coverage.
Hopefully that helps clarifies the constraint of the question.
$\endgroup$ 41 Answer
$\begingroup$This is a reasonable thing to wonder about, but hard to formulate a good question. If you have three mines in the cells next to each corner you can't determine the solution if you have the rest of the board and know that some corners are mine(s) and some are not. For the beginner level you could have just two corners in this configuration with one mine yet to find.
One can certainly write a program to solve minesweeper, then ask how many times it got a solution without guessing. You have to decide which cell to start with. I always started with a corner because it seemed to have the best chance of giving a lot of information, but given that you will never lose on the first guess maybe you should start with a middle square. It gives information on more neighboring squares. This implies that the best strategy depends on what you know about how the mine pattern is generated.
$\endgroup$
