Minesweeper is one of those games that feels simple on the surface but hides real mathematical depth. Every player has experienced the moment where logic runs out and you are forced to guess. But how often does that actually happen? And how much of the game can a computer solve with pure deduction? Building an AI solver for Minesweeper turns out to be a fascinating exercise in constraint satisfaction, probability theory, and practical algorithm design.

Having built and maintained a Minesweeper implementation on GGAMES.MOBI, I wanted to explore what it would take to build a solver that plays optimally—or as close to optimally as is computationally feasible.

Minesweeper as a Constraint Satisfaction Problem

Every revealed number on a Minesweeper board is a constraint. A cell showing "3" tells you that exactly 3 of its unrevealed neighbors contain mines. This maps directly to a constraint satisfaction problem (CSP): you have variables (the unrevealed cells, each either mine or safe), domains (mine = 1, safe = 0), and constraints (each number equals the sum of mine values among its neighbors).

The formal statement is: given a set of unrevealed cells x1, x2, ..., xn where each xi ∈ {0, 1}, and a set of constraints of the form xi + xj + xk + ... = c (where c is the displayed number minus already-flagged neighbors), find all valid assignments.

What makes Minesweeper interesting as a CSP is that determining whether a Minesweeper board is consistent is NP-complete. This was proven by Richard Kaye in 2000. In practice, however, the constraints are local (each constraint involves at most 8 cells), and boards are sparse enough that efficient solving is possible for real game boards.

Level 1: Simple Constraint Rules

The simplest solver applies two rules that every human player learns early:

function simpleSolve(board) {
    var changed = true;
    while (changed) {
        changed = false;
        for (var r = 0; r < board.rows; r++) {
            for (var c = 0; c < board.cols; c++) {
                var cell = board.get(r, c);
                if (!cell.revealed || cell.number === 0) continue;

                var neighbors = board.getUnrevealedNeighbors(r, c);
                var flagged = board.getFlaggedNeighborCount(r, c);
                var effective = cell.number - flagged;

                // All-mines rule
                if (effective === neighbors.length && effective > 0) {
                    neighbors.forEach(function(n) {
                        board.flag(n.r, n.c);
                        changed = true;
                    });
                }

                // All-safe rule
                if (effective === 0 && neighbors.length > 0) {
                    neighbors.forEach(function(n) {
                        board.reveal(n.r, n.c);
                        changed = true;
                    });
                }
            }
        }
    }
}

This simple solver loops until no more progress can be made. It solves a surprisingly large portion of beginner and intermediate boards. On expert-level boards (30x16, 99 mines), it typically solves 30-50% of cells before getting stuck. That is when more advanced techniques are needed.

Level 2: Constraint Set Reduction

Human players intuitively use a technique that goes beyond the simple rules: comparing overlapping constraints to derive new information. The solver can do this systematically.

Consider two adjacent numbered cells with overlapping unrevealed neighbors. Each generates a constraint. If one constraint's cell set is a subset of another's, we can subtract to create a simpler constraint:

// Constraint A: {x1, x2, x3} = 2
// Constraint B: {x1, x2} = 1
// Subtracting B from A: {x3} = 1
// Therefore x3 is a mine.

// Constraint C: {x4, x5, x6} = 2
// Constraint D: {x4, x5, x6, x7} = 2
// Subtracting C from D: {x7} = 0
// Therefore x7 is safe.

The algorithm maintains a list of active constraints and repeatedly tries to find subset relationships:

function reduceConstraints(constraints) {
    var changed = true;
    while (changed) {
        changed = false;
        for (var i = 0; i < constraints.length; i++) {
            for (var j = 0; j < constraints.length; j++) {
                if (i === j) continue;
                var a = constraints[i];
                var b = constraints[j];

                if (isSubset(a.cells, b.cells)) {
                    var diff = setDifference(b.cells, a.cells);
                    var newCount = b.count - a.count;
                    var newConstraint = { cells: diff, count: newCount };

                    if (!constraintExists(constraints, newConstraint)) {
                        constraints.push(newConstraint);
                        changed = true;
                    }
                }
            }
        }
        // Remove redundant constraints and apply simple rules
        constraints = cleanupConstraints(constraints);
    }
    return constraints;
}

This technique catches many situations that the simple rules miss. It is equivalent to what experienced human players do when they reason about pairs and triples of cells. On expert boards, this increases the solver's coverage to roughly 60-70% of cells before requiring probabilistic methods.

Level 3: Probability Estimation

When deduction stalls, the solver must make a guess. But not all guesses are equal. If one unrevealed cell has a 10% chance of being a mine and another has a 50% chance, the rational choice is clear. Computing these probabilities requires enumerating the valid assignments.

The approach works as follows:

  1. Identify the "frontier"—unrevealed cells adjacent to at least one revealed number.
  2. Partition the frontier into independent groups. Two frontier cells are in the same group if they share any constraint. Independent groups can be solved separately, which dramatically reduces the search space.
  3. For each group, enumerate all valid mine/safe assignments that satisfy every constraint.
  4. Count how many valid assignments have a mine at each cell. The probability is that count divided by the total number of valid assignments.
  5. Factor in the global mine count constraint: the total number of mines across all groups plus the interior (non-frontier unrevealed cells) must equal the remaining mine count.

The cell with the lowest mine probability is the safest guess. If that probability is 0, it is actually safe—the solver found a deduction that the simpler methods missed.

Level 4: The Tank Algorithm

The enumeration in Level 3 can be implemented efficiently with what is commonly called the "Tank algorithm" (named after a Minesweeper community member who popularized it). The key insight is that frontier cells can be processed sequentially, pruning invalid partial assignments early:

function tankSolve(frontier, constraints, minesRemaining) {
    var solutions = [];

    function backtrack(index, assignment, minesUsed) {
        // Base case: all frontier cells assigned
        if (index === frontier.length) {
            // Check global mine count feasibility
            var interiorCells = totalUnrevealed - frontier.length;
            var minesLeft = minesRemaining - minesUsed;
            if (minesLeft >= 0 && minesLeft <= interiorCells) {
                solutions.push(assignment.slice());
            }
            return;
        }

        var cell = frontier[index];

        // Try assigning safe (0) and mine (1)
        for (var value = 0; value <= 1; value++) {
            assignment[index] = value;
            var newMinesUsed = minesUsed + value;

            // Prune: too many mines
            if (newMinesUsed > minesRemaining) continue;

            // Check all constraints involving this cell
            if (isConsistent(cell, assignment, index, constraints)) {
                backtrack(index + 1, assignment, newMinesUsed);
            }
        }
    }

    backtrack(0, new Array(frontier.length), 0);
    return solutions;
}

The isConsistent function checks whether any constraint that is now fully assigned (all its cells have values) is satisfied, and whether any partially assigned constraint is still feasible (the remaining unassigned cells can potentially satisfy it).

The pruning makes this practical. Although the worst case is exponential, real Minesweeper boards have enough constraints to prune the search tree aggressively. On an expert board, frontier groups rarely exceed 20 cells, and the pruning typically reduces the effective branching factor well below 2.

Endgame Strategies

The endgame—the last few unrevealed cells—is where the global mine count becomes most valuable. When only a handful of cells remain, the constraint that the total mine count is fixed often resolves what would otherwise be ambiguous.

For example, if there are 3 unrevealed cells and 1 remaining mine, and the frontier analysis shows that cells A and B could each be a mine while cell C cannot, the probability for A and B is 50% each. But if the frontier analysis shows that A being a mine forces B to also be a mine (due to local constraints), then neither can be a mine (because only 1 mine remains), so all three cells are safe.

This interaction between local constraints and the global mine count is why the full Tank algorithm with global mine counting outperforms simpler probability estimation, especially in the endgame.

Performance Considerations

For a browser-based solver running alongside the GGAMES.MOBI Minesweeper game, performance matters. Players expect the solver to respond instantly. Here are the key optimizations:

With these optimizations, the solver handles expert boards (30x16, 99 mines) in under 50 milliseconds in modern browsers. That is fast enough to run after every move without any perceptible delay.

How Well Does It Play?

A Minesweeper AI solver using these techniques achieves the following approximate win rates on standard difficulty levels:

The remaining losses come from genuinely ambiguous positions where the solver must guess and guesses wrong. These are positions where no amount of deduction can determine the state of a cell—the information simply does not exist on the board. This is an inherent property of Minesweeper: some boards are not solvable without guessing.

The win rate on expert can be pushed to around 40% by optimizing the first-click strategy (clicking a corner, which tends to open more cells) and by being smarter about which guess to make when multiple cells have equal probability (preferring cells near the frontier over interior cells, as frontier cells provide more information when revealed).

Building a Minesweeper solver is a rewarding project that touches on constraint satisfaction, combinatorics, probability theory, and practical optimization—all within a problem domain that is immediately visual and easy to verify. If you want to try it yourself, start with the simple rules, get them working correctly, and then layer on complexity. Each level of sophistication is a meaningful improvement that you can observe directly in the solver's performance.