Minesweeper is NP-complete.

DOI10.1007/BF03025367MaRDI QIDQ5949249zbMATH OpenOpenAlexWikidataFDO

Authors Richard Kaye

Publication date 18 November 2001

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

Full work available at URL https://doi.org/10.1007/bf03025367

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(17)

• Finding smooth maps is NP-complete
• The complexity of solitaire
• Minesweeper strategy for one mine
• TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable
• NP-completeness in hedonic games
• Rikudo is NP-complete
• \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\)
• The computational complexity of Angry Birds
• On the fairness and complexity of generalized \(k\)-in-a-row games
• `Minesweeper' and spectrum of discrete Laplacians
• The complexity of speedrunning video games
• Phutball is PSPACE-hard
• TETRIS IS HARD, EVEN TO APPROXIMATE
• LaserTank is NP-Complete
• Minesweeper on graphs
• Application of spectral theory to constructing a puzzle on the basis of the Minesweeper computer game
• The complexity of flood filling games

This page was built for publication: Minesweeper is NP-complete.

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