Minesweeper Math Papers

Introducing Proof Techniques Using The Logical Game Mine Hunter (1995)

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

A Mathematical Introduction to the Game of Minesweeper (1997)

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)

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

Evolving a Program to Play the Game Minesweeper (1998)

Chris Quartetti applies genetic programming to evolve a Minesweeper solver.

The Minesweepers' Bayesian Guide to Survival (1998)

Ṕal Ruj́an discusses whether a neural network could solve Minesweeper and proposes several strategies. He also discusses how different approaches could be used to solve real-world problems.

Minesweeper is NP-complete (2000)

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)

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)

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)

Stephen Rhee applies genetic programming to evolve a Minesweeper solver.

En studie i röj (2000)

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)

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)

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

How Complicated is Minesweeper? (2003)

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

Explorations of the Minesweeper Consistency Problem (2003)

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

Minesweeper, #Minesweeper (2003)

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)

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.

Learning Minesweeper with Multirelational Learning (2003)

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

Search Improvements in Multirelational Learning (2004)

Castillo builds on his earlier 2003 paper ("Learning Minesweeper with Multirelational Learning") and combines multirelational learning with active learning to create an active inductive model. He improves the solving rate on Beginner from 52.4% to 53.6% when the first click can be a mine.

Playing the Minesweeper with Constraints (2004)

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)

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)

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)

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)

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)

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

Games en Puzzels en hun Complexiteit (2005)

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.

Teaching Proofs and Algorithms in Discrete Mathematics with Online Visual Logic Puzzles (2005)

Cigas and Hsin explore using puzzle games to teach logic. Minesweeper and nonograms are reviewed.

An Interactive Constraint Based Approach to Minesweeper (2006)

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)

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)

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

Automated Strategies for the Game "Minesweeper" (2006)

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)

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)

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)

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)

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)

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)

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

Consistent Belief State Estimation with Application to Mines (2011

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)

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)

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

Combining Myopic Optimization and Tree Search: Application to MineSweeper (2012)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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

Generating All Solutions of Minesweeper Problem Using Degree Constrained Subgraph Model (2016)

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

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

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)

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)

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

Algorithms for Minesweeper Game Grid Generation (2017)

Jan Cicvárek explores various solving algorithms then implements an algorithm that can generate a minefield that is always solvable. He suggests a new difficulty rating system that can be used as an input for his new minefield generator.

A minesweeper game-based steganography scheme (2017)

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

Exploring Efficient Strategies for Minesweeper (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)

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)

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)

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)

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)

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)

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.

Minesweeper is NP-Complete (2018)

Ben-Ari reviews Kaye's famous paper and presents similar logic gates and circuits. He originally published a short summary in ACM SIGCSE Bulletin in December 2005.

A Phase Transition in Minesweeper (2020)

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)

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

Critical exponents and the universality class of a minesweeper percolation model (2020)

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)

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. The paper was later published in IEEE Transactions on Games PP(99):1-1 in 2021.

Fast constraint satisfaction problem and learning-based algorithm for solving Minesweeper (2021)

Sinha et al. model Minesweeper as Constraint Satisfaction Problem (CSP) and Markov Decision Process (MDP). They perform a deterministic solution search (DSScsp) and use heuristics to train classification models including XGBoost and Q-Learning. The results of 11 solving approaches are then compared for speed and accuracy for different board sizes and densities.

Grid Puzzles (2021)

Adrian Groza explores how to model Minesweeper using First Order Logic.

A solver of single-agent stochastic puzzle: A case study with Minesweeper (2022)

Liu et al. propose a 'PAFG' solver strategy. They achieved solving rates of 87.9% (9x9), 78.2% (16x16) and 39.7% (30x16). When the first click is guaranteed to be an opening the solving rate improved to 96.4% (9x9), 86.3% (16x16) and 45.6% (30x16).

A Simple Minesweeper Algorithm (2023)

Sheppard rephrases the Minesweeper problem in terms of information theory and entropy optimization.