2026-08-13T10:01:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12773 2024-03-06T10:49:09Z ddc:004 open_access

A Phase Transition in Minesweeper Dempsey, Ross Guinn, Charles Complexity of Games Minesweeper We study the average-case complexity of the classic Minesweeper game in which players deduce the locations of mines on a two-dimensional lattice. Playing Minesweeper is known to be co-NP-complete. We show empirically that Minesweeper exhibits a phase transition analogous to the well-studied SAT phase transition. Above the critical mine density it becomes almost impossible to play Minesweeper by logical inference. We use a reduction to Boolean unsatisfiability to characterize the hardness of Minesweeper instances, and show that the hardness peaks at the phase transition. Furthermore, we demonstrate algorithmic barriers at the phase transition for polynomial-time approaches to Minesweeper inference. Finally, we comment on expectations for the asymptotic behavior of the phase transition. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ross Dempsey and Charles Guinn 2020 Is Part Of LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2021.12 urn:nbn:de:0030-drops-127735 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.12 eng https://creativecommons.org/licenses/by/3.0/legalcode