Minesweeper as a linear algebra problem

Question

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:

1. 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
2. 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:

1. Are there other logical cases I am missing that can yield more information?

2. Is there a better way of analysing the matrix (e.g., Binary Integer Programming)?

Answer 1

The only additional case I identified was a modification to case 1 above:

1. If the total (RHS) is not zero and is the same as the sum of the +ve (or -ve) numbers in the row then the entries of the same sign as the total must all be 1s and the other entries must all be zeros

I believe this solves all solveable cases. The remaining cases are characterised by multiple solutions which results in free variables in the RREF matrix that has no application of the above 2 rules.