# No-Guess Minesweeper Boards: First-Click Rules and Solver Verification

> A solver can filter no-guess Minesweeper boards from the chosen start. Opening odds and completion rates help choose between retries and perturbation.

Source: https://sheng.page/en/posts/minesweeper-no-guess-board-generation/ · Published: 2026-10-24 · Author: Sheng

A safe first click can still leave the player guessing later, even when it opens a clear area. One straightforward way to generate a no-guess board is to have a solver play from the chosen starting square, using only deductions the revealed clues justify, and keep the board only if it opens every safe square. Simon Tatham's Mines also modifies boards that leave its solver stuck, then checks them again.

The random-board and excluded-click rules have closed-form opening probabilities that can be checked with Monte Carlo samples. Across a whole board, a single-point solver can try to finish using deductions from individual numbers. It completes almost no Expert boards, so a generator using it would reject most candidates.

## Three first-click rules

On a uniformly random board, mines can occupy any square, including the one clicked first. To make that click safe, a generator can wait for the player to choose a square, exclude it, then distribute mines uniformly over the remaining cells.

The [older Windows rule](https://minesweepergame.com/strategy/first-click.php) relocated a mine hit on the first move to the first empty square along the top row, scanning from the left. That slightly increases mine density towards the top left, giving a different distribution from excluding the click before placement. Relocation needs its own probability calculation. From Vista onwards, the first click is guaranteed to open a region.

An opening means revealing a zero and automatically expanding the area around it. For a central square with eight neighbours, all nine cells must be clear. A safe numbered square does not count.

## Odds that the first click opens a region

Take a board with N cells and M mines, and click in the centre. There are `C(N, M)` equally likely mine layouts on an unrestricted board. An opening requires every mine to fall outside the nine-cell block around the click, leaving `C(N - 9, M)` qualifying layouts. The probability is therefore `C(N - 9, M) / C(N, M)`.

Excluding the clicked cell reduces the total number of possible layouts to `C(N - 1, M)`. The number that leave all nine cells clear stays the same, giving `C(N - 9, M) / C(N - 1, M)`. Equivalently, this is the probability of eight clear neighbours conditional on a safe click. The count is a special case of the hypergeometric distribution.

`first_click.py` samples 200,000 boards for each combination of size and rule, with seed 42. `exact` is the formula result, `MC` the sampled proportion, `CI95` the approximate 95% confidence interval half-width calculated as `1.96 * sqrt(p * (1 - p) / T)`, and `delta` the difference `MC - exact`.

```python
# Probability that the first click (on the centre cell) opens a region, i.e. shows a zero.
# Two placement rules give two closed forms; both are checked against Monte Carlo (seed 42, 95% CI).
#   random board:            P(9 cells clear) = C(N-9, M) / C(N, M)
#   first click excluded,    P(8 neighbours clear | click cell safe) = C(N-9, M) / C(N-1, M)
#   mines uniform elsewhere:
# Windows' "move the mine to the top-left free cell" rule is a third distribution and is not modelled here.
import math, random

random.seed(42)
boards = {"Beginner 9x9, 10 mines": (9, 9, 10), "Intermediate 16x16, 40": (16, 16, 40), "Expert 30x16, 99": (30, 16, 99)}
T = 200_000
print(f"{'board':24s} {'rule':22s} {'exact':>7} {'MC':>7} {'CI95':>7} {'delta':>7}")
for name, (w, h, m) in boards.items():
    n = w * h
    cx, cy = w // 2, h // 2
    click = cx + cy * w
    nb = {(cx + dx) + (cy + dy) * w for dx in (-1, 0, 1) for dy in (-1, 0, 1)} - {click}
    for rule, exact in (("random board", math.comb(n - 9, m) / math.comb(n, m)), ("click excluded", math.comb(n - 9, m) / math.comb(n - 1, m))):
        hits = 0
        for _ in range(T):
            pool = range(n) if rule == "random board" else [i for i in range(n) if i != click]
            mines = set(random.sample(pool, m))
            hits += click not in mines and not (mines & nb)
        p = hits / T
        ci = 1.96 * math.sqrt(p * (1 - p) / T)
        print(f"{name:24s} {rule:22s} {exact:7.4f} {p:7.4f} {ci:7.4f} {p - exact:+7.4f}")
```

```text
board                    rule                     exact      MC    CI95   delta
Beginner 9x9, 10 mines   random board            0.2855  0.2852  0.0020 -0.0002
Beginner 9x9, 10 mines   click excluded          0.3257  0.3270  0.0021 +0.0013
Intermediate 16x16, 40   random board            0.2110  0.2089  0.0018 -0.0021
Intermediate 16x16, 40   click excluded          0.2501  0.2495  0.0019 -0.0006
Expert 30x16, 99         random board            0.1226  0.1226  0.0014 +0.0000
Expert 30x16, 99         click excluded          0.1545  0.1533  0.0016 -0.0012
```

On Expert, the central click opens a region about 12.3% of the time on a random board, or 15.4% when that cell is excluded from placement.

On the random Intermediate board, the delta is −0.0021 against an interval half-width of 0.0018, roughly 2.3 standard errors. A 95% interval can miss the exact value, so one miss across six comparisons is not surprising.

[Kostka's position-dependent opening probabilities](https://minesweepergame.com/strategy/first-click.php) range from 0.19 to 0.60 for Beginner, 0.21 to 0.60 for Intermediate, and 0.12 to 0.50 for Expert. At an edge or corner, fewer neighbouring cells have to be clear, making an opening more likely than at the centre.

## Choosing a first-click rule

After an opening, another part of the board can still leave two covered squares sharing one mine, with no further clue to distinguish them: a 50/50.

For a safe first click, exclude the clicked cell when placing mines. To guarantee an opening, exclude its neighbours as well.

## Tatham's solver plus perturber

[Tatham's generator](https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/mines-solver/) waits for the first click, since solvability depends on the starting square. Its solver reasons from the player's available clues. When deductions run out, a perturber usually moves mines among covered cells. Near the end, with no other covered cell available, it may have to move a mine into an opened area.

A modification can invalidate earlier deductions. Any run that needed a perturbation must therefore be followed by a fresh run from the same start, with the solving state cleared. The board is accepted only when the solver finishes without further changes. Tatham keeps modifying a board while successive runs need fewer perturbations, and generates a fresh board if the count increases.

The method is heuristic, with no guarantee that each generation attempt will succeed. Tatham's default mine densities exceed twice the Windows standards while still allowing his generator to find solvable boards.

A solver with sound rules certifies a no-guess solution even if those rules are simple. Stronger reasoning can admit more boards, though its deductions may be harder for a player to spot. Reproducing the same board also matters for debugging; see [the article on production RNG and reproducible tests](/en/posts/rng-unpredictable-in-prod-replayable-in-tests/) for seed management.

## How much a simple solver can finish

A single-point solver reasons about each revealed number on its own. This `single_point_solver.py` applies just two rules until neither can make progress:

- If the number minus the adjacent flag count equals the count of covered, unflagged neighbours, flag all those neighbours.
- If adjacent flags already account for the number, open every remaining covered, unflagged neighbour.

The test samples 2,000 boards at each difficulty with seed 42. Every board starts at the centre, with mines placed uniformly outside its 3×3 safe zone. Revealing a zero expands the clear region; success means opening every non-mine cell.

```python
# How often can a simple "single point" solver finish a board without guessing?
# Boards: Beginner/Intermediate/Expert, first click on the centre, mines placed uniformly
# outside the 3x3 block around the click (so the first click always opens a region).
# Solver rules, applied until nothing changes:
#   - a revealed number whose hidden neighbours all must be mines -> flag them
#   - a revealed number whose flagged neighbours already satisfy it -> open the rest
# This measures what THIS solver can finish, not whether a board is logically guess-free.
import random

random.seed(42)

def neighbours(i, w, h):
    x, y = i % w, i // w
    return [(x + dx) + (y + dy) * w for dx in (-1, 0, 1) for dy in (-1, 0, 1)
            if (dx or dy) and 0 <= x + dx < w and 0 <= y + dy < h]

def solve(w, h, m, click):
    n = w * h
    safe_zone = set(neighbours(click, w, h)) | {click}
    mines = set(random.sample([i for i in range(n) if i not in safe_zone], m))
    count = [sum(j in mines for j in neighbours(i, w, h)) for i in range(n)]
    opened, flagged = set(), set()
    def open_cell(i):  # flood fill through zeros
        stack = [i]
        while stack:
            c = stack.pop()
            if c in opened: continue
            opened.add(c)
            if count[c] == 0:
                stack.extend(j for j in neighbours(c, w, h) if j not in opened)
    open_cell(click)
    changed = True
    while changed:
        changed = False
        for i in list(opened):
            if count[i] == 0: continue
            hidden = [j for j in neighbours(i, w, h) if j not in opened and j not in flagged]
            flags = sum(j in flagged for j in neighbours(i, w, h))
            if hidden and flags + len(hidden) == count[i]:
                flagged.update(hidden); changed = True
            elif hidden and flags == count[i]:
                for j in hidden: open_cell(j)
                changed = True
    return len(opened) == n - m

T = 2000
for name, (w, h, m) in {"Beginner 9x9/10": (9, 9, 10), "Intermediate 16x16/40": (16, 16, 40), "Expert 30x16/99": (30, 16, 99)}.items():
    done = sum(solve(w, h, m, (w // 2) + (h // 2) * w) for _ in range(T))
    p = done / T
    print(f"{name:24s} single-point solver finishes without guessing: {p:.3f} +/- {1.96 * (p * (1 - p) / T) ** 0.5:.3f}  (n={T})")
```

```text
Beginner 9x9/10          single-point solver finishes without guessing: 0.637 +/- 0.021  (n=2000)
Intermediate 16x16/40    single-point solver finishes without guessing: 0.241 +/- 0.019  (n=2000)
Expert 30x16/99          single-point solver finishes without guessing: 0.001 +/- 0.001  (n=2000)
```

The solver finishes about 64% of Beginner boards and 24% of Intermediate boards. On Expert it manages roughly 0.1%. The printed `+/-` uses the same normal approximation, but Expert has too few successes for a reliable 95% interval: its unrounded lower bound is below zero. Use a Wilson interval for this estimate.

Suppose two groups of covered cells must contain the same number of mines, and one group is wholly contained within the other. The extra cells must be safe. A single-point solver cannot combine clues to make that deduction. It also ignores the global mine count and does not enumerate possible layouts, leaving some solvable boards unfinished. Its failure rate is therefore not the proportion of boards that need a guess.

Start a generator with random retries. Placement currently happens inside the solver, which returns only a success flag. Move placement outside it and pass in the candidate board, keeping that same board to return when verification succeeds. On failure, sample another candidate; stop with a generation failure when the attempt or waiting-time limit is reached. This verifier would reject almost every Expert candidate, so measure the cost of each verification attempt and the time a player waits for an accepted board. If that wait is too long, compare full generation times with stronger reasoning or a perturber such as Tatham's.

## What NP-completeness means for a solver

[Kaye's 2000 result](https://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm) in *The Mathematical Intelligencer*, volume 22, issue 2, pages 9 to 15, establishes that the Minesweeper Consistency Problem is NP-complete. The problem asks whether a partial board and its numbers admit any consistent mine layout. P vs NP is one of the Clay Mathematics Institute's million-dollar prize problems.

The problem allows generalised inputs of arbitrary size and shape. A solver can enumerate every possible layout, at the cost of poor worst-case running time. In an unresolved 50/50, the remaining layouts disagree about which of the two squares is safe, so those clues alone cannot justify opening either one.

## Notes

- Match the opening formula to the placement rule: `C(N - 9, M) / C(N, M)` for a random board, or `C(N - 9, M) / C(N - 1, M)` with the clicked cell excluded. On Expert these give about 12.3% and 15.4%. Fixed-location relocation needs a separate distribution.
- After perturbing a board, verify it afresh from the player's chosen start before accepting it.
- The single-point solver finishes roughly 64% of Beginner boards, 24% of Intermediate boards and 0.1% of Expert boards. For Expert, measure the wait for an accepted board before choosing stronger reasoning or perturbation.
- To decide whether a position requires a guess, check whether its clues determine a safe move. Kaye's NP-completeness result concerns consistency on generalised inputs.

## Further reading

- Simon Tatham, [Writing a soluble-grid generator for Mines](https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/mines-solver/): a detailed account of generation and verification.
- [Minesweeper first click](https://minesweepergame.com/strategy/first-click.php): a short strategy page covering the Windows placement rules and Kostka's opening-probability ranges.
- Richard Kaye, [Minesweeper and NP-completeness](https://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm): Kaye's explanation of Minesweeper and NP-completeness, with a reference to the original paper.

> Ideas and technical judgement by Sheng; drafted with Claude · examples run on a Mac with Python 3.15.0.