Minesweeper may not be NP-complete but is hard nonetheless

DOI10.1007/S00283-011-9256-XMaRDI QIDQ660171zbMATHOpenAlexWikidataFDO

Authors Allan Scott, Ulrike Stege, Iris van Rooij

Publication date 29 January 2012

Published in The Mathematical Intelligencer (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00283-011-9256-x

zbMATH Keywords

computational complexityNP-completenessMinesweeper

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Minesweeper on graphs
• A phase transition in Minesweeper
• Hyperbolic Minesweeper is in P
• Strategy and Complexity of The Game of Squares
• `Minesweeper' and spectrum of discrete Laplacians

Cited in

(14)

• LaserTank is NP-Complete
• Minesweeper on graphs
• Knowledge-based programs as succinct policies for partially observable domains
• Covert computation in self-assembled circuits
• Rikudo is NP-complete
• Covert computation in self-assembled circuits
• A phase transition in Minesweeper
• Hyperbolic Minesweeper is in P
• `Minesweeper' and spectrum of discrete Laplacians
• The Minesweeper Game: Percolation and Complexity
• \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\)
• Luckless graphical minesweeper
• Application of spectral theory to constructing a puzzle on the basis of the Minesweeper computer game
• Minesweeper strategy for one mine

This page was built for publication: Minesweeper may not be NP-complete but is hard nonetheless

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q660171)