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
2 reactions
tTA Spectral Approach to #P -Hardness via Clause Expander Graphs?
I believe to have proven it what I set out for, though it's now technically a Laplacian-energy approach via clause expander graphs. No notation changes. I initially proposed the problem on the P vs NP board and now believe to have found a solution. The problem it is addressing: \\textbf{Input.}
A finite weighted graph \\(E=(V,\\mathcal{E},w)\\)
whose edge weights \\(w:\\mathcal{E}\\to\\{1,\\dots,108\\}\\) are written in unary,
together with a vertex–type map
\\(\\ell:V\\to\\Sigma=\\{\\mathrm{VAR},\\mathrm{GAD},\\mathrm{ANC}\\}\\).
\\textbf{Task.}
Let \\(k:=\\bigl|\\{v\\in V:\\ell(v)=\\mathrm{VAR}\\}\\bigr|\\).
Compute
\\\
\\Lambda\\text{-}\\mathrm{Sum}(E)\\;:=\\;
\\sum\_{x\\in\\{0,1\\}\^{n}}
\\widehat{\\Lambda}\_{E}(x),
\\\]
where \\(\\widehat{\\Lambda}\_{E}(x)\\) is the global‑clip functional
defined in Eq. 7.1.
Results:
In our first approach, we attempted to create a 'one-shot' gadget where each unsatisfying assignment contributes exactly 4. We prove this impossible (Theorem 6.1), leading us to an additive scheme where contributions scale with violated clauses. Post-processing recovers the counting property. We define a Laplacian-energy sum, then show that approximating this spectral sum even within an additive error of ±1 is #P -hard.he key details begin in Section 6 and culminate with the main result in 8.2, hough it might help to skim what comes before to get a sense of the approach. The novelty is in connecting spectral graph properties directly to counting complexity through a new gadget construction.
I'd appreciate any feedback! 😁
Here's a link to the paper: [https://doi.org/10.5281/zenodo.15668482 https://doi.org/10.5281/zenodo.15668482
The most updated version of the paper will now better reflect what became of each appraoch.
#technology
I believe to have proven it what I set out for, though it's now technically a Laplacian-energy approach via clause expander graphs. No notation changes. I initially proposed the problem on the P vs NP board and now believe to have found a solution. The problem it is addressing: \\textbf{Input.}
A finite weighted graph \\(E=(V,\\mathcal{E},w)\\)
whose edge weights \\(w:\\mathcal{E}\\to\\{1,\\dots,108\\}\\) are written in unary,
together with a vertex–type map
\\(\\ell:V\\to\\Sigma=\\{\\mathrm{VAR},\\mathrm{GAD},\\mathrm{ANC}\\}\\).
\\textbf{Task.}
Let \\(k:=\\bigl|\\{v\\in V:\\ell(v)=\\mathrm{VAR}\\}\\bigr|\\).
Compute
\\\
\\Lambda\\text{-}\\mathrm{Sum}(E)\\;:=\\;
\\sum\_{x\\in\\{0,1\\}\^{n}}
\\widehat{\\Lambda}\_{E}(x),
\\\]
where \\(\\widehat{\\Lambda}\_{E}(x)\\) is the global‑clip functional
defined in Eq. 7.1.
Results:
In our first approach, we attempted to create a 'one-shot' gadget where each unsatisfying assignment contributes exactly 4. We prove this impossible (Theorem 6.1), leading us to an additive scheme where contributions scale with violated clauses. Post-processing recovers the counting property. We define a Laplacian-energy sum, then show that approximating this spectral sum even within an additive error of ±1 is #P -hard.he key details begin in Section 6 and culminate with the main result in 8.2, hough it might help to skim what comes before to get a sense of the approach. The novelty is in connecting spectral graph properties directly to counting complexity through a new gadget construction.
I'd appreciate any feedback! 😁
Here's a link to the paper: [https://doi.org/10.5281/zenodo.15668482 https://doi.org/10.5281/zenodo.15668482
The most updated version of the paper will now better reflect what became of each appraoch.
#technology
2
5 reactions
tTlA Spectral Approach to #P -Hardness via Clause Expander Graphs?
It's just as the title says. I initially proposed the problem on the P vs NP board and now believe to have found a solution. The problem it is addressing: \\textbf{Input.}
A finite weighted graph \\(E=(V,\\mathcal{E},w)\\)
whose edge weights \\(w:\\mathcal{E}\\to\\{1,\\dots,108\\}\\) are written in unary,
together with a vertex–type map
\\(\\ell:V\\to\\Sigma=\\{\\mathrm{VAR},\\mathrm{GAD},\\mathrm{ANC}\\}\\).
\\textbf{Task.}
Let \\(k:=\\bigl|\\{v\\in V:\\ell(v)=\\mathrm{VAR}\\}\\bigr|\\).
Compute
\\\
\\Lambda\\text{-}\\mathrm{Sum}(E)\\;:=\\;
\\sum\_{x\\in\\{0,1\\}\^{n}}
\\widehat{\\Lambda}\_{E}(x),
\\\]
where \\(\\widehat{\\Lambda}\_{E}(x)\\) is the global‑clip functional
defined in Eq. 7.1.
Results:
In our first approach, we attempted to create a 'one-shot' gadget where each unsatisfying assignment contributes exactly 4. We prove this impossible (Theorem 6.1), eading us to an additive scheme where contributions scale with violated clauses. Post-processing recovers the counting property. We define a spectral sum, then show that approximating this spectral sum even within an additive error of ±1 is #P -hard.he key details begin in Section 6 and culminate with the main result in 8.2, hough it might help to skim what comes before to get a sense of the approach. The novelty is in connecting spectral graph properties directly to counting complexity through a new gadget construction.
I'd appreciate any feedback! 😁
Here's a link to the paper: [https://doi.org/10.5281/zenodo.15668482 https://doi.org/10.5281/zenodo.15668482
#technology
It's just as the title says. I initially proposed the problem on the P vs NP board and now believe to have found a solution. The problem it is addressing: \\textbf{Input.}
A finite weighted graph \\(E=(V,\\mathcal{E},w)\\)
whose edge weights \\(w:\\mathcal{E}\\to\\{1,\\dots,108\\}\\) are written in unary,
together with a vertex–type map
\\(\\ell:V\\to\\Sigma=\\{\\mathrm{VAR},\\mathrm{GAD},\\mathrm{ANC}\\}\\).
\\textbf{Task.}
Let \\(k:=\\bigl|\\{v\\in V:\\ell(v)=\\mathrm{VAR}\\}\\bigr|\\).
Compute
\\\
\\Lambda\\text{-}\\mathrm{Sum}(E)\\;:=\\;
\\sum\_{x\\in\\{0,1\\}\^{n}}
\\widehat{\\Lambda}\_{E}(x),
\\\]
where \\(\\widehat{\\Lambda}\_{E}(x)\\) is the global‑clip functional
defined in Eq. 7.1.
Results:
In our first approach, we attempted to create a 'one-shot' gadget where each unsatisfying assignment contributes exactly 4. We prove this impossible (Theorem 6.1), eading us to an additive scheme where contributions scale with violated clauses. Post-processing recovers the counting property. We define a spectral sum, then show that approximating this spectral sum even within an additive error of ±1 is #P -hard.he key details begin in Section 6 and culminate with the main result in 8.2, hough it might help to skim what comes before to get a sense of the approach. The novelty is in connecting spectral graph properties directly to counting complexity through a new gadget construction.
I'd appreciate any feedback! 😁
Here's a link to the paper: [https://doi.org/10.5281/zenodo.15668482 https://doi.org/10.5281/zenodo.15668482
#technology
5