Minesweeper Math Papers

Introducing Proof Techniques Using The Logical Game Mine Hunter (1995)
PRIMUS, 5:2, 108-112

Allan Struthers uses Mine Hunter (an early Windows Minesweeper rival) to introduce proof techniques.

A Mathematical Introduction to the Game of Minesweeper (1997)
The UMAP Journal, Vol. 18, No. 1, 35-42

Philip Crow introduces a Minesweeper notation system and defines several theorems on what can and cannot be known from some common mine configurations. The paper includes an early description of the 1-2-1 pattern and the first mention of "relative" patterns where mines touching numbers can reduce those numbers to a known pattern. Article hosted with permission from COMAP.

How Cellular Automaton Plays Minesweeper (1997)
Applied Mathematics and Computation 85, 2-3, 127–137

Andrew Adamatzky develops a two-dimensional deterministic celluar automaton for solving n*n Minesweeper lattices.

Evolving a Program to Play the Game Minesweeper (1998)
Undergraduate Thesis (Genetic Algorithms and Genetic Programming, Stanford, 2000, 137-146)

Chris Quartetti applies genetic programming to evolve a Minesweeper solver.

Minesweeper is NP-complete (2000)
Mathematical Intelligencer, Vol 22, No 2, 9-15

Richard Kaye proves Minesweeper belongs to the class of P=NP? problems. He demonstrates how to create a Minesweeper computer using boolean circuits then proves that solving Minesweeper is a satisfiability (SAT) problem thus NP-complete. (The original paper was published on his website in 1998.)

Some Minesweeper Configurations (2000)
Boletim Sociedade Portuguesea de Mathemática, Janeiro 2007, 181-189

Companion paper to Richard Kaye's famous "Minesweeper is NP-complete" paper. Kaye provides additional examples of logic gates and in this updated version from 2007 he comments on Kadlac's 2003 "Minesweeper Consistency" paper.

Infinite versions of minesweeper are Turing complete (2000)
Unpublished (University of Birmingham)

Richard Kaye explores the consistency problem for infinite versions of Minesweeper and proves the game is Turing complete. This is the updated version of the paper from 2007.

Evolving Strategies for the Minesweeper Game using Genetic Programming (2000)
Undergraduate Thesis (Genetic Algorithms and Genetic Programming, Stanford, 2000, 312-318)

Stephen Rhee applies genetic programming to evolve a Minesweeper solver.

En studie i röj (2000)
Master Thesis (Umeå Universitet)

Lindgren calculates mine probabilities using combinatorics, algebra and matrices. Source code is shared for a solver capable of solving a 4*4 grid and he demonstrates that starting in corners increases the chance of winning.

Minesweeper as a Constraint Satisfaction Problem (2001)
Graduate Term Paper (University of Toronto)

Chris Studholme uses Ramsdell's PGMS solver (1995) to test constraint satisfaction solving strategies. Three strategies are implemented in three modes for Microsoft Minesweeper with a CSP implementation producing world record win ratios of 80.0% on Beginner and 33.9% on Expert.

The Minesweeper Game: Percolation and Complexity (2002)
Combinatorics, Probability & Computing, 11 (5), 487-499

Elchanan Mossel uses perculation theory to calculate safe paths within an infinite Minesweeper lattice.

How Complicated is Minesweeper? (2003)
Public Lecture (University of Birmingham)

Lecture by Richard Kaye on his famous "Minesweeper is NP-complete" paper.

Learning Minesweeper with Multirelational Learning (2003)
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence

Machine learning is used to create a Minesweeper solver (Mio). Four learning models are tested and combined to create an optimal strategy with a 52.4% win rate on Beginner level when the first click is allowed to be a mine. Results are compared to Ramsdell's PGMS solver (1995).

Explorations of the Minesweeper Consistency Problem (2003
Undergraduate Thesis (Oregon State University)

Meredith Kadlac develops a solver in C++ to explore minesweeper consistency in one dimension.

Minesweeper, #Minesweeper (2003)
Unpublished (University of Berkeley)

Nakov and Wei define Minesweeper as a Markov Decision Problem and propose that the counting problem #Minesweeper is #P-complete. The authors explore ways to reduce state space calculations then solve various densities for grids up to 4*4.

The Complexity of Puzzles: NP-Completeness Results for Nurikabe and Minesweeper (2003)
Undergraduate Thesis (Reed College)

Brandon McPhail reviews SAT and NP-completeness and in Chapter 5 applies these concepts to Minesweeper. He shows that 3-Minesweeper (where no cell can touch more than 3 mines) is NP-complete and that ASP-Minesweeper (where multiple solutions are consistent) is also NP-complete.

Playing the Minesweeper with Constraints (2004)
International Conference on Multiparadigm Programming in Mozart/OZ

Raphaël Collet implements an Oz Minesweeper solver using constraint satisfaction techniques to calculate mine probabilities. (You can visit his Oz Minesweeper site in the Archive.)

The complexity of Minesweeper and strategies for game playing (2004)
Undergraduate Thesis (University of Warwick)

Kasper Pedersen presents a detailed review of existing Minesweeper literature and explores DP-completeness and #P-completeness. He uses Ramsdell's PGMS solver (1995) to compare strategies achieving win rates of 77.8% on Intermediate (world record) and 30.0% on Expert.

Minesweeper: A Statistical and Computational Analysis (2004)
Undergraduate Thesis (Washington State University)

Young and Fowler design and test four approaches to solving Minesweeper on 4*4 grids using linear algebra.

Develop heuristics to the popular Minesweeper game (2004)
Masters Thesis (California State University)

Angela Huang writes a C/C++ solver (Automine) which colour codes cells based on risk to help a human play XBomb on Linux. Source code is included in the paper.

Offline 1-Minesweeper is NP-complete (2004)
Unpublished (Reed College)

Fix and McPhail explore Minesweeper consistency where k clues have been revealed. They demonstrate that 8-Minesweeper, 6-Minesweeper (the case in Kaye's "Minesweeper is NP-complete" paper), 3-Minesweeper and 1-Minesweeper are also NP-complete.

Minesweeper is NP-Complete (2005)
SIGCSE Bulletin 37:39–40, December 2005

Summary of Richard Kaye's paper "Minesweeper is NP-complete".

Games en Puzzels en hun Complexiteit (2005)
Master Thesis (Hasselt University)

Filip Smets reviews literature on the complexity of games with several chapters dedicated to Minesweeper. He demonstrates NP-completeness for Minesweeper variants with triangles, hexagons and octogons and suggests this should also be true in multiple dimensions.

An Interactive Constraint Based Approach to Minesweeper (2006)
Eighteenth Innovative Applications of Artificial Intelligence Conference (AAAI 2006, 1933–1934)

Bayer, Snyder and Choueiry write a Java applet to solve Minesweeper using constraint processing techniques. The paper proposes a solution similar to Collet (2004) but implements textbook algorithms so the game can be used for teaching purposes.

Komplexität und Varianten von Minesweeper (2006)
Undergraduate Thesis (Vienna University of Technology)

Martin Heinrich reviews the NP-completeness of Minesweeper on grids and graphs then reduces SAT, Vertex Cover, Clique, Three-Dimensional Mapping and similar problems to graph problems whose properties are NP-complete.

More Properties for NP-complete Minesweeper Graphs (2006)
Undergraduate Thesis (Vienna University of Technology)

Companion paper to Heinrich's "Komplexität und Varianten von Minesweeper" (2006) with additional configurations.

Automated Strategies for the Game "Minesweeper" (2006)
Undergraduate Thesis (University of Maryland)

Patrick Armstrong proposes four solving strategies of increasing difficulty (truth, contrapositive, exhaustion, burnout) and writes a solver (MineBot) to perform tests. The simple "Truth" strategy won 5.6% of Expert games and "difficulty" appeared to rise linearly with density. The solving rate was consistent across square and rectangular grids.

Games, Puzzles, and Computation (2006)
Doctorate Thesis (MIT)

Robert Hearn explores the idea of games as computation and in the second half of the paper develops existing hardness proofs for games including Minesweeper. He clarifies that normal Minesweeper play is not NP-complete but rather the consistency problem (Kaye, 2000) is NP-complete. He claims that Minesweeper is co-NP-hard and co-NP-complete (unpublished proof) and suggests Minesweeper should be PSPACE-complete.

2xn Minesweeper Consistency Problem is in P (2007)
Unpublished (UC Santa Barbara)

Hu and Lin prove the 2 dimension case for Kadlac's "Explorations of the Minesweeper Consistency Problem" (2003) paper in 1 dimension.

‘Minesweeper’ and spectrum of discrete Laplacians (2008)
Applicable Analysis 89(12):1907-1916

German and Lakshtanov develop an algorithm for generating Minesweeper games with a guaranteed unique solution. The authors titled the original paper "Minesweeper Without a Computer" because such games can be printed and played on paper.

Applying Bayesian Networks in the Game of Minesweeper (2009)
Unpublished (Charles University & Academy of Sciences of the Czech Republic)

Vomlelová and Vomlel develop a bayesian network model for solving Minesweeper and apply rank-one decomposition to conditional probability tables in order to reduce computational complexity.

Application of Spectral Theory to Constructing a Puzzle on the Basis of the Minesweeper Computer Game (2010)
Mat. Zametki, 2010, Volume 88, Issue 6, 935–937

German and Lakshtanov build on their previous paper "Minesweeper and spectrum of discrete Laplacians" (2008) where they discuss paper based Minesweeper. In this paper they present algorithms for constructing tables that can be use to create paper based puzzle games.

Minesweeper on Graphs (2011)
Applied Mathematics and Computation 217(14):6616-6623

Shahar Golan introduces a polynomial algorithm for solving Minesweeper on graphs with bounded treewidth.

Consistent Belief State Estimation with Application to Mines (2011
International Conference on Technologies and Applications of Artificial Intelligence, Hsinchu, Taiwan, 280-285

Couetoux, Milone and Teytaud explore Minesweeper as a Partially Observable Markov Decision Process and implement Monte-Carlo tree search to estimate belief states.

Minesweeper Puzzles (2011)
INFORMS Transactions on Education 11(2):90-91

Martin Chlond briefly describes two variants of Minesweeper proposed by Kaye and du Sautoy which are consistent (no guessing required). The paper then discusses two existing programs capable of generating such solveable Minesweeper boards.

Minesweeper May Not Be NP-Complete but Is Hard Nonetheless (2011)
The Mathematical Intelligencer 33(4):5-17

Scott, Stege and Rooj demonstrate that the Minesweeper inference problem is co-NP-complete.

Combining Myopic Optimization and Tree Search: Application to MineSweeper (2012)
Learning and Intelligent Optimization (LION6), 2012, Vol 7219, 222-236

Sebag and Teytaud combine belief state estimation and tree search strategies to design an algorithm that performs more accurately but more slowly than the single point and constraint satisfaction strategies of Ramsdell's PGMS solver (1995). They combine an Upper Confidence Tree (UCT) algorithm with a CSP strategy to calculate belief state in order to reduce the Partial Observable Markov Decision Process to the Markov Decision Process case.

Optimistic Heuristics for MineSweeper (2012)
International Computer Symposium 2012, Hualien, Taiwan, 199-207

Teytaud et al. improve the Upper Confidence Tree (UCT) solving method from his earlier "Combining Myopic Optimization" (2012) paper with Sebag. The new solver produced win rates of 80.2% on Beginner, 74.4% on Intermediate and 38.7% on Expert.

The computational complexity of Minesweeper (2012)
Unpublished (Radboud University Nijmegen)

Michiel de Bondt shows Minesweeper is PP-hard and in some cases PSPACE-complete in addition to being NP-complete on hexagonal and triangular grids. (Hexagonal and triangular grids were previously shown to be NP-complete in Smets' "Games en Puzzels en hun Complexiteit" (2005) paper written in Dutch.)

MineSweeper: Where to Probe? (2012)
Research Report N° 8041, July 2012, INRIA. 2012, 26

Legendre et al. model Minesweeper as a Partially Observable Markov Decision Process (POMDP) and develop multiple solving strategies. The best win rates produced were world records of 91.4% on Beginner (9x9) and 81% on Beginner (8x8). The authors demonstrate that starting games in a corner produces higher win rates than starting games in a random cell. (This last point was previously shown but with less rigour in Lindgren's "En studie i röj" (2000) paper written in Swedish.)

TeddySweeper: A Minesweeper Solver (2013)
The 18th Game Programming Workshop, Kanagawa, Japan 2013

Wu et al. develop a solving strategy that reduces the computational complexity of a pure CSP approach. The authors claim world record win rates for all levels of 91.78% for Beginner (9x9), 81.52% for Beginner (8x8), 77.84% for Intermediate and 38.84% for Expert. (This may be correct but depends on statistical error with previous records being 91.4%, 81%, 77.8% and 38.7%).

Minesweeper strategy for one mine (2014)
Applied Mathematics and Computation 232 (2014) 292–302

Shahar Golan proposes an optimal strategy for solving Minesweeper on general graphs (multiple dimensions) when exactly one cell contains a mine. This builds on his earlier "Minesweeper on Graphs" (2011) paper.

An Approximate Tensor-Based InferenceMethod Applied to the Game of Minesweeper (2014)
PGM 2014: Probabilistic Graphical Models, 535-550

Vomlel and Tichavský expand on the earlier paper by Vomlel "Applying Bayesian Networks in the Game of Minesweeper" (2014) and develop an approximate probabilistic inference method based on the CP-tensor decomposition.

Algorithmic Approaches to Playing Minesweeper (2015)
Undergraduate Thesis (Harvard University)

Davd Becerra reviews existing single point and constraint satisfaction models for solving Minesweeper and implements an enhanced version of each strategy on Microsoft Minesweeper.

Minesweeper as a Tool of Probability (2015)
NCACCT-2015 Conference Proceedings

Gautham describes a Minesweeper game in which a computer places a mine and the user has both limited time and attempts to locate this mine. After each click the computer gives the user a probability score of finding the mine as a function of click location, remaining time and remaining clicks. A modification of this approach can be applied to network security tasks.

Circuits, Minesweeper, and NP Completeness (2015)
Lecture (UC Santa Barbara)

Summary of Richard Kaye's paper "Minesweeper is NP-complete".

Generating All Solutions of Minesweeper Problem Using Degree Constrained Subgraph Model (2016)
IPSJ SIG Technical Report Vol.2016-MPS-109 No.3 2016/7/25

Suzuki, Hao and Minato test the solving efficiency of two graph enumeration models.

A framework for visualizing hardness reductions to grid-based games (2016)
Undergraduate Thesis (MIT)

Jeffrey Shen develops a framework for reducing hard problems such as Circuit SAT into integer grids representing games. He uses Akari and Minesweeper as proofs of concept.

The One-Dimensional Minesweeper Game: What are your chances of winning? (2016)
International Journal of Modern Physics C, Volume 27, Issue 11

Rodriguez-Achach et al. calculate the probability of winning one-dimensional Minesweper games. They identify a critical mine density that minimises the probability of winning the game in one dimension.

A new data hiding algorithm based on minesweeper game for binary images (2016)
Journal of the Faculty of Engineering and Architecture of Gazi University 31(4):951-959

Tuncer et al. develop an algorithm for embedding data such as pictures into Minesweeper games.

A minesweeper game-based steganography scheme (2017)
Journal of Information Security and Applications, Vol. 32, February 2017, Pages 1-14

Mahato et al. demonstrate a method for embedding hidden messages in Minesweeper games.

Exploring Efficient Strategies for Minesweeper (2017)
Association for the Advancement of Artificial Intelligence 2017

Various solving strategies are combined to create an optimal strategy producing win rates of 81.79% on Beginner (world record), 78.22% on Intermediate (world record) and 40.06% on Expert (world record). The paper includes a table of win rates from previously published papers and confirms earlier work proving that starting in a corner increases the win rate.

Quantum Computational Speedup For The Minesweeper Problem (2017)
Masters Thesis (Uppsala University)

Terner and Hedbjörk demonstrate how a quantum algorithm using quantum logic gates can solve Minesweeper more quickly than traditional algorithms.

Minesweeper with Limited Moves (2018)
Association for the Advancement of Artificial Intelligence 2018

Gaspers et al. demonstrate Minesweeper is PSPACE-complete when you partially reveal the board and restrict the number of solving moves.

A Short Note on Improved Logic Circuits in a Hexagonal Minesweeper (2018)
Unpublished (Seoul National University)

Seunghoon Lee advances the PP-hardness proof from Bondt's "The computational complexity of Minesweeper" (2012) paper and applies logic circuits to hexagonal Minesweeper. (For additional research on hexagonal circuits see Smet's ""Games en Puzzels en hun Complexiteit" (2005) paper.)

A Minesweeper Solver Using Logic Inference, CSP and Sampling (2018)
Unpublished (Shanghai Tech University)

Tang, Jiang and Hu implement a Minesweeper solver using four strategies (logic inference, grouping, CSP, sampling). Code published on Github.

Complexity of Minesweeper with Restricted Number Sets (2018)
Masters Thesis (MIT)

Ray Wu explores Minesweeper consistency when the set of possible numbers i.e., {0,1,2,3,4,5,6,7,8} is restricted.

Simulations and Analysis of Adiabatic Quantum Annealing (2018)
Undergraduate Thesis (School of Engineering Sciences KTH)

Shen and Wallin explore the properties of a quantum annealer. The final page of the paper explains how this can be used to solve Minesweeper in any dimension.

A Phase Transition in Minesweeper (2020)
Unpublished (University of Princeton)

Dempsey and Guinn show that Minesweeper undergoes a phase transition at a critical density and that Minesweeper hardness peaks at this transition.

Hyperbolic Minesweeper is in P (2020)
Unpublished (University of Warsaw)

Eryk Kopczyński shows that hyperbolic variants of Minesweeper are in P.

Critical exponents and the universality class of a minesweeper percolation model (2020)
International Journal of Modern Physics C

Qing, You and Liu introduce a Minesweeper percolation model and use Monte-Carlo simulations to identify critical mine density.

Multi-Armed Bandits for Minesweeper: Profiting from Exploration-Exploitation Synergy (2020)
Unpublished (Centro Federal de Educação Tecnológica)

Lordeiro and Cardoso use reinforcement learning and adapt multi-armed bandit algorithms for Minesweeper. Their solver completes 74% of Beginner and 44% of Intermediate games. Interestingly, this was the first paper to incorporate flagging mines into its algorithms.