Minesweeper

Description

Minesweeper is an interactive puzzle played on a rectangular $n \times m$ board in which each tile is either empty or contains one out of a total of $k$ mines. Initially the contents of all the location are hidden. A move consists of selecting an hidden tile to reveal: if the tile contains a mine the player loses the game immediately, otherwise the tile is revealed as empty and it is labeled with the number of adjacent tiles that contain a mine, where two distinct tiles are considered to be adjacent if each of their coordinates differ by at most $1$ (i.e., each tile is adjacent to up to 8 tiles). The player knows the value of $k$ in advance and wins when all the empty tiles are revealed.

Some common implementations of the game recursively reveal all the neighbors of a tile labeled with “$0$” (which might be displayed as an empty tile) and allow the player to mark the tiles as definitely or possibly containing a mine.

Computational complexity

A configuration consists of a board whose revealed tiles are labeled and whose unrevealed squares are possibly marked as mines. A configuration is consistent if there exists a placement of the $k$ mines such that all the marked squares contain a mine and all the labels correspond to the number of adjacent mines.

The (decision version of) minesweeper inference problem [2] asks to determine, given a consistent configuration, whether there exists a covered square that either (i) is unmarked and definitely contains a mine, or (ii) is definitely empty. Minesweeper inference is co-NP-complete (a no-certificate consists, for each covered tile, of a pair of consistent configurations that disagree on that tile) [2].

The minesweeper consistency problem [1] asks to decide whether a given configuration is consistent. Minesweeper consistency is NP-complete.

Any algorithm for minesweeper consistency yields an algorithm for minesweeper inference with a $O(n \cdot m)$-time blow-up. [1] [2]

The variant in which the game is played on a tesellation of the hyperbolic plane and the goal is to determine whether a given input configuration is consistent is in P, as shown by a more general result in [3].

References

[1] R. Kaye, “Minesweeper is NP-complete”, The Mathematical Intelligencer, 2000.

[2] A. Scott, U. Stege, I. van Rooij, “Minesweeper May Not Be NP-Complete but Is Hard Nonetheless”, The Mathematical Intelligencer, 2011.

[3] E. Kopczyński, “Hyperbolic Minesweeper Is in P”, in FUN 2020.

@misc{cog:minesweeper,
    author = "{CoG contributors}",
    title  = "{Minesweeper --- Complexity of Games}",
    year   = "2024",
    url    = "https://www.isnphard.com/i/minesweeper/",
    note   = "[Online; accessed 2024-05-28]"
}