Minesweeper may not be NP-complete but is hard nonetheless

DOI10.1007/S00283-011-9256-XzbMATH Open1248.68223OpenAlexW2126010852WikidataQ63285632 ScholiaQ63285632MaRDI QIDQ660171FDOQ660171

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

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

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)

Cited In (12)

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

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)