11
$\begingroup$

You have an $m$ by $n$ rectangular grid. Each cell may contain a single bomb or a number (or neither, but not both). If a cell has no bomb and is adjacent (horizontally, vertically or diagonally) to atleast 1 bomb-containing cell, then it must have a number. The number (between $1$ and $8$) is the number of cells adjacent to it that contain bombs. This is how you must set up a grid for the opponent.

All cells with numbers are visible to the opponent. All cells with bombs and all empty cells look the same, these are the ones that need to be probed. The opponent picks up one cell at a time. If he picks up a bomb, he loses. If he picks up every blank cell, but no bomb, he wins.

Is it possible to set up a grid, where the opponent cannot use logic alone to win, and will have to use guesswork at some point? If so, please give the smallest* possible grid setup.

Twist: Instead of a 2D grid, if we have a 3D grid ($l$ by $m$ by $n$). All rules same as above, except that now a number could be anything between $1$ and $26$. What is the smallest* unsolvable grid setup?

*smallest in terms of area/volume of grid, not number of bombs

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ The opponent cannot use any logic for his first move. So if no special rules apply to the first move the answer is trivial. $\endgroup$
    – kasperd
    Jun 26, 2015 at 6:59
  • 6
    $\begingroup$ @kasperd All cells with numbers are visible to the opponent - opponent will use this to make first move. Yes, this is not 'classic' Windows minesweeper :) $\endgroup$
    – nevermind
    Jun 26, 2015 at 8:21
  • $\begingroup$ @nevermind Thanks, now the question makes sense to me. $\endgroup$
    – kasperd
    Jun 26, 2015 at 8:50
  • $\begingroup$ I made an interactive playground to calculate bomb probabilities given the numbers here codegolf.stackexchange.com/a/24179/315 $\endgroup$
    – Dr. belisarius
    Jun 27, 2015 at 4:25

6 Answers 6

Reset to default
21
$\begingroup$

As has been pointed out, the smallest possible 2D grid is

1x3, which looks like: 

X 1 X

If we discount any grids with a length of 1 on either side, then the smallest possible 2D grid is

2x3, which looks like: 

X 2 X
X 2 X

For a 3D grid (assuming no side can have a length of 1), the smallest grid is

2x2x3, which has the following faces: 

X 4 X     X 4 X
X 4 X     X 4 X

Therefore, a possible layout of unsolvable grids (and the rule that describes the smallest examples for each dimensional count) can be summarized as

Grids where the numbers are rotationally symmetrical and the bombs/empty spaces are not rotationally symmetrical, meaning that if the entire grid is rotated 180 degrees, the numbers would match up with the original grid, but the bombs and blank spaces would not. Note that this is not all-inclusive: Grids that follow this pattern are always unsolvable, though there are unsolvable grids that do not follow this pattern.

Improve this answer
$\endgroup$
5
  • $\begingroup$ If there are two bombs, the '1's should be '2's $\endgroup$
    – dfperry
    Jun 25, 2015 at 15:55
  • $\begingroup$ This assumes a single bomb, where the X's are either bombs or blanks. $\endgroup$
    – Bailey M
    Jun 25, 2015 at 15:55
  • 3
    $\begingroup$ it is not true that the entire grid must be rotationally symmetrical, only a portion of it needs to be. For example, the 3x3 grid with rows: X X X X 5 X X 2 X is not solvable without guesswork, and is not rotationally symmetrical (but does have such a portion) $\endgroup$
    – durron597
    Jun 25, 2015 at 20:17
  • $\begingroup$ True, and there are fully symmetrical grids that are unsolvable as well - I think X 2 X 2 X | X 3 X 3 X | X 2 X 2 X also falls under that rule. My assertion, while poorly worded, is simply that grids where the numbers are rotationally symmetrical but the bombs are not are unsolvable. $\endgroup$
    – Bailey M
    Jun 26, 2015 at 13:37
  • $\begingroup$ @BaileyM The edit would be too substantial for me to do it, but could you edit your answer to improve the wording? $\endgroup$
    – durron597
    Jun 26, 2015 at 16:31
16
$\begingroup$

A 1x3 grid will work

? 1 ?

(Where a question mark is either a blank or a mine)

No 2x2 grid will work because all cells are adjacent to one another

Edit: I suppose that one might not qualify as a 2-dimensional grid, because then it would be a 1x1x3 3-D grid too. The following 3x3 grid should be fine:

? 1 ?
1 2 1
? 1 ?
Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ If 1x3 doesn't count, then a 2x3 would be the smallest: [?][2][?] [?][2][?] $\endgroup$
    – Ninety-Three
    Jun 25, 2015 at 16:17
  • $\begingroup$ @Ninety-Three: Ah, good point. A 2x2x3 mine space can be constructed the same way, with 4 ambiguous spaces, then 4 spaces marked by '4's, then 4 more ambiguous spaces $\endgroup$
    – WellWell
    Jun 25, 2015 at 16:27
10
$\begingroup$

The smallest grid with that property is the 1 by 1 grid showing no numbers. It also has a maximum of uncertainty.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ If there is a bomb the opponent has won already. He has to pick all the blank cells, but since there are none, he has won before the game starts. If there is no bomb the opponent hasn't won already and then it is clear that he must choose the only cell to win. $\endgroup$
    – kasperd
    Jun 26, 2015 at 6:55
  • $\begingroup$ The player has to decide when to stop, so this is really the smallest possible example. $\endgroup$
    – Eiko
    Jun 26, 2015 at 9:20
  • $\begingroup$ Interesting solution.... $\endgroup$
    – ghosts_in_the_code
    Jun 26, 2015 at 15:34
3
$\begingroup$

A simple 1x3 grid can be unsolvable:

?1?

The solution doesn't rely on the grid's trivial size, as you can create unsolvable repeating columns in an arbitrarily large grid (as long as m or n is odd).

?2?3?2?
?3?3?3?
?3?3?3?
?2?2?2?

Improve this answer
$\endgroup$
1
  • $\begingroup$ You're right, but Wellwell beat you to it. $\endgroup$
    – ghosts_in_the_code
    Jun 26, 2015 at 15:38
1
$\begingroup$

Wellwell already gave the best answer. If you want it to be embeddable in a larger grid - that is, if you don't want it to depend on the border - then it's impossible if the player is automatically notified when they've won. Here's a proof.

Let's take a minimal embeddable grid. "Minimal" in this sense doesn't mean that it's the smallest possible - it just can't have any extraneous mines that are instantly detectable.

Now let's look at this grid. The top left corner looks like this:

.-----------
|A B C X ...
|D E F X ...
|X X X X ...
|...

A, B, C, or D cannot contain mines; if they were embedded in a larger grid, then it would be immediately possible to figure that out.

Assume A contains a number. That number must be 1, and therefore E must have a mine. The puzzle must not have any extraneous mines; contradiction.

Therefore A must be blank, and E must have a number or blank.

Now we relabel the squares.

.-------------
|  A B C X ...
|X D E F X ...
|X X X X X ...
...

The same proof shows that once again the square now labeled A must be blank.

Continuing to the edge of the grid:

          ---.
  ...     A B|
  ...   X D E|
        X X X|
          ...|

We know from the previous iteration that D must be a number or a blank. Because A, B, and E are on the border, none of them can be mines. Therefore, there are no mines in the top two rows - the entire top row must be blank. There are also no mines in the bottom row because the grid must be embeddable, as shown at the beginning. The grid must have no size at all; contradiction.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ You can't have a blank in the middle of a bunch of mines, though. That would be a number, and thus revealed $\endgroup$
    – StephenTG
    Jun 25, 2015 at 16:23
  • $\begingroup$ @StephenTG You're right. I don't know why I didn't notice that. $\endgroup$
    – Deusovi ♦
    Jun 25, 2015 at 16:36
0
$\begingroup$

A few answers state that the smallest possible 2D grid (not allowing either side's length to be 1) is 2x3:

? 2 ?
? 2 ?

But it is possible for a 2x2 grid to be unsolvable. Here are a few examples:

? 1    1 ?    2 ?
1 ?    ? ?    ? ?

The same can be said of a 2x2x2 grid in 3D. For example, if one of the eight cells is a number less than seven and the other seven are unknown, it is impossible to determine which cells contain mines.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I originally thought that as well, but keep in mind that EVERY number has to be revealed. In a 2x2 grid, since every square touches every other square, all squares are either bombs or numbers and the answers are non-trivial. $\endgroup$
    – Bailey M
    Jul 1, 2015 at 18:13
  • $\begingroup$ I knew I was missing something. $\endgroup$
    – MooneyA
    Jul 1, 2015 at 18:18
  • $\begingroup$ If you look at the edit history on my answer, I said the exact same thing. xD $\endgroup$
    – Bailey M
    Jul 1, 2015 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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