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.