How much of Minesweeper is pure deduction vs forced…
0 reactions
How much of Minesweeper is pure deduction vs forced guessing? Measured with a constraint solver over ~32k boards
Minesweeper's consistency problem is NP-complete (Kaye, 2000), but a more practical question is measurable: for a randomly generated board, how often is the game fully determined by logic, versus how often does it reach a state where no cell can be *proven* safe and you're forced into a probabilistic guess?
I implemented a solver to measure it, in two phases:
- **Deduction:** treat each revealed number as a constraint on its hidden neighbours and propagate every forced conclusion (a cell is provably safe/mine iff all consistent configurations agree).
- **Probability:** when propagation stalls, enumerate the mine configurations consistent with the frontier (the counting step — #P -flavoured in general) to get each hidden cell's exact mine probability, then take the minimum.
Run over tens of thousands of first-click-safe boards:
| Difficulty | Mine density | No-guess solvable | Solver win rate |
|---|---|---|---|
| Beginner (9x9, 10) | 12.3% | 80.6% | 96.1% |
| Intermediate (16x16, 40) | 15.6% | 53.2% | 85.0% |
| Expert (30x16, 99) | 20.6% | 3.9% | 34.9% |
So ~96% of Expert boards force at least one guess, and even playing the minimum-probability cell every time caps Expert wins near 35% — a few independent forced guesses is enough to lose on probability alone.
Two things I found worth discussing:
- The cliff from 80.6% (Beginner) to 3.9% (Expert) comes from fairly small density changes — a phase-transition-like sensitivity around constraint density.
- "No-guess" board generation is essentially rejection sampling on solvability, which raises a real cost question at scale.
Full method, seeds and charts: https://lkforge.com/blog/minesweeper-how-often-you-must-guess/ (my own implementation/write-up). Curious how others would formalise the "forced-guess" threshold.
#technology
source
Minesweeper's consistency problem is NP-complete (Kaye, 2000), but a more practical question is measurable: for a randomly generated board, how often is the game fully determined by logic, versus how often does it reach a state where no cell can be *proven* safe and you're forced into a probabilistic guess?
I implemented a solver to measure it, in two phases:
- **Deduction:** treat each revealed number as a constraint on its hidden neighbours and propagate every forced conclusion (a cell is provably safe/mine iff all consistent configurations agree).
- **Probability:** when propagation stalls, enumerate the mine configurations consistent with the frontier (the counting step — #P -flavoured in general) to get each hidden cell's exact mine probability, then take the minimum.
Run over tens of thousands of first-click-safe boards:
| Difficulty | Mine density | No-guess solvable | Solver win rate |
|---|---|---|---|
| Beginner (9x9, 10) | 12.3% | 80.6% | 96.1% |
| Intermediate (16x16, 40) | 15.6% | 53.2% | 85.0% |
| Expert (30x16, 99) | 20.6% | 3.9% | 34.9% |
So ~96% of Expert boards force at least one guess, and even playing the minimum-probability cell every time caps Expert wins near 35% — a few independent forced guesses is enough to lose on probability alone.
Two things I found worth discussing:
- The cliff from 80.6% (Beginner) to 3.9% (Expert) comes from fairly small density changes — a phase-transition-like sensitivity around constraint density.
- "No-guess" board generation is essentially rejection sampling on solvability, which raises a real cost question at scale.
Full method, seeds and charts: https://lkforge.com/blog/minesweeper-how-often-you-must-guess/ (my own implementation/write-up). Curious how others would formalise the "forced-guess" threshold.
#technology
source
| 4,000 mlx | |
| 4 | |
| 0 |