# Minesweeper as a linear algebra problem

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)?