54
$\begingroup$

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

Good luck!

$\endgroup$
  • 1
    $\begingroup$ Nice one, and congrats on your work. $\endgroup$ – Mindwin Sep 17 at 12:34
41
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ @DmitryKamenetsky Thanks, this is a pretty nice puzzle! $\endgroup$ – PiIsNot3 Sep 16 at 5:17
  • 6
    $\begingroup$ I'm interested how you achieved this result? By hand or did you write an algorithm? Either way, what was the process? $\endgroup$ – Euphoric Sep 16 at 12:42
  • 4
    $\begingroup$ @Euphoric Seems like it'd be pretty straightforward. Just place the square of mines around the 8 first, which obviously has to go in a corner to make room for the others. After that the 7 is pretty obvious as well, and then there's very few possibilities for where to place the rest of them. Process of elimination could cover the remaining numbers easily. $\endgroup$ – Darrel Hoffman Sep 16 at 13:24
  • 6
    $\begingroup$ @DarrelHoffman I think that is only straightforward when you look at final layout. $\endgroup$ – Euphoric Sep 16 at 13:28
  • 2
    $\begingroup$ @Euphoric I added a rigorous explanation of my process that I hope is clear enough. I do agree it’s not that straightforward as there are several cases that need to be studied carefully before making any definite statements $\endgroup$ – PiIsNot3 Sep 17 at 9:12
18
$\begingroup$

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();
        }
    }

}

$\endgroup$
  • $\begingroup$ This doesn't include: xxxx2,xx8x4,xxxxx,3567x,1xxxx. The reason I'm confident this is not a listed solution is the 8 is not towards a corner but rather an edge. $\endgroup$ – matt_rule Sep 16 at 15:59
  • $\begingroup$ @matt_rule the zero seems to be missing. $\endgroup$ – Bass Sep 16 at 16:55
  • 12
    $\begingroup$ If you have some "validity preserving" transformations (like flipping or rotating), that always make valid positions from valid ones, and invalid positions from invalid ones, then it makes sense to say that two solutions to the puzzle are different iff one cannot be transformed into the other by such transformations. So I'd say there are two solutions, each one with 8 possible ways to place it on the board. $\endgroup$ – Bass Sep 16 at 17:06
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Actually I've included the solutions here: oeis.org/A302980/a302980.txt $\endgroup$ – Dmitry Kamenetsky Sep 17 at 4:36
  • 1
    $\begingroup$ Oh wow. Sorry I didn't notice it was your own OEIS submission. Per Marco13's answer, I wonder how many distinct non-axially/rotationally-symmetric solutions there are for each n (assume WLOG the top-left corner is 012x, I suppose). $\endgroup$ – smci Sep 17 at 5:13
  • 1
    $\begingroup$ @dmitry you should post them here. If for some reason oeis.org goes down, your answer is worthless. The stack exchange guidelines and community dislikes link-only solutions because of that. Links rots. $\endgroup$ – Mindwin Sep 17 at 12:33
  • 1
    $\begingroup$ Also, congrats on doing that research and getting your sequence published last year. $\endgroup$ – Mindwin Sep 17 at 12:33
  • 1
    $\begingroup$ @Mindwin I agree out of principle that there should be more than links in an answer. But the OEIS is one of the few sites where the "Link Rot" argument makes me smirk: It's twice as old as stackexchange, and I'm sure that it will never-ever go down permanently (or: not before SE goes down). However, @Dmitry: Did you find solutions for larger boards, or discover any rule? I mean, could you compute a(100), for that matter? $\endgroup$ – Marco13 Sep 17 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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