combinatorics - All numbers in a 5x5 Minesweeper grid

Can you place mines on a 5x5 Minesweeper grid such that each number from 0 to 8 appears exactly once?

Good luck!

Answer

Assuming standard Minesweeper rules, here’s one solution (with $ X $ = a mine):

$$ \begin{array}{|c|c|c|c|c|} \hline 0 & 2 & X & X & X \\\hline 1 & 4 & X & 8 & X \\ \hline X & 5 & X & X & X \\ \hline X & 6 & X & 7 & X \\ \hline X & X & 3 & X & X \\ \hline \end{array} $$

EDIT: In response to Euphoric in the comments, I solved this purely by logical deduction with a bit of educated guessing to make things easier on me. But if you really want to know how I did it, here’s a rigorous solution:

We’ll start with a blank grid, as such: $$ \begin{array}{|c|c|c|c|c|} \hline & & & & \\ \hline \\ \hline \\ \hline \\ \hline \\ \hline \end{array} $$ Label the rows A-E (uppercase) going from top to bottom, and the columns a-e (lowercase) going from left to right.

The first thing I did was try and place the 0. It cannot be placed anywhere in the central 3x3 square, since that would prevent the 8 from being placed. It also cannot be in any square next to a corner, e.g. Ab, Ad, Be, since that would force the corner it is next to to also be a 0, which is not allowed. The case where it is located in the middle of an edge i.e. Ac, Ce, Ec, Ca requires more work. WLOG, suppose the 0 were placed in Ac. Then, Ab, Bb, Bc, Bd, Ad all have to be safe, which forces Ab and Ad to be 1 and 2 in some order. This, in turn, forces Bc to be 3. Let’s say Ab were 1. Then, there is a mine in one of Aa or Ab. If it were in Ab, then Aa would also have to be 1, so Aa must contain the mine. However, this leads to a contradiction at Ba: it can’t be a mine due to Ab, so it has to be 2 or 3, which are already taken by other squares. (See the grid below. $ S $ = safe.) Contradiction, so the only valid location(s) for the 0 are the corners. $$ \begin{array}{|c|c|c|c|c|} \hline X & 1 & 0 & 2 & X \\ \hline \color{red}{?} & S & 3 & S & X \\ \hline & X & X & X & \\ \hline \\ \hline \\ \hline \end{array} $$
WLOG let’s put the 0 in corner Aa. This makes Ab, Bb, Ba all safe. Looking at their surroundings, we see that Ab and Ba have to be 1 and 2 in some order, so let’s make Ba the 1 and Ab the 2: $$ \begin{array}{|c|c|c|c|c|} \hline 0 & 2 & X & & \\ \hline 1 & S & X \\ \hline X \\ \hline \\ \hline \\ \hline \end{array} $$ Here, I put Ca as a mine, even though Cb is also another option. Since this is a rigorous write-up, I will explain why Cb cannot be a mine. If it were, then Ca would have to be a 3 and Bb would be a 4: $$ \begin{array}{|c|c|c|c|c|} \hline 0 & 2 & X & & \\ \hline 1 & 4 & X \\ \hline 3 & X & X \\ \hline X & X \\ \hline \\ \hline \end{array} $$ By trying out different locations for the 8 (namely, Dc, Dd, Cd, and Bd), we find that none of them allow for all of 5, 6, 7 to be placed. Thus, Cb cannot be a mine.

Returning to our current grid, we need to decide whether Bb is a 3 or a 4. This one’s easier to deduce, as if Bb were a 3, then Cb and Cc would both be safe, and now the 8 cannot be placed anywhere. Thus, Bb is a 4, Cb is safe, and Cc is a mine: $$ \begin{array}{|c|c|c|c|c|} \hline 0 & 2 & X & & \\ \hline 1 & 4 & X \\ \hline X & S & X \\ \hline \\ \hline \\ \hline \end{array} $$ Obviously, Cb cannot be 3, so it is either 5 or 6. Here, I made another guess and wrote down Cb as 5, but to be rigorous — if we were to make Cb a 6, then Bd and Dd have to be 8 and 7 in some order, but neither configuration allows 3, 5 to be placed on the grid. Our grid now looks like this: $$ \begin{array}{|c|c|c|c|c|} \hline 0 & 2 & X & & \\ \hline 1 & 4 & X \\ \hline X & 5 & X \\ \hline ? & ? & ? \\ \hline \\ \hline \end{array} $$ Only one of Da, Db, Dc is safe, while the other two contain mines. I will show that Da must contain a mine i.e. it cannot be safe. If it were, then it would have to be a 3, which gives us this configuration: $$ \begin{array}{|c|c|c|c|c|} \hline 0 & 2 & X & & \\ \hline 1 & 4 & X \\ \hline X & 5 & X \\ \hline 3 & X & X \\ \hline X & \color{red}{?} \\ \hline \end{array} $$ Ea is a mine over Eb since 2 is already taken. However, we can see that Eb is now problematic: it cannot be a mine, but it also cannot be a number as the only valid one it could possibly be is 4, which is already placed in the grid. Therefore, Da must be a mine: $$ \begin{array}{|c|c|c|c|c|} \hline 0 & 2 & X & & \\ \hline 1 & 4 & X \\ \hline X & 5 & X \\ \hline X & ? & ? \\ \hline \\ \hline \end{array} $$ Now, there remains one mine between Db and Dc. As it turns out, making either one the mine (and the other the safe square) each give valid solutions, which Marco13 found in their computer search. I chose Dc as the mine for my solution: $$ \begin{array}{|c|c|c|c|c|} \hline 0 & 2 & X & & \\ \hline 1 & 4 & X \\ \hline X & 5 & X \\ \hline X & S & X \\ \hline \\ \hline \end{array} $$ Now, Db is either a 6 or a 7. It cannot be a 7, since attempting to place the 8, 6, 3 in the remaining squares is impossible (there will be a leftover square). So, Db is a 6, and the mines must be Ea and Eb, which forces Ec to be a 3: $$ \begin{array}{|c|c|c|c|c|} \hline 0 & 2 & X & & \\ \hline 1 & 4 & X \\ \hline X & 5 & X \\ \hline X & 6 & X \\ \hline X & X & 3 \\ \hline \end{array} $$ From here, it is clear where the 7 and 8 should go (Dd and Bd, respectively), and this gives my final solution.