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

2 Answers 2

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
-1
$\begingroup$

It's a little late but yes, there's more you can do. The row echelon form used to solve the matrix in minesweeper does not always immediately give you all possible answers. But you can use proof by contradiction in conjunction with this method. Then all possible solutions are guaranteed.

$\endgroup$

Your Answer

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

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