Faster algorithm solving minesweeper puzzles (1)

Minesweeper is something that I'm always addicted to. This is obvious when this blog contains multiple entries talking about different aspects of this absolute classic. Last time, I talked about solving minesweeper using logical deduction generalised as a satisfiability problem. That was quite a long time ago -- when I was playing mienfield. 3 years after that I am now addicted to another minesweeper game called Minesweeper: Collector, that you can find on the Google play store.

Yes of course. Using ILP (integer linear programming) or even SAT (satisfiability) to solve minesweeper is not a very smart idea. Since we are working with equations and we know integral solution exists, we can simply employ linear algebra to make our life easier.

It is a bit hard to define how useful a deduction is by solving all the equations. For instance if we can conclude from 100 equations that now the space of possible solutions has dimension 68, then probably a faster way to solve the puzzle could be done by performing an educated guess in terms of probability. However probability is not something that linear algebra can handle easily so we would simply look for any definite deduction here. The most desirable result from the algorithm is that we can deduce the solution of some particular grids.

For the classic rectangular minesweeper we can think the whole puzzle as a matrix $M\in \mathbb{R} ^{m\times n}$, then we can setup variables $v_{11},...,v_{mn}$. Of course the same idea applies to different kinds of minesweeper shape [hexagonal etc] it is just the naming/coordinate setup that differs. They are supposed to be binary, but this is some technicality that we must handle later.

If a certain grid [for example row $s$ column $t$] is known but its neighborhoods are not all revealed then the grid yields an equation denoted by $E_{st}$. It has the form

$E_{st} ~:~ \sum _{p=s\pm 1, q = t\pm 1}^{1\leq p \leq m, 1\leq q \leq n} \delta _{pq}v_{pq} = c_{st}$

Where $c_{st}$ is the number of mines surrounded, and $\delta _{st} = 1$ if the grid $(s,t)$ is concealed, 0 otherwise. The aim of course, is to identify the mines [i.e. solving $v$] and receive more hints, eventually solving the whole puzzle.

Here is our first algorithm:

Algorithm 1.
-----
Input: A partially solved minesweeper matrix $M\in \mathbb{R}^{m\times n}$ provided that solution exists
Output: Any definite deduction

- Convert puzzle into linear eqautions
- RREF and solve $M$
- Interpret the solution
- Return any conclusion

For example we look at a classic 1-2 combination

$\begin{pmatrix}
\square & \square & \square & \square & \square & \square & \square & \square \\
\square & 2 & 1 & 1 & 2 & 2 & 1 & \square
\end{pmatrix}$

that should give you deduction like

$\begin{pmatrix}
\square & X & O & O & X & X &O & O \\
\square & 2 & 1 & 1 & 2 & 2 & 1 & O
\end{pmatrix}$

[where X represents mine and O is safe.] Let $v_1,...,v_{10}$ be the variables naming from left to right, top to bottom. Loot at the matrix reduction:

$\begin{pmatrix}
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2\\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 2\\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 2\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1
\end{pmatrix}

\xrightarrow[~]{rref}

\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 1 & 0 & 1\\
0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 1\\
0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & -1 & 0 & -1 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \end{pmatrix}$

What a mess! But we can still interpret the solution.

From row 3 we have $v_3+v_7+v_8+v_{10} = 0$, then by non-negativity they are all zero. By removing column 3,7,8,10 and row 3 we instantly get $v_2 = v_5 = v_6 = 1, v_4 = 0$. Now the solution space is given by:

$v = (0,1,0,0,1,1,0,0,1,0)^t + t(1,0,0,0,0,0,0,0,-1,0)^t$ where $t \in \mathbb{R}$, or simply $t \in \left\{ 0,1\right\}$.

as expected. However the deduction is very messy that it cannot be automated in an obvious way. Things get worse if the solution space is more complicated. Look at this simple example:

$\begin{pmatrix}
\square & \square &  \square & \square & \square & \square \\
\square & 1 & 1 & 2 & 2 & \square
\end{pmatrix}$

that yields immediately the following [this should be really obvious for any experienced player!]

$\begin{pmatrix}
\square & O &  \square & \square & X & \square \\
\square & 1 & 1 & 2 & 2 & \square
\end{pmatrix}$

assign the names $v_1,...,v_8$ as before, reduce the matrix:

$\begin{pmatrix}
1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1\\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 2\\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 2
\end{pmatrix}

\xrightarrow[~]{rref}

\begin{pmatrix}1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2\\
0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & -1\\
0 & 0 & 1 & 0 & 0 & -1 & 0 & -1 & 0\\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 2 \end{pmatrix}$

The only thing we can deduce is the second equation. Since we know $v_2,v_5\in \left\{ 0,1\right\}$ we must have $v_2 = 0, v_5 = 1$ as predicted, and this is basically all we know.

The trouble here is the deduction heavily relies on facts that we have omitted by modelling the problem into a system of linear equations. Of course rearranging the columns [hence changing the RREF] could solve this problem, but recognising the rearrangement of columns is basically equivalent to knowing the grids that can be definitely [or at least almost definitely - when the solution of that grid has a very low dimension] which is the fundamental aim.

To improve our efficiency instead of adding conditionals that check whether an equation is useful for deduction, we can change the fields that we are working on. Rings wouldn't work [and that is why ILP is bad], but we can look at fields, like $F_2$ or $F_7$!. This will be addressed in the next entry.