# and matrix solvers in general.

## Getting the computer’s help to play Mine Sweeper.

For years before I became interested in Python I had a web site offering somewhat similar software for C++ as autorej is for Python. One day a fellow from Finland contacted me and asked for the source code. (Sometimes I offered the code, but most times I offered apps that used the code.) I of course emailed it to him, but I asked casually what his application was. It said playing MineSweeper! I pointed out that if he got answers that were between 0 and 1 for a hidden square that probably he should consider those to be probabilities. He assured me he was only interested sure things: 0 for no bomb in a square, 1 for a bomb.

So when prepping these examples for Python and users (and anyone else who is interested), I decided to try my hand at solving  Minesweeper with linear equations, as I had never bothered to ask the customer HOW exactly he did that. I guess I figured it was straightforward. Let’s take this little segment which I choose from a must larger problem because it is a legitimate stand-alone problem in itself except for the three bottom squares in the right-most column which we will not be able to determine. So what are the equations? Let’s refer to the elements of the above grid as we would elements of a matrix that size, e.g., A11, A12, etc. And call the NUMBER which is (or should be) in that square #A11, etc. Now first, the unknowns for our problem are the values in the blank, unexploded squares. For example, we want to know how many bombs (aero or one) are at A38.After some thought I realized there are two types:

1.       Each square with a bomb, such as square (2,2), is a simple equation, e.g., #A22=1.0

2.       Each number which is next (by left, right, up, down, or diagonal) to an unknown square also gives us an equation, e.g., from A23 we get

#A22  + #A32 + #A33 = 2

So we have to go create all those equations. Here is my is my matrix file as read by autorej’s read_problem() method (except for the last column which was helpful during building the file but cannot be present in the input file). Also note the comment lines marked with “#”.

Now….. before trying to solve this problem to find the numbers in the blank squares, are at least SOME of them in this first try, we should ask ourselves exactly WHAT we expect to see. Do we have any right to expect to get back ONLY INTEGERS? Actually, we would like that, but we have not inserted any constraints into the problem that would even encourage that, much less require it. The calculation process will begin by computing the Singular Value Decomposition of our matrix. Here are the singular values for this matrix:

[3.66882986e+00    3.29958015e+00    2.74052834e+00    2.44205520e+00

2.33557658e+00    1.85017432e+00    1.51369996e+00    1.28268753e+00

1.15207922e+00    9.33783720e-01    6.28601369e-01    5.72988469e-01

4.98618121e-01    4.38608280e-01    2.59847585e-16    1.82895960e-16

1.16177952e-16    3.02411221e-17    1.69841264e-33    0.00000000e+00]

No hint here of any likelihood for integer answer!! When sending the C++ code to my customer I pointed out that if he got answers that were between 0 and 1 for a hidden square that probably he should consider those to be probabilities. He assured me he was only interested sure things: 0 for no bomb in a square, 1 for a bomb.

Here are the answers that Autorej normal solver gives:

[-4.04451282e-16  1.00000000e+00  1.03922202e-15 -1.51275221e-02

1.00000000e+00  1.00000000e+00  4.05824099e-16  4.41513009e-03

-1.36256212e-15  2.74346447e-01 -2.74346447e-01  1.32495853e-15

2.74346447e-01  8.62826776e-01  8.62826776e-01  0.00000000e+00]

Most of the answers are indeed VERY CLOSE to zero or 1. But the 4th and 10th are about -0.2. What does that mean? It means we should try autorej’s Non-negative solver. Here is the answer that that gives:

[1.         1.         0.         0.         0.         1.

0.         0.         1.         1.         0.         0.

0.         0.         0.         0.         0.         1.02359314     0.97640686    0.        ]

Now that’s pretty good!! Even the two that are slightly off of one are very near to one. Terrific!

If we go into the problem and mark the new squares that are now solved with a red symbol we have this: All the remaining blank squares are actually empty. But I wasn’t actually playing the game by this point so I was not able to click them to show they are empty. Our problem setup had no information about certain squares, such as the last three in the last column.