Minesweeper Algorithms and Solver Design
A complete implementation has two different jobs: generate and render a playable board, then reason about partial information without reading the hidden mine map. Keeping those jobs separate prevents a solver from accidentally cheating.
Board generation
Store a mine bit for each cell, then calculate each safe cell's adjacent count. For first-click safety, delay placement until the opening coordinate is known and exclude that cell, or a small zone around it, from the shuffled candidate list.
- Use a seeded pseudorandom generator for reproducible boards.
- Apply Fisher-Yates to unbiased candidate placement.
- Store the seed and first-click rule with any replay.
Reveal and chording
A reveal on a zero cell performs a bounded flood fill through connected zeroes and their numbered boundary. Chording reveals the remaining covered neighbors of a clue only when its adjacent flag count equals the clue.
- Use an explicit stack or queue instead of deep recursion.
- Never reveal a flagged cell during flood fill.
- Record reveal, flag and chord as distinct replay actions.
Constraint solver
Each visible clue becomes an equation over adjacent covered cells. Subtract known flags, split the frontier into connected components, enumerate consistent assignments, and intersect the surviving solutions. A cell present as a mine in every solution is forced; a cell absent from every solution is safe.
- Component splitting limits exponential growth.
- Global remaining-mine constraints can couple otherwise separate components.
- Probability overlays require an explicit weighting model and honest labels.
Complexity and practical engineering
Richard Kaye proved the Minesweeper consistency problem NP-complete. That does not mean every ordinary board is slow to solve. Local propagation, subset deductions, component decomposition and bounded enumeration handle many practical frontiers efficiently.
- Cap component enumeration and report uncertainty instead of freezing.
- Test solver output against every visible clue.
- For no-guess generation, simulate a solver from the intended opening and reject boards it cannot finish.
Choose a clear board representation
A flat array indexed by y times width plus x is compact and works well for a rectangular grid. Store immutable mine placement separately from mutable player state such as covered, revealed and flagged. Precompute or generate neighbor indices through one shared function so clue calculation, flood fill, chording and the solver agree about boundaries.
- Validate width, height and mine count before generation.
- Keep the hidden mine map out of solver-facing state.
- Represent elapsed time and game state independently from rendering.
- Use stable coordinate labels for accessibility and replays.
Turn clues into equations
For a revealed clue c, collect its covered unflagged neighbors as variables and subtract adjacent confirmed flags from c. The resulting equation says how many of those variables must be mines. A zero remainder makes every variable safe; a remainder equal to the variable count makes every variable a mine. Subset reduction handles cases where one variable set is contained in another by subtracting both the sets and required totals.
- Reject a state when a remainder is negative or exceeds its unknown count.
- Repeat direct and subset propagation until no new facts appear.
- Do not treat a user flag as ground truth unless the solving mode explicitly assumes flags are correct.
Enumerate only the unresolved frontier
After deterministic propagation, build a graph connecting variables that appear in the same constraint. Each connected component can usually be enumerated independently. During backtracking, stop a branch as soon as any clue has too many assigned mines or too few remaining cells to reach its total. Intersect all surviving assignments to find forced cells.
- Use component size limits and cancellation checks.
- Memoize repeated constraint states when profiling shows a benefit.
- Combine components with the global remaining-mine count only when the visible position contains enough board context.
- Report zero surviving assignments as a contradiction, not as a random recommendation.
Probability needs a stated model
A cell's mine probability can be estimated from the fraction of surviving assignments that contain a mine, but assignments may need weighting when unconstrained cells and a global mine count are involved. A local frontier percentage is not automatically the probability for the complete hidden board. The interface should distinguish proven safe, proven mine and uncertain probability rather than presenting every percentage as equivalent evidence.
- Forced safe means zero mines across every valid assignment.
- Forced mine means a mine across every valid assignment.
- Uncertain cells require risk comparison or more information.
- If enumeration is truncated, label the result approximate or omit it.
Generate and verify no-guess boards
Generate a candidate after the intended first click, expose the starting cascade, and give the solver only the information a player would see. Apply the allowed deduction set until the board is complete or progress stops. Accept only a completed candidate. Store the seed, opening coordinate, generator version and rule set so the result can be reproduced later.
- Bound the number of candidate attempts.
- Do not let the verifier read the hidden map when selecting a move.
- Define whether global mine counting and advanced enumeration are allowed.
- Changing the solver changes the meaning of a no-guess guarantee.
Testing a Minesweeper engine
Use small deterministic boards for unit tests and randomized property tests for invariants. Every clue must equal the number of adjacent mines. Flood fill must reveal connected zeroes and their numbered boundary without opening a mine or flag. A solver recommendation must satisfy every visible clue across all assignments it claims to represent.
- Test corners, edges, one-row boards and maximum mine counts.
- Round-trip seeds and exact layouts.
- Verify keyboard, pointer and touch actions reach the same state transitions.
- Keep replay tests when generation or timing code changes.
Frequently asked questions
Why not let the solver read the hidden mine map?
That would test the game engine rather than logical inference. A fair solver must operate only on clues, covered cells, flags and any explicitly supplied remaining-mine count.
Does NP-complete mean every Minesweeper board is hard?
No. The complexity result describes worst-case decision problems. Many practical boards collapse through direct rules, subset deductions and small independent components.
How do I make the first click safe?
Delay placement until the opening is known, remove the protected cell or zone from the candidates, then perform an unbiased seeded shuffle before choosing mine positions.
What makes a probability exact?
It is exact only relative to a complete and correctly weighted model of the visible constraints, global mine count and unconstrained cells. A cropped screenshot often supports only local frontier probabilities.
Continue exploring
Sources and further reading
External facts and claims on this page are grounded in the references below. Time-sensitive record information should always be checked at the linked authority.