Phase transition for Minesweeper

Baptiste Louf

REVIEW 3 major objections 5 minor 10 references

Phase transition for Minesweeper

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Random Minesweeper has a coarse phase transition at mine probability $\Theta(n^{-1/6})$: below it a linear-time algorithm wins with high probability, above it no algorithm wins.

desk verdict First rigorous coarse phase transition for Minesweeper solvability, with a credible strategy but a load-bearing unproved lemma (Lemma 4) that must be fixed before the main theorem is established. read the letter →

arxiv 2506.01634 v1 pith:R737525D submitted 2025-06-02 math.PR math-phmath.COmath.MP

Baptiste Louf This is my paper

classification math.PRmath-phmath.COmath.MP MSC 60C0505C8068Q25

keywords phasetransitionMinesweeperrandomdiscretestructuresambiguouspatternslineartimealgorithmsolvabilitymineprocesscoarsethreshold

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that a random Minesweeper board, where each of $n$ cells is a mine independently with probability $p$, changes from solvable to unsolvable at the threshold $p=\Theta(n^{-1/6})$. Below the threshold, a simple linear-time strategy solves the board with high probability; above it, every algorithm has success probability $o(1)$. The transition is neither sharp nor monotone, but it is driven by the emergence of the two smallest ambiguous patterns, each of which forces a genuine $50/50$ guess. At the critical scale $p\sim c n^{-1/6}$, the best success probability is bounded between $\varepsilon$ and $1-\varepsilon$ for every fixed $c$.

What carries the argument

The load-bearing objects are the two smallest ambiguous patterns $P_1$ and $P_2$: six-mine configurations whose revealed grid state $S_{\min}$ contains a hidden cell that is a mine in one pattern and empty in the other, so the best possible play is an unbiased guess. Proposition 3 proves, via an envelope analysis of ambiguous grid states, that these are the only ambiguous patterns with six or fewer mines. Lemma 4 then converts many disjoint occurrences of $P_1$ or $P_2$ into an upper bound of $2^{-k}+o(1)$ on any algorithm's success probability, and Lemma 14 shows that above the threshold the board contains $\Theta(n p^6)$ such occurrences with high probability. Below the threshold, Lemma 13 ensures every island of revealed nonzero cells is small enough that the smallest-pattern classification applies, yielding the linear-time solving algorithm.

What would settle it

Simulate $M_{n,p}$ at $p=c n^{-1/6}$ for several fixed values of $c$ and large $n$: count occurrences of $P_1$ and $P_2$ and measure the success probability of the best known inference strategy. If the success probability does not approach $\exp(-2c^6)$ below the pattern threshold and $1-(1-\exp(-2c^6))/2$ above it, the Poisson approximation or the independence assumption in Lemma 4 would be contradicted.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: for the random mine assignment $M_{n,p}$, if $p=o(n^{-1/6})$ there exists a linear-time algorithm that solves $M_{n,p}$ with high probability; if $p \gg n^{-1/6}$, then $\max_A \mathbb{P}(A \text{ solves } M_{n,p}) = o(1)$; and if $p\sim c n^{-1/6}$, the maximal success probability lies between $\varepsilon$ and $1-\varepsilon$. The proof identifies the two smallest ambiguous patterns, $P_1$ and $P_2$, each with six mines, and shows they are the only ambiguous patterns with six or fewer mines. Below threshold these patterns almost never appear, so an island-by-island inference algorithm succeeds; above threshold they appear many times, and each occurrence acts as an unavoidable $50/50$ coin flip that no algorithm can eliminate. At criticality their number converges to a Poisson distribution with mean $c^6$, giving the coarse transition window.

Load-bearing premise

The upper bound above the threshold rests on Lemma 4, which assumes that many separated copies of the two smallest ambiguous patterns act as independent $50/50$ guesses, so that any algorithm's success probability is at most $2^{-k}+o(1)$; the paper states this lemma without a proof.

Editorial extensions

If this is right

For mine densities well below $n^{-1/6}$, random Minesweeper is computationally easy: the paper supplies an explicit linear-time algorithm that succeeds with high probability.
For densities well above $n^{-1/6}$, no algorithm, however clever, can win with more than $o(1)$ probability, so the ambiguity is intrinsic to the random instance rather than a limitation of a particular strategy.
In the critical window $p\sim c n^{-1/6}$, the success probability is bounded away from both $0$ and $1$, showing the phase transition is coarse rather than sharp.
In the random process where mines are added one at a time, non-solvability coincides with the first appearance of $P_1$ or $P_2$, and once such a pattern appears it is almost surely never destroyed before $n/2$ mines are placed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the same envelope classification could be pushed to patterns with more mines, the threshold exponent might generalise: a puzzle whose smallest ambiguity has $k$ mines would plausibly transition at $p=\Theta(n^{-1/k})$.
A direct numerical test is to simulate $M_{n,p}$ at $p=c n^{-1/6}$ and compare the observed failure probability with $1-\exp(-2c^6)$, the prediction obtained by counting occurrences of $P_1$ and $P_2$ as independent Poisson variables.
The almost-sure monotonicity proven in the random process suggests that, although solvability is not a monotone property, it is monotone enough that local ambiguous patterns may be the only obstruction; that intuition, if formalised, would connect the result to sharp-threshold theorems for monotone properties.
The paper leaves open the characterisation of larger ambiguous patterns; any enumeration of such patterns could sharpen the critical window or reveal additional transitions below the main threshold.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Louf proves something genuinely new: a coarse phase transition for solvability of random Minesweeper, at p around n^{-1/6}. The direction is right and the main ideas are visible. The classification of the two minimal ambiguous patterns (Proposition 3) is a real piece of work, and the envelope lemmas are clever. The linear-time algorithm below threshold is clean, as is the island decomposition. The hitting-time result in Section 5 is a nice bonus.

But the paper is not complete. The unsolvability half of Theorem 1 rests on Lemma 4, which asserts that k occurrences of P1/P2 force any algorithm to succeed with probability at most 2^{-k}+o(1). This is stated without proof. It needs at least two things: a proof that each occurrence gives a binary choice whose posterior is 1/2, and an argument that multiple occurrences give independent choices—especially since occurrences are subgrid matches and are not required to be disjoint. Without a precise statement and proof of Lemma 4, the upper bound in Theorem 1 is not established. The stress-test note is right about this.

The other soft spot is Section 4.4. The critical window is the most delicate part, and the paper explicitly leaves the details 'as an exercise'. The Stein-Chen Poisson approximation and the conditioning argument need to be written out. That is fixable, but it is not a minor typo.

One concern the reader raised does not actually land: the claim that Lemmas 12/13 are applied outside their stated range. At criticality the paper applies them with k=7, and p ~ c n^{-1/6} is indeed o(n^{-1/7}), so the condition is satisfied. That part is fine.

Who is this for? Anyone working on random discrete structures and thresholds. The result is important enough that the referee process should see it, but the current version is far from publishable as is. I would ask for a full proof of Lemma 4, a written-out critical-window argument, and a careful statement about overlap of occurrences. If those are supplied, it should be a strong paper.

My recommendation: send to peer review, with a clear expectation of major revision.

Referee Report

3 major / 5 minor

Summary. The paper studies the random Minesweeper instance M_{n,p} on an n-cell rectangular grid with independent mines of probability p. The main result, Theorem 1, claims a coarse phase transition at p=Theta(n^{-1/6}): below this scale a linear-time algorithm solves the instance with high probability, above this scale no algorithm succeeds with high probability, and at the critical scale the optimal success probability is bounded away from both 0 and 1. The strategy is to identify the smallest ambiguous patterns, P1 and P2, each using 6 mines, then to show that their appearance forces a random binary choice that no algorithm can resolve. The paper also contains a random-process version in which mines are added one by one, with a claimed hitting-time property and almost-sure monotonicity.

Significance. If the proofs are completed, the result is a clean and interesting phase-transition theorem for a non-monotone random discrete structure. The threshold exponent n^{-1/6} arises naturally from the size of the smallest ambiguous patterns, and the paper gives a constructive linear-time algorithm below the threshold. The classification of minimal ambiguous patterns in Proposition 3 is a substantial finite-case analysis, and the additional process-level results in Section 5 are appealing. The main obstacle is that the key unsolvability lemma, Lemma 4, is stated without proof, and the critical-window section is only sketched. These are load-bearing for Theorem 1, so the central claim is not yet fully established as written.

major comments (3)

[Section 3, Lemma 4] Lemma 4 is the central bridge from the appearance of ambiguous patterns to unsolvability, but no proof is provided. The lemma asserts that conditionally on at least k << n occurrences of P1 and P2, every algorithm succeeds with probability at most 2^{-k}+o(1). This is used in Sections 4.2 and 4.4 to obtain the upper bounds in Theorem 1. Proposition 3 only classifies the smallest ambiguous patterns; it does not imply that each occurrence contributes an independent fair binary choice. Moreover, occurrences are defined as subgrid matches and are not required to be disjoint, so overlapping occurrences could share hidden cells and reduce the number of independent degrees of freedom. Please supply a complete proof of Lemma 4, or replace it with a lemma that applies to the disjoint occurrences produced by Lemma 14 and prove that lemma in detail.
[Section 4.4] The critical-window case, which is the third bullet of Theorem 1, is only sketched and the details are explicitly left as an exercise. This is a load-bearing part of the main theorem and cannot be deferred. In particular, the Poisson approximation via the Stein-Chen method requires a precise dependency-graph argument; the lower bound epsilon in Theorem 1 is not explicitly derived; and the application of Lemma 4 at criticality, where the number of occurrences is typically bounded, needs a careful error analysis. Please write out the full proof of Section 4.4.
[Section 4.2 and Section 4.4] The upper-bound arguments in both the supercritical and critical regimes rest entirely on Lemma 4. Since Lemma 4 is unproved, the unsolvability half of Theorem 1 does not follow from the current manuscript. The proof needs to establish, at minimum, that the occurrences counted by Lemma 14 are causally independent in the sense of the game: revealing cells in one occurrence cannot provide information about the hidden cells of another occurrence, and the posterior probability of each occurrence is 1/2. This should be stated and proved explicitly.

minor comments (5)

[Section 5, Proposition 5] The proof of Proposition 5 is left as an exercise to the reader. Since this proposition is a stated result, please include the proof or a reference, or rephrase it as a remark without proof.
[Section 2] The asymptotic notation 'p << n^{-1/k}' is used throughout but never defined. Please define it precisely, for instance as p n^{1/k} -> 0.
[Section 4.4] In the critical window, the statement 'the expected number of occurrences of P1 (resp. P2) is c^6 + o(1)' should be justified by an explicit computation including the (1-p)^{58} factor and the number of possible positions; this is standard but should be written out.
[Section 5.1] Theorem 15 is said to be a direct consequence of Proposition 16 and the reasoning of Section 4.3, but the implication is not fully spelled out. In particular, one should argue that if no island contains more than 6 mines and no occurrence of P1 or P2 is present, then every ambiguous pattern is absent, so the algorithm of Section 4.3 succeeds. Please add this argument.
[Section 5, process definition] The phrase 'All steps are pairwise independent' is unclear; the steps are exchangeable but not pairwise independent in the usual sense. Please rephrase to describe the process correctly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the threshold exponent is derived from pattern counting and standard probabilistic bounds, with no fitted parameter or self-citation chain.

full rationale

The paper derives the phase transition from two independent ingredients: a finite classification of the smallest ambiguous patterns (Proposition 3) and probabilistic estimates for the appearance of those patterns (Lemmas 12–14). The critical exponent n^{-1/6} arises because the smallest ambiguous patterns contain exactly 6 mines, so their expected number is of order n p^6. This is a direct calculation, not a quantity fitted to the target result. No parameter is calibrated to make Theorem 1 come out; no self-citation is load-bearing; and no uniqueness theorem from the author's prior work is invoked. Lemma 4 is indeed stated without proof, and the unsolvability bound depends on it, but an unproved lemma is a correctness gap, not circularity: Lemma 4 does not assume Theorem 1 or any equivalent formulation, and its content (many disjoint 50/50 ambiguous patterns defeat any algorithm) is not the same as the theorem it supports. The finite case analysis in Proposition 3 uses the paper's own definitions of ambiguous patterns and envelopes, which is legitimate derivation rather than assuming the conclusion. Overall, the derivation chain is self-contained and not circular.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper's proof rests on standard probabilistic tools and on two structural claims: Proposition 3 (a finite classification of small ambiguous patterns, proved by case analysis but dependent on figures) and Lemma 4 (an unproved claim about independent coin flips from disjoint ambiguous patterns). There are no free parameters and no invented entities.

assumptions (3)

domain assumption The characterization of ambiguous patterns with at most 6 mines (Proposition 3) is correct; it relies on a finite case analysis and the visibility of Figures 2 and 3.
The conclusion that all islands below criticality avoid ambiguity depends on P1/P2 being the only small ambiguous patterns.
ad hoc to paper Occurrences of P1/P2 in disjoint 8x8 boxes are causally independent in the sense of Lemma 4.
Lemma 4 is stated without proof; a formal proof would need to show that no algorithm can transfer information between disjoint occurrences.
standard math Standard probabilistic tools (Chernoff bounds, Stein-Chen Poisson approximation, local limit theorem) hold as stated.
These tools are used without proof in Sections 4 and 5.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Phase transition for Minesweeper." pith.science (2026). https://pith.science/paper/R737525D

@misc{pith2026250601634,
  author       = {Pith},
  title        = {Pith review of: Phase transition for Minesweeper},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R737525D}},
  note         = {Machine review of arXiv:2506.01634}
}

read the original abstract

We prove a coarse phase transition for the game of Minesweeper: above a certain critical mine density, the game becomes unsolvable with high probability, whereas below the critical mine density it can be solved with a linear time algorithm.

Figures

Figures reproduced from arXiv: 2506.01634 by the authors.

**Figure 2.** The two smallest ambiguous patterns P1 and P2 and their corresponding ambiguous grid state S min . 3 Ambiguous patterns A pattern is a mine assignment on a grid such that there is no mine on the first and last two rows and columns, but there is a mine on the third and third-to-last row and column. Roughly speaking, this way we ensure that patterns are independent (in terms of solving), but that we don’t encode the s… view at source ↗

**Figure 3.** Adding a mine to the ambiguous pattern P1 to create a non-ambiguous pattern [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: An ambiguous grid state and its envelope in purple. [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

**Figure 5.** Figure 5: An ambiguous pattern with 8 mines, and its associated ambiguous grid state with 8 flags the only hidden cells in the neighborhood of a3 are b2, b3 and b4. Therefore we have the system of equations Sclue(a2) = 1b2 contains a mine + 1b3 contains a mine Sclue(a3) = 1b2 co…

**Figure 6.** Figure 6: Two more nice ambiguous grid states [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]

**Figure 7.** Figure 7: A grid state and its islands in orange. We now show that when the mine density is small enough, mines do not concentrate too much in small regions. Lemma 12. Let k = 6 or 7. If p << n−1/k, then, the expected number of 100 × 100 subgrids of Mn,p, containing k mines or m…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

Louis H. Y. Chen. Poisson approximation for dependent trials.Ann. Probab., 3:534–545, 1975

work page 1975
[2]

A phase transition in Minesweeper

Ross Dempsey and Charles Guinn. A phase transition in Minesweeper. In10th international conference on fun with algorithms. FUN 2021, May 30 – June 1, 2021, Favignana Island, Sicily, Italy. Proceedings, page 10. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik, 2020. Id/No 12

work page 2021
[3]

Sharp thresholds of graph properties, and thek-SAT problem (with an appendix by Jean Bourgain).J

Ehud Friedgut. Sharp thresholds of graph properties, and thek-SAT problem (with an appendix by Jean Bourgain).J. Am. Math. Soc., 12(4):1017–1054, 1999

work page 1999
[4]

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants

MIT Hardness Group, Della Hendrickson, and Andy Tockman. Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants. In Andrei Z. Broder and Tami Tamir, editors,12th International Conference on Fun with Algorithms (FUN 2024), volume 291 ofLeibniz International Proceedings in Informatics...

work page 2024
[5]

Wiley-Intersci

Svante Janson, Tomasz Łuczak, and Andrzej Ruciński.Random graphs. Wiley-Intersci. Ser. Discrete Math. Optim. New York, NY: Wiley, 2000

work page 2000
[6]

Threshold phenomena and influence: perspectives from mathematics, computer science, and economics

Gil Kalai and Shmuel Safra. Threshold phenomena and influence: perspectives from mathematics, computer science, and economics. InComputational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algori...

work page 2001
[7]

Richard M. Karp. Reducibility among combinatorial problems. InComplexity of computer computations. Proceedings of a symposium on the complexity of computer computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, mathematics program, IBM World Trade Corpor...

work page 1972
[8]

Minesweeper is NP-complete.Math

Sadie Kaye. Minesweeper is NP-complete.Math. Intell., 22(2):9–15, 2000. 12

work page 2000

Show all 10 references

[9]

Searching for (sharp) thresholds in random structures: where are we now?Bull

Will Perkins. Searching for (sharp) thresholds in random structures: where are we now?Bull. Am. Math. Soc., New Ser., 62(1):113–143, 2025

2025
[10]

Minesweeper may not be NP-complete but is hard nonetheless

Allan Scott, Ulrike Stege, and Iris Van Rooij. Minesweeper may not be NP-complete but is hard nonetheless. Math. Intell., 33(4):5–17, 2011. 13

2011

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Louis H. Y. Chen. Poisson approximation for dependent trials.Ann. Probab., 3:534–545, 1975

work page 1975

[2] [2]

A phase transition in Minesweeper

Ross Dempsey and Charles Guinn. A phase transition in Minesweeper. In10th international conference on fun with algorithms. FUN 2021, May 30 – June 1, 2021, Favignana Island, Sicily, Italy. Proceedings, page 10. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik, 2020. Id/No 12

work page 2021

[3] [3]

Sharp thresholds of graph properties, and thek-SAT problem (with an appendix by Jean Bourgain).J

Ehud Friedgut. Sharp thresholds of graph properties, and thek-SAT problem (with an appendix by Jean Bourgain).J. Am. Math. Soc., 12(4):1017–1054, 1999

work page 1999

[4] [4]

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants

MIT Hardness Group, Della Hendrickson, and Andy Tockman. Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants. In Andrei Z. Broder and Tami Tamir, editors,12th International Conference on Fun with Algorithms (FUN 2024), volume 291 ofLeibniz International Proceedings in Informatics...

work page 2024

[5] [5]

Wiley-Intersci

Svante Janson, Tomasz Łuczak, and Andrzej Ruciński.Random graphs. Wiley-Intersci. Ser. Discrete Math. Optim. New York, NY: Wiley, 2000

work page 2000

[6] [6]

Threshold phenomena and influence: perspectives from mathematics, computer science, and economics

Gil Kalai and Shmuel Safra. Threshold phenomena and influence: perspectives from mathematics, computer science, and economics. InComputational complexity and statistical physics. Selected papers based on the presentation at the workshops on computational complexity and statistical physics, Santa Fe, NM, USA, September 2001, and phase transition and algori...

work page 2001

[7] [7]

Richard M. Karp. Reducibility among combinatorial problems. InComplexity of computer computations. Proceedings of a symposium on the complexity of computer computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, mathematics program, IBM World Trade Corpor...

work page 1972

[8] [8]

Minesweeper is NP-complete.Math

Sadie Kaye. Minesweeper is NP-complete.Math. Intell., 22(2):9–15, 2000. 12

work page 2000