Thursday, December 1, 2016

logical deduction - Unsolvable static minesweeper puzzle? (+ 3D twist!)


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



Answer



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.



No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...