Phase transition for Minesweeper

Baptiste Louf · 2025

Read Phase transition for Minesweeper by Baptiste Louf (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01634.txt.

Introduction

Baptiste Louf proves a phase transition for the game Minesweeper in a mathematics paper from two thousand twenty-five, written alone. In the game, hidden mines must be flagged from number clues on a grid. The question is how mine density affects whether a board can be solved at all. Louf shows a coarse threshold effect. Above a critical density, boards become unsolvable with high probability. Below it, boards can be solved by an algorithm that runs in linear time.

Catalog record

CREATORBaptiste Louf
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-01634

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Phase transition for Minesweeper Baptiste Louf 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. Keywords: Phase transition, minesweeper, random discrete structures 1 Introduction Minesweeper is a classic computer game that starts with a rectangular grid whose cells have been obscured, under some of which lie mines. The player needs to determine where the mines are by revealing cells (without hitting a mine), and each revealed cell gives a clue about the number of mines in its vicinity. Figure 1: An ongoing game of minesweeper. All figures in this paper are screenshots from the website https://minesweeper.us/ . As a mathematical problem, Minesweeper has mostly been studied from the complexity theory perspective: in [ 8 ] it is shown that deciding whether a certain grid state is consistent with a mine assignment is NP-complete, and the inference problem (i.e. given a grid state, is there a safe cell to click on ?) is coNP-complete (see [ 10 , 4 ] ). However, these are worst-case complexity results. It is well known that many problems that are hard in the worst case become much more tractable when considering random instances. A famous example is the 3 -SAT problem (which is NP-complete [ 7 ] ): consider a random instance with a fixed density of clauses. If the density is above a certain threshold, then the instance is most likely unsatisfiable; if it is below the threshold, it is most likely satisfiable—and finding a satisfying variable assignment can be done quickly 1 1 1 this very simplified presentation doesn’t do justice to the richness and complexity of the research on random SAT instances; we refer to [ 9 ] for a more detailed account. .This kind of behavior is referred to as a phase transition , and similar phenomena have been observed in many other random structures. We refer to [ 6 , 9 , 5 ] and references therein for more details. In this paper, we prove a phase transition result regarding whether a random Minesweeper instance is solvable, with respect to the mine density (this question has already been approached experimentally in [ 2 ] ). Note that contrary to most properties where a phase transition is observed, solvability of Minesweeper is not a monotone property. Indeed, adding a mine to an unsolvable instance can make it solvable (see Proposition 5 ). Let M_{n,p} be the random minesweeper instance on a rectangular grid of size n where each cell receives a mine independently with probability p . Our main result is the following. Theorem 1 . There is a coarse phase transition at p=\Theta(n^{-1/6}) , i.e. • if p=o(n^{-1/6}) then there exists a linear time algorithm that solves M_{n,p} with high probability; • if p>>n^{-1/6} then with high probability no algorithm solves M_{n,p} , i.e. \max_{\text{algorithms }\mathcal{A}}\mathbb{P}(\mathcal{A}\text{ solves }M_{n,p})=o(1); • for every c>0 , there exists \varepsilon such that, taking p\sim cn^{-1/6} and n large enough, \varepsilon\leq\max_{\text{algorithms }\mathcal{A}}\mathbb{P}(\mathcal{A}\text{ solves }M_{n,p})\leq 1-\varepsilon. The phase transition is driven by the emergence of small ambiguous mine patterns . This is reminiscent of Friedgut’s theorem [ 3 ] which states that for monotone properties, there is a coarse phase transition if and only if the property is well approximated by local constraints. This suggests that solvability of a random minesweeper instance is very close to being monotone. And indeed, we show it is " almost surely monotone " in Section 5 , where we study a random process version in which mines appear one after the other. In that same section, we also show a " hitting time property ", i.e. non-solvability coincides with the appearance of the smallest ambiguous pattern. The paper is organized this way: in Section 2 we give definitions. Section 3 is the main technical part of the proof, where we identify the smallest ambiguous patterns. Then in Section 4 , we prove the main theorem, using the results of Section 3 and standard probabilistic arguments. Finally, in Section 5 , we study the random mine process, showing a hitting time property and almost sure monotonicity. 2 Definitions Given a rectangular grid G , we define the neighborhood N(c) of a cell c as the cell itself plus the (up to 8) cells that touch it. This induces a natural distance d on the cells of the grid 2 2 2 the graph distance in the neighbor graph. . A mine assignment M on G is a function that assigns the value \varnothing (" empty ") or (" mine ") to each cell c\in G , while a grid state S on G is a function that assigns to each cell c\in G a value in \{\mathchoice{\raisebox{0.0pt}{\resizebox{411105}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{411105}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{287774}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{205552}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{hidden}$}}}}},0,1,2,3,4,5,6,7,8,\mathchoice{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}}{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}}{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}}{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}},\mathchoice{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{286719}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{204798}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{mine}$}}}}}\} . We say that c is a clue if S(c)\in\mathbb{Z} , a flag if S(c)=\mathchoice{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}}{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}}{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}}{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}} and hidden if S(c)=\mathchoice{\raisebox{0.0pt}{\resizebox{411105}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{411105}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{287774}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{205552}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{hidden}$}}}}} . A mine assignment M and a grid state S on the same grid G are said to be consistent if for each cell c , we have either : • S(c)=\mathchoice{\raisebox{0.0pt}{\resizebox{411105}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{411105}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{287774}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{205552}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{hidden}$}}}}} ; • S(c)=|\{c^{\prime}\in N(c)|M(c^{\prime})=\mathchoice{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{286719}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{204798}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{mine}$}}}}}\}| ; • S(c)\in\{\mathchoice{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{286719}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{204798}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{mine}$}}}}},\mathchoice{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}}{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}}{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}}{\raisebox{0.0pt}{\resizebox{0}{0}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[page]{hwemoji-assets.pdf}$}}}}}\} and M(c)=\mathchoice{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{286719}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{204798}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{mine}$}}}}} . Finally, if a mine assignment M and a grid state S are consistent with each other, and if c\in S is hidden, then let \text{Reveal}(M,S,c) be the grid state that equals S except at c , where it is equal to if M(c)=\mathchoice{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{286719}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{204798}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{mine}$}}}}} , and to |\{c^{\prime}\in N(c)|M(c^{\prime})=\mathchoice{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{286719}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{204798}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{mine}$}}}}}\}| otherwise. An algorithm \mathcal{A} is a function that associates to each grid state S one of its hidden cells. Given an algorithm \mathcal{A} and a mine assignment M of the grid G , we can define the sequence of grid states S^{\mathcal{A},M}_{t} by • S^{\mathcal{A},M}_{0}=\mathchoice{\raisebox{0.0pt}{\resizebox{411105}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{411105}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{287774}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{205552}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{hidden}$}}}}}^{G} ; • S^{\mathcal{A},M}_{t+1}=\text{Reveal}\left(M,S^{\mathcal{A},M}_{t},\mathcal{A}\left(S^{\mathcal{A},M}_{t}\right)\right) . We say that \mathcal{A} solves M if there is a t such that for every c\in M , we have that S^{\mathcal{A},M}_{t}(c)\neq\mathchoice{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{286719}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{204798}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{mine}$}}}}} and if S^{\mathcal{A},M}_{t}(c)=\mathchoice{\raisebox{0.0pt}{\resizebox{411105}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{411105}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{287774}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{hidden}$}}}}}{\raisebox{0.0pt}{\resizebox{205552}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{hidden}$}}}}} then M(c)=\mathchoice{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\displaystyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{409598}{403045}{\hbox{\raisebox{0.0pt}{$\textstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{286719}{282132}{\hbox{\raisebox{0.0pt}{$\scriptstyle\includegraphics[]{mine}$}}}}}{\raisebox{0.0pt}{\resizebox{204798}{201522}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\includegraphics[]{mine}$}}}}} . Remark 2 . Without loss of generality, we made three simplifying assumptions: • we do not allow flagging for algorithms here (in real life, they just help the player remember where the mines are). However, we will allow them for grid states, as it will simplify the exposition for ambiguous patterns (see Section 3 ); • the algorithms we consider do not take the number of mines as input; • we only consider deterministic algorithms. The last two assumptions are not restrictive for our purposes 3 3 3 as long as we don’t want to consider random algorithms whose source of randomness is not independent with the mine placement, which would defeat the purpose of the game anyways. , indeed we will consider the set of all possible algorithms, i.e. all possible moves at any time. Let a_{N} and b_{N} two integer sequences that both tend to infinity as N\to\infty . For each N , set n=n(N):=a_{N}\times b_{N} and let G_{n} the rectangular a_{N}\times b_{N} grid. From now on, we forget about N and only talk about n , the size of the grid. This will lead to slight abuses of notation, such as saying "as n\to\infty ", omitting that we are working along a subsequence. In

Read the complete text