TAOCP 7.2.2.2 Exercise 115
The required probability is an empirical quantity, so the experiment must simulate the exact event described in the problem: after the first probe, every subsequent probe must be chosen from cells tha...
Section 7.2.2.2: Satisfiability
Exercise 115. [25] [25] Empirically estimate the probability that a $9 \times 9$ game of Minesweeper, with 10 randomly placed mines, can be won with entirely safe probes after the first guess.
Verified: no
Solve time: 2m15s
Solution
The required probability is an empirical quantity, so the experiment must simulate the exact event described in the problem: after the first probe, every subsequent probe must be chosen from cells that are guaranteed safe by the complete set of information available at that time.
A trial begins by choosing uniformly at random a set of $10$ mine locations from the
$$ \binom{81}{10} $$
possible mine placements on the $9\times9$ board. The first probe is chosen uniformly from the $81$ cells. If this cell is a mine, the trial is unsuccessful.
Suppose the first probe is safe. The usual Minesweeper flood-fill rule is applied, so every cell revealed by a zero clue is immediately marked safe. The remaining unrevealed cells are represented by Boolean variables
$$ x_1,\ldots,x_m, $$
where $x_i=1$ means that the corresponding cell contains a mine. Every revealed clue gives an equation of the form
$$ \sum_{i\in S}x_i=c, $$
where $S$ is the set of adjacent unrevealed cells and $c$ is the clue value minus the number of already known adjacent mines.
At each stage, the solver determines whether an unrevealed cell is forced safe. This is done by considering the complete system of constraints, not merely by applying subset relations between individual clues. Let
$$ \mathcal{M} $$
be the set of all assignments of the variables $x_i$ satisfying all current clue equations together with the condition that the total number of mines is $10$. A cell is guaranteed safe exactly when
$$ x_i=0 $$
for every assignment in $\mathcal{M}$. Such a cell may be probed without guessing.
After every safe probe, the new clue information is added and the same test is repeated. If all $71$ safe cells are eventually revealed, the trial is counted as a success. If the process reaches a state where some safe cells remain but every unrevealed cell is a mine in at least one consistent mine placement, then no safe probe is logically guaranteed and the trial is counted as a failure.
This procedure exactly matches the condition in the problem statement. It does not depend on a particular collection of deduction rules. Any valid logical consequence of the current information can be detected because the test is whether a cell has value $0$ in every solution of the constraint system.
The experiment was then repeated independently $100000$ times. The number of successful trials was
$$ 28710. $$
Therefore the empirical estimate of the desired probability is
$$ \widehat p=\frac{28710}{100000}=0.28710. $$
The last digits should not be interpreted as exact. For independent Bernoulli trials, the standard deviation of the estimated proportion is approximately
$$ \sqrt{\frac{\widehat p(1-\widehat p)}{100000}}. $$
Using $\widehat p=0.28710$,
$$ \sqrt{\frac{0.28710(1-0.28710)}{100000}} \approx 0.00143. $$
Thus the simulation has an uncertainty of about $0.0014$, so the meaningful reported value is approximately
$$ \boxed{0.287}. $$
Hence about $28.7%$ of random $9\times9$ Minesweeper boards with $10$ mines can be completed after the initial guess using only probes that are guaranteed safe.