Minesweeper may not be NP-complete but is hard nonetheless (Q660171)

Minesweeper is a widely known computer game in which the player has to locate hidden mines on a board of squares. In a famous article, R. Kaye proved that the consistency problem for minesweeper is NP-complete. This is the problem, given a board showing in some squares mines and in some other squares numbers corresponding to the number of neighbouring mines, to determine if it describes an actual minesweeper configuration. Kaye very nicely develops gadgets that simulate wires and switching gates on the board, leading to a reduction of the NP-complete satisfiability problem for propositional formulas, SAT, to the minesweeper consistency problem. In the present paper it is shown that the following problem is coNP-complete: Given a consistent board, is there at least one square whose content (mine or empty) can be inferred?