Minesweeper may not be NP-complete but is hard nonetheless
type: Item
instance of: scholarly article
title: Minesweeper may not be NP-complete but is hard nonetheless
zbMATH Open document ID: 1248.68223
author: Allan Scott
author: Ulrike Stege
author: Iris van Rooij
published in: The Mathematical Intelligencer
publication date: 2012-01-29T00:00:00Z
review text: 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?
reviewed by: Heribert Vollmer
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 97A20
zbMATH DE Number: 6002565
zbMATH Keywords: Minesweeper
zbMATH Keywords: computational complexity
zbMATH Keywords: NP-completeness
Wikidata QID: Q63285632
MaRDI profile type: Publication
full work available at URL: s00283-011-9256-x
OpenAlex ID: W2126010852
DOI: 10.1007/S00283-011-9256-X
description: scientific article; zbMATH DE number 6002565