Criteria for solvable Minesweeper game?
Minesweeper is a computer game that works on a rectangular grid of squares. Initially, all the squares are shown blank. A known number of "mines" are distributed under the squares, but their locations are unknown to the player. The object of the game is to uncover all the squares by flagging each as a mine or empty. If you flag a mined square as empty, the mine "blows up" and you lose the game. You win when all the squares have been correctly flagged. Having an empty square flagged as a mine prevents completing the game.
When flagging an empty square, the number of adjacent mines to that square is shown as a number in that square. Adjacent is both on the side and corner. A square can therefore be adjacent from 0 to 8 mines.
For more details on Minesweeper, see https://minesweeper.online.
I like to play the "no guessing mode" version on that web site sometimes. I usually do the "evil" configuration. Sometimes I get to the end of a game, and there seems to be no way to determine the solution from the available clues. You know how many mines are left, but there is more than one possible configuration that satisfies the constraints uncovered so far. In short, you have to guess.
This made me think how to create a game to avoid having to guess. Clearly just randomly placing mines is insufficient to guarantee a solvable (without guessing) game. However, what is sufficient? If I were to write a computer program to place mines in the grid to create a game, how can that be done to guarantee the game is solvable?
One obvious criterion is that all the open squares be connected. If a set of squares are "walled off" with mines, then there is no way to get clues to the mines inside from the outside. But, just being connected is insufficient.
For a computer-generated grid, one strategy would be to write a solver. If the computer can solve the grid, then it must be solvable. Mine placement could be varied until a solvable configuration is found. That would work, but is rather unsatisfying. I'm looking for explicit rules of solvability.
Can we assume that this applies, so the player has at least 1 uncovered square to start with?
Yes. I'm willing to give the first square to a player to guarantee no guessing required.
The total number of mines is known, so if there are multiple disconnected open regions but all but one of them are simply connected (have no mines in their interiors), could that not also be solvable?
I guess you're right that connectedness is not required in the special case when all the unconnected parts have zero mines. Another exception is when the number of unconnected unknown squares is equal to the number of remaining mines and the connected part has been completely solved.
I'd be fine with never having games with those cases.
0 answers
2 comment threads