8
$\begingroup$

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

$\endgroup$
1

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks - I mean the 2 rules in the original problem statement $\endgroup$ Dec 3, 2020 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.