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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Do you as the solver know n but presumably not the configuration of mines? $\endgroup$– xnorCommented 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$– fblundunCommented Oct 29, 2023 at 8:30
-
2$\begingroup$ The first move is always a risky move $\endgroup$– rtaftCommented Oct 30, 2023 at 13:36
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
Here is a six-mine solution:
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.
answered Oct 29, 2023 at 13:11
-
$\begingroup$ I think this is minimal and unique, even if the solver doesn't know the total number of mines. $\endgroup$ Commented 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$– quaragueCommented 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$– Mateon1Commented 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$– Mateon1Commented Oct 29, 2023 at 14:48
$\begingroup$
$\endgroup$
3
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.
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.
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.
-
$\begingroup$ Regarding V2: if your first click is on one of the two ?, then the problem is solved. $\endgroup$ Commented 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$ Commented 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$ Commented Oct 31, 2023 at 10:38
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ The question specifies an infinite grid. $\endgroup$– fljxCommented 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$– juiciferCommented Nov 2, 2023 at 12:38