Two covered squares sit side by side at the edge of a nearly finished Expert board. Each touches the same 1, the mine counter reads one, and every other number within reach has already been satisfied. Putting the mine under the left square explains all of them. So does putting it under the right square. Nothing else on the grid is close enough to break the tie, and there is no third click that would produce new information before one of the two is taken.
Half the time the guess is wrong, and the run ends with a board that was, by every measure a player cares about, finished. That is not a failure of the solver in the player's head. It is a property of the position, and it is the reason no program clears Expert Minesweeper every time. Any claim of a 100% Expert win rate is either a board generator that screens out these positions, or a lie.
The formal treatment of the general problem arrived in 2000. Richard Kaye's paper in The Mathematical Intelligencer proved that the Minesweeper Consistency Problem is NP-complete, by encoding Boolean circuits as grids of numbers and mines. The result is quoted often enough that it passes for an explanation of the position above. It is not one, and working out why is most of the work in building an honest board.
What the NP-completeness result does and does not tell a player
Membership in NP is the easy half. Hand the algorithm a candidate arrangement of mines and checking it is a walk over every cell and its neighbours, linear in the size of the board. The certificate is the mine layout itself.
NP-hardness is the half that took a paper. Kaye builds wires, NOT gates, AND gates and wire crossings out of minesweeper patterns, so that any Boolean circuit can be laid out as a board which is consistent exactly when the circuit is satisfiable. Solving consistency for arbitrary boards in polynomial time would therefore solve satisfiability, and P would equal NP. Kaye put the conclusion in the paper's own words: Minesweeper is "essentially equivalent in complexity to any of a wide range of known natural and important problems".
None of that says an Expert board needs a guess. NP-completeness is a worst-case claim about one decision problem — whether a position has any consistent mine layout at all. The boards that carry the hardness are constructions built to encode circuits, and they are far larger and stranger than 480 cells of random mines. An average Expert board is decided by a handful of local patterns, and the guess it still needs comes from density and coincidence rather than circuit encoding. The same style of result puts Sokoban a class higher, at PSPACE-complete.
Expert is the densest of the three standard boards
Mine density is the number that moves with difficulty, and each figure below is the mine count divided by the cell count.
| Level | Board | Cells | Mines | Density |
|---|---|---|---|---|
| Beginner | 9×9 | 81 | 10 | 12.3% |
| Intermediate | 16×16 | 256 | 40 | 15.6% |
| Expert | 30×16 | 480 | 99 | 20.6% |
The step from Beginner to Expert raises the density by about two thirds, and that is enough to change the character of the game. Ten mines across 81 cells leave most of the board as connected runs of zeroes, and one click cascades a third of the grid open. Ninety-nine across 480 closes those runs up. A deduction that resolves a whole region at Beginner becomes a single-cell deduction at Expert, and those are the ones that arrive in pairs and cancel each other out.
The constraint network also has a phase transition, reported above roughly 25% density, where deductions stop arriving and the remaining cells can only be attacked by estimating probabilities. Expert at 20.6% sits just under that line, which is the uncomfortable part: dense enough to force guesses often, not dense enough to be hopeless.
How many coin flips it takes to lose a run
The arithmetic of repeated independent guesses is unforgiving and worth writing down, because the numbers move faster than most players expect.
| Coin flips in the run | Chance of surviving all of them | Runs won per 100 |
|---|---|---|
| 0 | 1 | 100 |
| 1 | 0.5 | 50 |
| 2 | 0.25 | 25 |
| 3 | 0.125 | 12.5 |
| 5 | 0.031 | 3.1 |
Those rows are just 0.5 raised to the flip count, so they are arithmetic rather than measurement. They are still the clearest way to read an Expert win rate. A solver that wins one board in four is, if every loss is a coin flip, surviving two independent flips per game on average. Getting better at deduction does not push the ceiling to 100%; it removes flips from the board, and each one removed is worth a doubling and no more.
Teaching the solver one more pattern that turns a two-cell ambiguity into a deduction is worth more than any amount of speed, because it moves the ceiling rather than the clock.
3BV counts clicks, not guesses
The community's difficulty metric is 3BV — Bechtel's Board Benchmark Value — and it measures work rather than luck. Take the finished board before anyone has clicked. Every opening, meaning a connected run of zero-mine cells that a single click cascades through, counts as 1 no matter how many cells it covers. Every numbered cell that touches no opening also counts as 1, because it has to be clicked by hand. Add the two counts and that is the minimum number of left-clicks needed to clear the board.
Expert boards run from roughly 60 to roughly 280, with a typical board near 150. Under about 100 is a notably easy board and over 200 a notably hard one. Time rankings refuse a record set on a board below 100 at Expert, 30 at Intermediate or 2 at Beginner.
The number is useful and it is not the same axis as the guess count. A 3BV of 150 says the board needs 150 clicks of work; it says nothing about how many of those were forced. Two boards with the same 3BV can hide very different numbers of coin flips, and the flips decide win rates.
Three ways to make the coin flip fair
Guarantee the first click. Every clone worth playing makes the opening click safe, and most open a zero region with it. A run that ends before the player has made a decision is not a loss, it is a bad deal, and it is entirely within the generator's control.
Keep the mine counter honest. A meaningful share of positions that look like 50/50 do not survive the counter. If the numbers already placed account for all but one of the mines, the counter plus the remaining constraints often names the cell. A clone that counts flags rather than confirmed mines turns a solvable position into a coin flip and blames the player for it.
Offer a no-guess mode, checked by a solver. Generate the board, run a constraint solver over it, and discard the board if the solve cannot finish without a guess. That is the same job as checking a Sudoku has exactly one answer, and it turns the promise from a marketing line into a guarantee, at the cost of throwing away a fair share of boards.
Seeding the generator is the cheap fourth option, and it belongs in a test suite rather than a feature list. A board built from a recorded seed can be replayed cell for cell, which is the only way to check a reported 50/50 was genuinely unbreakable rather than a bug in the flood fill. This site's Minesweeper keeps a solver in the generator for that reason: a board that cannot be reasoned to the end is a bug report about the clone, not about the player.
Pros
- A constraint solver in the generator turns a no-guess mode from a promise into something the code can prove on every board.
- 3BV gives one number per board, so a record time can be read against the work the board actually required.
- Tracking confirmed mines separately from flags catches the clone bug that quietly converts deductions into coin flips.
- A recorded seed makes a claimed 50/50 reproducible, which is the difference between a bug report and an anecdote.
Cons
- Solver-checked boards cost generation time, and the discards get frequent enough at Expert density to show up in the frame where a new board appears.
- Removing every forced guess removes the tension with it, because a board that always has an answer always has a next click that is simply correct.
- 3BV rewards cascades, so a generator tuned to show a low number produces wide-open boards with fewer decisions in them.
- The no-guess guarantee stops at the strength of the bundled solver, so boards a better solver could finish are thrown away without explanation.
Sources
- Minesweeper (video game) — the standard board configurations, Kaye's 2000 NP-completeness proof and its reduction, and the phase transition reported past roughly 25% mine density.
- Minesweeper ranking rules — the minimum 3BV a board must have for a time to count, at 2 for Beginner, 30 for Intermediate and 100 for Expert.
- Minesweeper.now: can you win every time — the two-cells-one-mine position, the 20.6% Expert density, and why even a flawless run gets lost to a guess.
- Minesweeper 3BV explained — how 3BV is counted from openings and isolated numbered cells, and the 60 to 280 range with a typical Expert board near 150.