10
$\begingroup$

I'm playing minesweeper on an infinite grid. I'm told upfront how many mines there are. What's the smallest possible $n$ for which there exists a configuration of $n$ mines such that, no matter where I make my initial move, I will be unable to fully solve the puzzle without making at least one subsequent risky move?

$\endgroup$
3
  • $\begingroup$ Do you as the solver know n but presumably not the configuration of mines? $\endgroup$
    – xnor
    Oct 29, 2023 at 7:29
  • $\begingroup$ Yes, I'm playing a version of minesweeper which tells you how many mines you have left to find. $\endgroup$
    – fblundun
    Oct 29, 2023 at 8:30
  • 2
    $\begingroup$ The first move is always a risky move $\endgroup$
    – rtaft
    Oct 30, 2023 at 13:36

3 Answers 3

19
$\begingroup$

Here is a six-mine solution:

enter image description here

Of the four question marks in the middle, two are mines, but it could either be the top-left and bottom-right pair, or the other two.

$\endgroup$
4
  • $\begingroup$ I think this is minimal and unique, even if the solver doesn't know the total number of mines. $\endgroup$
    – aschepler
    Oct 29, 2023 at 13:31
  • $\begingroup$ Doesn't this fail on the 'no matter where I make my initial move' part? It works fine if you start out somewhere away from the mines but if your initial square is one of the central 4 you can solve everything. If you double your solution (maybe with partial overlap?) you should be able to avoid that. $\endgroup$
    – quarague
    Oct 29, 2023 at 14:00
  • 5
    $\begingroup$ @quarague It doesn't fail in that case. If you press one of the center squares, you'll uncover a 3, and nothing else. You can't press any squares around the 3 without risk, and you can't press any other squares since there are three mines that are unaccounted for. $\endgroup$
    – Mateon1
    Oct 29, 2023 at 14:04
  • 4
    $\begingroup$ I've further analyzed the problem if you consider the infinitesimal risk of picking an arbitrarily faraway tile as 'not risky'. In that case, you get one free tile plus the entirety of the outside as information. The 10-mine solution made by gluing this solution to itself along the side of the square seems to be minimal if you require a non-infinitesimal risk. I couldn't quite prove a 9-mine solution impossible, but I'm fairly convinced one can't exist. $\endgroup$
    – Mateon1
    Oct 29, 2023 at 14:48
5
$\begingroup$

V2:

Here's a solution with 7 mines. You cannot tell which of the middle two is a mine. If you click the non-mine ? square, you'll still have to take a risk. The ? will give a 4, but you won't know which of the 8 surrounding squares contain them, since that's the only square that would be revealed. You also won't be able to click a random far-away square, as you can only be sure of the location of 4 out of the 7 bombs. enter image description here

V1: Just starting off with a basic answer, but I don't know if it can be improved upon:

The following is a solution with 11 mines. You can safely place 10 of the mines, but of the middle two squares it is impossible to tell which contains a mine. enter image description here

Of course, you can avoid this exact scenario by having your first click be the 8 square somewhere in the center of the grid, allowing you to place 8 mines instantly. However, it is impossible to determine which surrounding squares contain the remaining 3 flags and you would be forced to make a guess.

$\endgroup$
3
  • $\begingroup$ Regarding V2: if your first click is on one of the two ?, then the problem is solved. $\endgroup$ Oct 30, 2023 at 13:13
  • 1
    $\begingroup$ If so, you'll still have to take a risk. The ? will give a 4, but you won't know which of the 8 surrounding squares contain them. You also won't be able to click a random far-away square, as you can only be sure of the location of 4 out of the 7 bombs. $\endgroup$ Oct 31, 2023 at 10:33
  • $\begingroup$ Right, because only 0 squares are automatically cleared, not squares with adjacent mines. Would be worth adding to the explanation. $\endgroup$ Oct 31, 2023 at 10:38
0
$\begingroup$

Wrong Answer. Missed the infinity grid

Shouldn't every Yx2 field have a one-mine solution?
For a 2x2 grid:
1 ?
? ?

For a Yx2 grid in the middle:
1 ? 1
1 ? 1

One of the questionmarks is a mine.

$\endgroup$
2
  • $\begingroup$ The question specifies an infinite grid. $\endgroup$
    – fljx
    Nov 2, 2023 at 8:50
  • $\begingroup$ to be fair, though, it doesn't specify that it's infinite in both directions. an ∞x2 grid still has infinite squares. though in that case, as this answer shows, any setup with one mine (or more) is unsolvable, making the answer kind of trivial. for that matter, an ∞x1 grid has infinite squares and has the same problem for any number of mines greater than 1 $\endgroup$
    – juicifer
    Nov 2, 2023 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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