TAOCP 7.2.2.2 Exercise 114

Section 7.2.2.2: Satisfiability

Exercise 114. [27] [27] Each cell $(i, j)$ of a given rectangular grid either contains a land mine ($x_{i,j} = 1$) or is safe ($x_{i,j} = 0$). In the game of Minesweeper, you are supposed to identify all of the hidden mines, by probing locations that you hope are safe: If you decide to probe a cell with $x_{i,j} = 1$, the mine explodes and you die (at least virtually). But if $x_{i,j} = 0$ you're told the number $n_{i,j}$ of neighboring cells that contain mines, $0 \le n_{i,j} \le 8$, and you live to make another probe. By carefully considering these numeric clues, you can often continue with completely safe probes, eventually touching every mine-free cell.

For example, suppose the hidden mines happen to match the $25 \times 30$ pattern of the Cheshire cat (Fig. 36), and you start by probing the upper right corner. That cell turns out to be safe, and you learn that $n_{1,30} = 0$; hence it's safe to probe all three neighbors of $(1, 30)$. Continuing in this vein soon leads to illustration (o) below, which depicts information about cells $(i, j)$ for $1 \le i \le 9$ and $21 \le j \le 30$; unprobed cells are

shown in gray, otherwise the value of $u_{i,j}$ appears. From this data it's easy to deduce that $x_{1,24} = x_{2,24} = x_{3,25} = x_{4,25} = \cdots = x_{9,26} = 1$; you'll never want to probe in those places, so you can mark such cells with X, arriving at state $(\beta)$ since $n_{3,24} = n_{5,25} = 4$. Further progress downward to row 17, then leftward and up, leads without difficulty to state $(\gamma)$. (Notice that this process is analogous to digital tomography, because you're trying to reconstruct a binary array from information about partial sums.)

$$(\alpha) = \begin{array}{l}\includegraphics{fig_alpha}\end{array} \quad (\beta) = \begin{array}{l}\includegraphics{fig_beta}\end{array} \quad (\gamma) = \begin{array}{l}\includegraphics{fig_gamma}\end{array}$$

a) Now find safe probes for all thirteen of the cells that remain gray in $(\gamma)$. b) Exactly how much of the Cheshire cat can be revealed without making any unsafe guesses, if you're told in advance that (i) $x_{1,1} = 0$? (ii) $x_{1,30} = 0$? (iii) $x_{25,1} = 0$? (iv) $x_{25,30} = 0$? (v) all four corners are safe? Hint: A SAT solver can help.

Verified: no
Solve time: 2m15s

---

Setup

The exercise requires the exact mine configuration of the Cheshire cat pattern in Fig. 36 and the three intermediate Minesweeper states $(\alpha)$, $(\beta)$, and $(\gamma)$. The data needed to solve part (a) are the thirteen unrevealed cells remaining in $(\gamma)$ together with all clue values $n_{i,j}$ adjacent to them. The data needed to solve part (b) are the complete $25 \times 30$ binary image from Fig. 36, because the question asks how many cells can be logically determined under several additional corner constraints.

The statement provided here contains only placeholders,

$$ (\alpha)=\begin{array}{l}\includegraphics{fig_alpha}\end{array},\qquad (\beta)=\begin{array}{l}\includegraphics{fig_beta}\end{array},\qquad (\gamma)=\begin{array}{l}\includegraphics{fig_gamma}\end{array}, $$

and does not include the actual grids or the clue numbers. Therefore the variables $x_{i,j}$ and $n_{i,j}$ required for the deduction cannot be instantiated.

Solution

The intended method is to translate the Minesweeper instance into a SAT instance. For every cell $(i,j)$ introduce a Boolean variable $x_{i,j}$, where

$$ x_{i,j}=1 $$

means that the cell contains a mine.

For every revealed safe cell $(i,j)$ with clue value $n_{i,j}$, the corresponding constraint is

$$ \sum_{(p,q)\in N(i,j)}x_{p,q}=n_{i,j}, $$

where $N(i,j)$ is the set of neighboring cells of $(i,j)$. Each such cardinality constraint is converted into conjunctive normal form by a standard SAT encoding. A cell is a safe probe exactly when the SAT instance together with

$$ x_{i,j}=1 $$

is unsatisfiable. A cell is a forced mine exactly when the SAT instance together with

$$ x_{i,j}=0 $$

is unsatisfiable.

For part (a), the thirteen gray cells in $(\gamma)$ must be tested one at a time. For each remaining cell $(i,j)$, the two satisfiability queries are

$$ S\wedge (x_{i,j}=0) $$

and

$$ S\wedge (x_{i,j}=1), $$

where $S$ is the SAT formula obtained from all currently revealed information. A cell is a guaranteed safe probe precisely when only the first formula is satisfiable.

For part (b), the same construction is applied after adding the corresponding corner assumptions. For example, case (i) adds

$$ x_{1,1}=0, $$

case (ii) adds

$$ x_{1,30}=0, $$

and similarly for the other cases. A cell can be revealed without guessing exactly when its value is forced in every satisfying assignment of the resulting SAT instance.

The numerical answers require the missing pixel data from Fig. 36 and the missing clue grids $(\alpha)$, $(\beta)$, and $(\gamma)$. Without those data, multiple different Minesweeper instances satisfy the textual description and produce different sets of safe probes and different reveal counts.

Verification

The deduction procedure above follows directly from the definition of satisfiability. If

$$ S\wedge(x_{i,j}=1) $$

has no satisfying assignment, then every solution of $S$ has

$$ x_{i,j}=0, $$

so probing $(i,j)$ is guaranteed safe. Conversely, if both

$$ S\wedge(x_{i,j}=0) $$

and

$$ S\wedge(x_{i,j}=1) $$

are satisfiable, then two compatible mine configurations exist with different values at $(i,j)$, so no deduction without guessing is possible.

This completes the verification of the method. ∎

Notes

The complete numerical solution can be produced once the actual contents of Fig. 36 and the grids $(\alpha)$, $(\beta)$, and $(\gamma)$ are supplied. The SAT formulation above is also the standard approach used for general Minesweeper deduction problems.