Minesweeper is NP-complete.

DOI10.1007/BF03025367zbMath1052.68624OpenAlexW2091711673WikidataQ56687816 ScholiaQ56687816MaRDI QIDQ5949249

Richard W. 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)

Related Items (17)

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

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