How Minesweeper Solvers Work: Algorithms Explained
A Minesweeper solver is a program that analyzes a partially revealed board and determines which covered cells are safe, which are mines, and which are uncertain. The solver on Minesweeper Blast uses these techniques to help you learn — but understanding how it works reveals deep connections between Minesweeper, computer science, and mathematics.
The Problem: Constraint Satisfaction
Every revealed number creates a constraint: “exactly $n$ of my 8 neighbors are mines.” A Minesweeper board is a constraint satisfaction problem (CSP) — a set of variables (cells: mine or safe?) with constraints (numbers) that must all be simultaneously satisfied.
Formally:
- Variables: Each covered cell $c_i$ has value 0 (safe) or 1 (mine)
- Constraints: For each revealed number $n$ at position $(r,c)$, the sum of its unrevealed neighbors equals $n$ minus already-flagged neighbors
$$\sum_{(i,j) \in \text{neighbors}(r,c)} c_{ij} = n - \text{flags}(r,c)$$
A solver’s job is to determine which variables are forced to be 0 or 1 by the constraints.
Level 1: Single-Cell Constraint Resolution
The simplest solving technique. For each revealed number:
All Mines
If the number of remaining mines needed equals the number of covered neighbors:
$$n - \text{flagged} = \text{covered}$$
Then every covered neighbor is a mine. Flag them all.
Example: A “3” with 2 flagged neighbors and 1 covered neighbor → that covered cell is a mine.
All Safe
If all mines are accounted for:
$$n - \text{flagged} = 0$$
Then every covered neighbor is safe. Reveal them all (this is chording).
Example: A “2” with 2 flagged neighbors and 3 covered neighbors → all 3 covered cells are safe.
Complexity
This is $O(cells \times neighbors)$ — very fast. It runs in a single pass over the board and is repeated until no more progress can be made. It solves roughly 60–70% of cells on a typical no-guess board.
Level 2: Subset Logic (Constraint Pairing)
When single-cell logic stalls, compare pairs of constraints.
The Principle
If constraint A’s unknown cells are a subset of constraint B’s unknown cells:
$$S_A \subseteq S_B$$
Then the cells in $S_B \setminus S_A$ (B’s extra cells) must contain exactly $m_B - m_A$ mines, where $m_A$ and $m_B$ are the remaining mine counts.
If $m_B - m_A = 0$: all extra cells are safe (subset safe). If $m_B - m_A = |S_B \setminus S_A|$: all extra cells are mines (subset mine).
Example
Number A (a “1”) has unknown neighbors: {cell1, cell2}. Needs 1 mine. Number B (a “2”) has unknown neighbors: {cell1, cell2, cell3}. Needs 2 mines.
${cell1, cell2} \subset {cell1, cell2, cell3}$ → cell3 must contain $2 - 1 = 1$ mine. Since cell3 is the only extra cell, it is a mine.
This is the generalized logic behind 1-2-X, 1-1-X, 1-2-1, and all subset patterns.
Complexity
Comparing every pair of boundary constraints is $O(b^2)$ where $b$ is the number of boundary constraints. On Expert boards, $b$ ≈ 50–100, so this is fast.
Level 3: Backtracking Search
When levels 1 and 2 stall, the solver needs to consider multiple possibilities simultaneously.
How It Works
- Pick an undetermined cell on the boundary
- Assume it is a mine → propagate using levels 1–2
- If contradiction → the cell must be safe
- Assume it is safe → propagate using levels 1–2
- If contradiction → the cell must be a mine
- If both are consistent → the cell is truly ambiguous
- Repeat for each undetermined cell
Contradiction Detection
A contradiction occurs when any constraint becomes impossible:
- A number requires more mines than it has covered neighbors
- A number requires fewer mines than it has flagged neighbors (negative remaining)
- The global mine count is exceeded
Optimization: Boundary Analysis
The solver only needs to consider cells on the boundary (covered cells adjacent to at least one revealed number). Interior cells (covered, far from revealed numbers) have no constraints and cannot be resolved until the boundary reaches them.
On Expert boards, the boundary typically has 20–40 cells while the total board has 480. Searching only boundary cells reduces the problem dramatically.
Complexity
In the worst case, backtracking is exponential: $O(2^b)$ where $b$ is the number of boundary cells. In practice, constraint propagation prunes the search tree heavily, and real boards take milliseconds. But this exponential worst case is why Minesweeper is NP-complete.
Level 4: Probabilistic Analysis
When exact determination is impossible (a true 50/50), a solver can calculate the exact probability that each cell is a mine.
Method: Enumerate All Consistent Configurations
- Generate every possible assignment of mines to boundary cells that satisfies all constraints
- Include the global mine count constraint (total mines remaining)
- For each cell, count the fraction of valid configurations where it is a mine
- The cell with the lowest mine probability is the safest guess
Example
If a cell is a mine in 30 out of 100 valid configurations, it has a 30% probability of being a mine. A “50/50” is literally a cell that is a mine in 50% of valid configurations.
Boundary Partitioning
Smart solvers partition the boundary into independent groups — subsets of cells with no constraint connections between them. Each group can be analyzed separately, reducing the combinatorial explosion.
If the boundary splits into groups of size 8, 10, and 12, the search is $O(2^8 + 2^{10} + 2^{12})$ instead of $O(2^{30})$ — a massive speedup.
Global Mine Count Integration
The total number of mines remaining constrains which combinations are valid. A group that looks ambiguous locally may be resolved by the global mine count:
- Region A has 5 cells and could contain 2 or 3 mines
- Region B has 3 cells and could contain 1 or 2 mines
- Mine counter says 4 remaining total
- If Region A has 3 mines, Region B has 1 → consistent
- If Region A has 2 mines, Region B has 2 → consistent
- But wait: the interior (non-boundary cells) also has possible mines
This global reasoning sometimes resolves cells that group-level analysis cannot.
Complexity
Exact probability calculation is #P-hard — even harder than NP-complete. In the worst case, counting all valid configurations is exponential. But with boundary partitioning and constraint propagation, real boards are solvable in milliseconds.
How No-Guess Boards Are Generated
The no-guess algorithm uses a solver during board creation:
- Place mines randomly (avoiding the first-click cell and its neighbors)
- Run the solver using levels 1–3 (single-cell + subset + backtracking)
- If the solver clears the entire board: the board is no-guess. Accept it.
- If the solver gets stuck: reject the board and generate a new one.
On Beginner (9×9, 10 mines), ~85–95% of random boards are no-guess solvable. On Expert (30×16, 99 mines), only ~30–50% are. The generator may need 2–3 attempts for Expert.
Minesweeper Blast uses this process for every game, ensuring you never face an unsolvable position.
What Solvers Cannot Do
Solve Unsolvable Boards
If a board has a true 50/50, no algorithm can resolve it — the information does not exist. A probabilistic solver can identify the 50/50 and give exact probabilities, but it cannot guarantee the correct guess.
Think Like a Human
Solvers use systematic enumeration. Humans use pattern recognition — identifying configurations (1-2-1, subset, reduction) without explicitly computing constraint equations. Solvers and humans arrive at the same answers through very different cognitive processes.
Run Instantaneously on All Boards
While real boards take milliseconds, contrived worst-case boards can take exponential time. This is academic — no generated Minesweeper board at standard sizes creates this problem — but it is why the NP-completeness result matters theoretically.
Practical Use: Learning With Solvers
The Minesweeper Blast solver is designed as a learning tool:
- Enter your current board position
- The solver highlights: green (safe), red (mine), gray (uncertain)
- Compare to your deduction: did you miss a safe cell? Was a cell you thought was a 50/50 actually solvable?
- Study the difference to identify patterns you don’t yet recognize
This is the fastest way to discover patterns you are missing. If the solver resolves a cell you couldn’t, the surrounding configuration is a pattern worth studying.
What to Do Next
- Use the solver — analyze your current board position
- Learn the patterns — the human-readable version of solver logic
- Study probability — understand the math behind uncertainty
- Play no-guess Minesweeper — every board is solvable by these algorithms
- Explore NP-completeness — the deeper mathematics