I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear algebra problem. I reduce the matrix to reduced row echelon form and then use the following logic on each row to try to make further progress:
- If the total (RHS) is not zero and is the same as the sum of the +ve (or -ve) numbers in the row then they must all be 1s
- If the total is zero and there are only +ve (or -ve) numbers then they must all be zeros
Here's an example matrix. Each variable can be 0 or 1 and the matrix is partitioned, the last column is the RHS of the linear equation: $$\left[\begin{array}{cccccc|c} 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{array}\right]$$ So using $a$, $b$, $c$, etc. as the variables, since they can only be 0 or 1, the above says:
- Either $a$ or $b$ is 1
- Either $a$, $b$ or $c$ is 1
- Either $c$ or $e$ is 1
- Either $d$ or $e$ is 1
The RREF matrix is then: $$\left[\begin{array}{cccccc|c} 1 & 0 & 0 & -1 & 0 & -1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{array}\right]$$ In the above no further progress can be made. This seems to solve the problem for all the cases I have checked that have single solutions. My questions are:
Are there other logical cases I am missing that can yield more information?
Is there a better way of analysing the matrix (e.g., Binary Integer Programming)?