All numbers in a 5x5 Minesweeper grid

Question

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

Good luck!

Answer 1

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 \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0} & \phantom{0}\\ \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 & \phantom{0} & \phantom{0} \\ \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 & \phantom{0} & \phantom{0} \\ \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 & \phantom{0} & \phantom{0} \\ \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 & \phantom{0} & \phantom{0} \\ \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 & \phantom{0} & \phantom{0} \\ \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 & \phantom{0} & \phantom{0} \\ \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 & \phantom{0} & \phantom{0} \\ \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 & \phantom{0} & \phantom{0} \\ \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.

Answer 2

Although the puzzle is most likely to be solved without a computer, and we already have a winner, here are all 16 solutions, just for the record:

Board state 6420159 (11000011111011010111111)
XXXXX
X7X8X
X6XXX
XX542
3XX10

Board state 7404223 (11100001111101010111111)
XXXXX
X7X8X
3XXXX
X6542
XXX10

Board state 7528123 (11100101101111010111011)
XX3XX
X7X6X
XXX5X
X8X41
XXX20

Board state 7528239 (11100101101111100101111)
XXXX3
X76XX
XXX5X
X8X41
XXX20

Board state 13393599 (110011000101111010111111)
XXXXX
X8X7X
XXX6X
245XX
01XX3

Board state 16571559 (111111001101110010100111)
XXX20
X8X41
XXX5X
X76XX
XXXX3

Board state 29023399 (1101110101101110010100111)
XXX20
X8X41
XXX5X
X7X6X
XX3XX

Board state 29030044 (1101110101111011010011100)
02XXX
14X8X
X5XXX
X6X7X
XX3XX

Board state 29900479 (1110010000011111010111111)
XXXXX
X8X7X
XXXX3
2456X
01XXX

Board state 30045822 (1110010100111011001111110)
3XXXX
XX67X
X5XXX
14X8X
02XXX

Board state 30045883 (1110010100111011010111011)
XX3XX
X6X7X
X5XXX
14X8X
02XXX

Board state 32110236 (1111010011111011010011100)
02XXX
14X8X
X5XXX
XX67X
3XXXX

Board state 33209884 (1111110101011111000011100)
01XXX
2456X
XXXX3
X8X7X
XXXXX

Board state 33218316 (1111110101101111100001100)
01XX3
245XX
XXX6X
X8X7X
XXXXX

Board state 33223782 (1111110101111010001100110)
3XX10
XX542
X6XXX
X7X8X
XXXXX

Board state 33224743 (1111110101111100000100111)
XXX10
X6542
3XXXX
X7X8X
XXXXX

Done
    states   : 33554432
    solutions: 16

There are some symmetries in there, of course. Whether rotations and flips should count as "different boards" is a matter of interpretation.

Found with the following (quick and dirty) Java program that jus enumerates all boards and prints those where each number appears exactly once:

public class MinesweeperNumbers {
    public static void main(String[] args) {

        Board board = new Board();
        int totalCounter = 0;
        int matchingCounter = 0;
        while (!board.isDone()) {
            if (board.hasEachNumberOnce()) {
                System.out.println(board.createString());
                matchingCounter++;
            }
            totalCounter++;
            board.next();
        }
        System.out.println("Done");
        System.out.println("    states   : " + totalCounter);
        System.out.println("    solutions: " + matchingCounter);
    }

    static class Board {
        private long state = 0;
        private final int rows = 5;
        private final int cols = 5;

        void next() {
            state++;
        }

        boolean isDone() {
            return state >= (1L << (rows * cols));
        }

        boolean hasEachNumberOnce() {
            boolean numbers[] = new boolean[9];
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (!hasMine(r, c)) {
                        int number = getNumber(r, c);
                        if (numbers[number]) {
                            return false;
                        }
                        numbers[number] = true;
                    }
                }
            }
            for (int i = 0; i < 9; i++) {
                if (!numbers[i]) {
                    return false;
                }
            }
            return true;
        }

        int getNumber(int r, int c) {
            int count = 0;
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr != 0 || dc != 0) {
                        if (hasMine(r + dr, c + dc)) {
                            count++;
                        }
                    }
                }
            }
            return count;
        }

        boolean hasMine(int r, int c) {
            if (r < 0 || r >= rows) {
                return false;
            }
            if (c < 0 || c >= cols) {
                return false;
            }
            int index = r * cols + c;
            return (state & (1L << index)) != 0;
        }

        String createString() {
            StringBuilder sb = new StringBuilder();
            sb.append("Board state " + state);
            sb.append(" (" + Long.toBinaryString(state) + ")\n");
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (hasMine(r, c)) {
                        sb.append("X");
                    } else {
                        sb.append(getNumber(r, c));
                    }
                }
                sb.append("\n");
            }
            return sb.toString();
        }
    }

}

Answer 3

The solution to this problem and its generalizations (multiple numbers on larger grids) can be found in this integer sequence:

https://oeis.org/A302980

You can see the actual solutions here:

https://oeis.org/A302980/a302980.txt