1
$\begingroup$

When I play the game Minesweeper, I make the puzzle more difficult by increasing the amount of mines and still keep the board. Once I set the maximum number of mines for a 9x9 board, which is $67$, I realise that the chance to win is almost zero(!). And when I play a game with a $24$x$30$ board with $150$ mines, I sometimes have to guess in order to win the game.

And after all, my question is:

Given a m by n Minesweeper board, what is the maximum number of mines can exist so that any puzzle with those mines is solveable without guessing?

Note: This question has some similarity to mine.

$\endgroup$
  • $\begingroup$ If there's more than 9 mines and they make a 3*3 square then, the one in the middle is very hard to find except if you already discovered the rest of the game and know there's a mine left $\endgroup$ – Kii May 21 '17 at 14:17
  • 1
    $\begingroup$ What counts as "not guessing"? Are you allowed an initial guess? I think what you meant is that you are also given a starting square which you know is safe, and then you can solve the puzzle from that square alone? $\endgroup$ – MaudPieTheRocktorate May 22 '17 at 3:19
3
$\begingroup$

Two if the dimensions are large enough.

If you have three mines, may have to guess between B1,C1,C2 and A1,C1,C2. Or A1,B2,C3 and A2,B1,C3. $$ \begin{array}{c|ccc} & A & B & C \\ \hline 1 & ? & ? & * \\ 2 & 1 & 3 & * \\ 3 & 0 & 1 & 1 \end{array} or \begin{array}{c|ccc} & A & B & C \\ \hline 1 & ? & ? & 1 \\ 2 & ? & ? & 2 \\ 3 & 1 & 2 & * \end{array} $$

$\endgroup$
1
$\begingroup$

Considering a 3*3 square full of mines and another 3*3 square with 8 mines around a empty space. There's one chance out of two that you can guess which square has a mine inside the 8 mines. So I would say 17 mines.

This is a worse case scenario. It can be even worse considering corner positions. Maybe just 7 mines in two corners would suffice to make it a guess.

$\endgroup$
  • $\begingroup$ Yep, I also think that 7 mines is enough for any board bigger than 4 by 4, and that's enough because I don't really care about smaller board! $\endgroup$ – Lê Đức Minh May 21 '17 at 14:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.