Minesweeper

Minesweeper is a game of inference. Some squares of a grid hide mines; the rest, once uncovered, show a number counting the mines in the eight squares around them, and from those numbers the player reasons out where the remaining mines must be. The reasoning is the game, and it is precisely the kind a constraint solver does well: each revealed number is a linear equation in unknown zero-one variables, one per covered square, and a position is solvable exactly when those equations pin the mines down. More than that, integer programming can answer the question a careful player actually asks, not “where are all the mines” but “is this square safe to click,” by testing whether any consistent arrangement could put a mine there. The mine-finding model is Chlond’s, from the INFORMS Transactions on Education puzzle column; the click-safety test is a short extension of it.

The position

The board in Figure 22.1 is five squares by five. Eleven squares have been uncovered and show numbers; the other fourteen stay covered. A number is the count of mines among a square’s neighbours, the up to eight squares touching it including the diagonals. The numbers alone fix where the mines are, with no guessing and no count of the total given; the task is to find them.

The model

Variables

For every square $(r, c)$ let $x_{rc} \in \{0, 1\}$ be $1$ when a mine lies there. The covered squares are the genuine unknowns; an uncovered, numbered square is known to hold no mine.

Constraints

Each numbered square is mine-free and constrains its neighbourhood: if square $(r, c)$ shows the number $n_{rc}$, then $$x_{rc} = 0, \qquad \sum_{(r', c') \in \mathcal{N}(r, c)} x_{r'c'} = n_{rc},$$ where $\mathcal{N}(r, c)$ is the set of neighbouring squares. That is the whole model. A feasible point is a mine layout consistent with every number on the board, and in a well-made puzzle, like the ones Chlond takes from Steinruecken, the numbers admit exactly one.

The solver

The model goes to CP-SAT directly. A second routine answers the click-safety question by pushing one square’s variable as low and as high as the constraints allow: if it cannot be made $1$, the square is certainly safe; if it cannot be made $0$, it certainly hides a mine; otherwise the evidence is not yet decisive.

from ortools.sat.python import cp_model

def neighbours(r, c, R, C):
    return [(r + dr, c + dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1)
            if (dr or dc) and 0 <= r + dr < R and 0 <= c + dc < C]

def model(clues, R, C):
    m = cp_model.CpModel()
    x = {(r, c): m.NewBoolVar(f"{r},{c}")
         for r in range(R) for c in range(C)}
    for (r, c), n in clues.items():
        m.Add(x[r, c] == 0)
        m.Add(sum(x[p] for p in neighbours(r, c, R, C)) == n)
    return m, x

def minesweeper(clues, R, C):
    m, x = model(clues, R, C)
    s = cp_model.CpSolver()
    s.Solve(m)
    return frozenset(p for p in x if s.Value(x[p]))

def status(clues, R, C, cell):
    m1, x1 = model(clues, R, C)
    m1.Maximize(x1[cell])                  # can a mine sit here at all?
    s1 = cp_model.CpSolver(); s1.Solve(m1)
    can_be_mine = s1.Value(x1[cell])
    m2, x2 = model(clues, R, C)
    m2.Minimize(x2[cell])                  # must a mine sit here?
    s2 = cp_model.CpSolver(); s2.Solve(m2)
    must_be_mine = s2.Value(x2[cell])
    return ("mine" if must_be_mine
            else "safe" if can_be_mine == 0 else "unknown")

For this position the solver returns a single layout, the five mines marked in Figure 22.1, so every covered square is decided: status reports “mine” for each of the five and “safe” for each of the other nine covered squares. The position is fully solvable by logic alone, with no guessing.

When logic runs out

The status test is the part worth keeping, because real Minesweeper positions are often not fully determined. When two layouts are both consistent, some squares carry a mine in one and not the other, and no amount of reasoning can settle them; the player must guess. The integer program draws that line exactly: a square is safe to click precisely when its variable cannot be raised to $1$ within the constraints. That the underlying decision, whether any consistent layout exists at all, is NP-complete, proved by Richard Kaye in $2000$, is the reason no simple rule replaces the search, and the reason a solver earns its place at the board.

Sources. The integer-programming treatment follows Martin J. Chlond, Puzzle—Minesweeper Puzzles, INFORMS Transactions on Education volume $11$, number $2$ ($2011$), pages $90$–$91$; the uniquely-solvable positions it models are Christian Steinruecken’s. Minesweeper reached a wide audience bundled with Microsoft Windows in the early $1990$s; the proof that deciding consistency of a Minesweeper position is NP-complete is Richard Kaye, Minesweeper is NP-complete, The Mathematical Intelligencer volume $22$ ($2000$), pages $9$–$15$. The position solved here is a re-authored instance with a unique solution.