The PGMS Equation Strategy

The PGMS Equation Strategy represents the information available on the board as a set of integer linear equations. Associated with an unknown tile $t$ is a variable $x_t$ that has the value one if the tile hides a mine, or zero otherwise.

An equation is generated for each known tile with an adjacent unknown tile. Each equation has the form $c=\sum _{t\in S}{x}_t$ where $S$ is a set of unknown tiles, and $c$ is a constant indicating the number of mines hidden among $S$ .. To simplify notation, the equation is written as $c\circeq S$ ..

Since the total number of hidden mines is known, an additional equation simply equates this number with the sum of all of the unknown tiles. For performance reasons, this equation is used only when there are eight or less unknown mines, or when guessing.

Every time a tile $t$ is determined safe or a mine, the board changes are propagated to all the equations containing $t$ and a new equation for the unknown neighbors of $t$ is added. To determine whether tiles are safe or a mine, the Equation Strategy iteratively applies the following rules until none are applicable:

• If $0\circeq S$ , all tiles in $S$ are safe.
• If $c\circeq S$ and $c=\left|S\right|$ , all tiles in $S$ are a mine.
• If $c_0\circeq S_0$ and $c_1\circeq S_1$ are two equations such that $S_0$ is a proper subset of $S_1$ , the equation $c_1-c_0\circeq S_1\setminus S_0$ is added.
• Let $c_0\circeq S_0$ and $c_1\circeq S_1$ be two equations such $c_0<c_1$ . The difference between the two equations is $c_1-c_0\circeq \left(S_1\setminus S_0\right)-\left(S_0\setminus S_1\right)$ . If $c_1-c_0=\left|S_1\setminus S_0\right|$ , all the tiles in $\left(S_1\setminus S_0\right)$ are a mine and all the tiles in $\left(S_0\setminus S_1\right)$ are safe. This rule is useful only when $S_0$ and $S_1$ share a tile.

The Equations Strategy must guess when presented with a board to which none of the rules apply. The Equation Strategy inspects each equation when guessing. For each tile $t$ it computes the value $P\left(t\right)$ as follows. Given an equation $c\circeq S$ , define its single equation probability to be $c/\left|S\right|$ .. The value $P\left(t\right)$ is largest single equation probability among all equations that contain $t$ .. The Equation Strategy picks the tile $t$ that minimizes $P\left(t\right)$ and then applies the rules listed above. A random choice is made when there is more than one tile that minimizes $P\left(t\right)$ ..

The Mio inspired modification to the Equation Strategy adds one more rule. Let $c_0\circeq S_0$ ,  $c_1\circeq S_1$ , and $c_2\circeq S_2$ be three equations such $c_0+c_1<c_2$ .. The combined equation is $c_2-c_1-c_0\circeq \left(S_2\setminus \left(S_1\cup S_0\right)\right)-\left(\left(S_1\cup S_0\right)\setminus S_2\right)-\left(S_1\cap S_0\right)$ .. If $c_2-c_1-c_0=\left|S_2\setminus \left(S_1\cup S_0\right)\right|$ , all the tiles in $\left(S_2\setminus \left(S_1\cup S_0\right)\right)$ are a mine and all the tiles in $\left(\left(S_1\cup S_0\right)\setminus S_2\right)\cup \left(S_1\cap S_0\right)$ are safe. This rule is useful only when $S_0$ and $S_2$ share a tile, and $S_1$ and $S_2$ share a different tile.