# Lottery in Minesweeper

The question is inspired by this scenario:

In this case, we had 2 tiles remaining, and each had the equal probability of being a mine, based on the already deduced information. Thus it was necessary to make a guess between the remaining 2 tiles. There are several times where one must make guesses because there is not enough information to logically deduce the positions of mines.

So.... What is the maximum number of covered (unsolved) tiles possible where only one tile is not a mine, and all others are mines, AND any one of the covered tiles may be the only blank with equal probability, forcing a guess among the remaining covered tiles?

There are two possible parts to the puzzle – one scenario where we have only one cluster of covered tiles, and another where we have more than one cluster of covered tiles, each cluster containing one or more covered tiles. However, in either case, we can assume we already have cleared the rest of the board and have only one blank tile left with rest being mines. In both cases, the cluster(s) are already surrounded, so we do have some information about where mines may or may not be. Thus, we should exclude trivial solutions such as having only 2 blanks tiles for the entire board.

The non-trivial solution should not have to depend on the size of the board, beyond being big enough to contain the maximum possible. It is OK to use the boundaries of the board if it helps increase the number of covered tiles, but they must be at least surrounded by other uncovered tiles.

Another trivial solution which satisfies the above criteria and is also unbounded is to create an isolated, enclosed region of unsolved tiles.  By “isolated” and “enclosed” I mean that it is surrounded by mines.  This is easily done with a rectangle; for example, the overall area could be a 10×7 rectangle.  We would have information about its edges (10−1 +7 −1 +10 −1 +7−1=30 tiles), having 3s along the side, 2s and 1s at the corner, with an inner 8×5 border of 8−1 +5 −1 +8 −1 +5−1=22 tiles that are all mines, and no information about the 6×3=18 interior – any one of those tiles could be the lone blank.  Such a region can be arbitrarily large.

Illustration:
\begin{array}c \color{blue}1&\color{green}2&\color{red}3&\color{red}3&\color{red}3& \color{red}3&\color{red}3&\color{red}3&\color{green}2&\color{blue}1 \\ \color{green}2&\color{red}\delta&\color{red}\delta&\color{red}\delta& \color{red}\delta&\color{red}\delta& \color{red}\delta&\color{red}\delta&\color{red}\delta&\color{green}2 \\ \color{red}3&\color{red}\delta&?&?&?&?&?&?&\color{red}\delta&\color{red}3 \\ \color{red}3&\color{red}\delta&?&?&?&?&?&?&\color{red}\delta&\color{red}3 \\ \color{red}3&\color{red}\delta&?&?&?&?&?&?&\color{red}\delta&\color{red}3 \\ \color{green}2&\color{red}\delta&\color{red}\delta&\color{red}\delta& \color{red}\delta&\color{red}\delta& \color{red}\delta&\color{red}\delta&\color{red}\delta&\color{green}2 \\ \color{blue}1&\color{green}2&\color{red}3&\color{red}3&\color{red}3& \color{red}3&\color{red}3&\color{red}3&\color{green}2&\color{blue}1 \end{array} where $\color{red}\delta$ represents a tile that has been solved / deduced to be a mine.  (For simplicity, assume that each outer edge of the above rectangle is adjacent to either an edge of the board, or a column or row of blank tiles.)

However, this is an unsatisfying solution, because it does not speak to the constraint of information we have when we explore the board. As illustrated in the (top) picture, we had 2 valid positions and we had enough information to exclude all other possible positions except for those 2 positions. We want to see what is the greatest possible number where we still would have to guess the position of the last blank tile.

Thus, to exclude this trivial solution, we should add the constraint that every covered tile has an adjacent uncovered tile that conveys some (but not complete) information about the position of the remaining blank tile.

• Eh? how if we play 10x10 minesweeper and there are 99 bombs? We have to guess with probability of 1/100 – athin Dec 24 '17 at 5:58
• @athin You'll win, since the first click can't be a mine. – boboquack Dec 24 '17 at 6:35
• The maximum number of uncovered tiles possible (as asked) is unbounded. It depends in part on the dimensions of the board. – Lawrence Dec 24 '17 at 7:17
• Also, you never have to "guess among the remaining uncovered tiles" - they are already uncovered. Perhaps you meant to say "covered"? – Lawrence Dec 24 '17 at 7:25
• @Lawrence I assumed that they meant "unrevealed" rather than "uncovered" (and answered as such). It would make the most sense with the question. – Deusovi Dec 24 '17 at 8:59

The most you can do according to these new rules is 8 tiles, with the following grid:

1 2 3 3 3 2 1
2 # # # # # 2
3 # ? ? ? # 3
3 # ? 7 ? # 3
3 # ? ? ? # 3
2 # # # # # 2
1 2 3 3 3 2 1


# represents an already-discovered mine.

To show that this is maximal, look at the "information-conveying" tiles required by the instructions. We'll call these "useful tiles".

If there is more than one useful tile, then the possible mines must be in all useful tiles' neighborhoods. (If they weren't, then the useful tiles' numbers would give you information about where the non-mine was, making the probabilities unequal.) In this case, the non-mine must be in all useful tiles' neighborhoods -- but two or more tiles can only have neighborhoods that intersect in at most 3 tiles.

- - ? - -
- U ? U -
- - ? - -


Therefore 1 useful tile is maximal, and it touches eight possible tiles.

• I apologize - you caught me with a trivial solution I didn't intend to include. I've already updated the question. Very good one! – this Dec 24 '17 at 14:29
• Impressive! I think your explanation about useful tiles having at most only 3 tiles that intersect explains why it's also difficult to have more than 2 possible layouts in a typical game with random layout. So far, I've yet to see a game where 3 or more layouts are due to "useful" tiles intersecting and thus limiting the possible choices. – this Jan 5 '18 at 4:03

Thinking about this more carefully, I'm not sure it's even possible to have more than 2 tiles being equally probable choice.

This is based on observations but consider the case where we only have 4 uncovered tiles and 2 mines left. For example:

X | 2 | 2 | X
2 | ? | ? | 2
2 | ? | ? | 2
X | 2 | 2 | X


With that, there are 2 different ways to place the mines without changing the surrounding tiles' numbers. Add one more mine to the board, then the adjacent tiles' numbers must change regardless where you place the new mine which then give us too much information, enough to solve the board without guessing. Therefore, to have more possible configurations, there has to be as many blank tiles as there are mines.

I do not think it is possible to have a setup where you could have 3 uncovered tiles, 2 of them being mines and all possible placements being equally valid placements without changing the adjacent tiles' number since to increase more possible valid layouts seems to require more blank tiles in addition to mines. But I can't prove this rigorously.

• I've updated my answer to show a configuration with 8 tiles -- I think this fits your guidelines, but I'm not sure. – Deusovi Jan 5 '18 at 0:05

With every unknown touching a clue, and every clue touching another clue (was "in a network" made explicit?), I think 5 is the answer.

02MMM
24M?M
MM6?M
M???M
MMMMM