You can compare the probability of the having a mine according to the numbers already discovered. In this case, there is 3 nearby, with 1 mine already located, so 2 mines left and 3 possible cells, so there are 2/3 chances that there is a mine. Whereas the average probability to have a mine is 99/(16*30) = 20,6 %
Is there anybody else who thinks that this should be an optimization game?
4 Likes
If there was āPrologā in the list of languages I may have had a goā¦
Pity itās not there when weāre trying to resolve a logic puzzle!
Iāve improved my C++ solution. Refining the probabilities using model counting when itās not too expensive:
The code may be difficult to understand without a mathematical explanation. Basically, every slot on the board is a 0 or 1, viewed as a SAT problem. There are many possibilities for the mine/no
mine configurations. When you have a list of every possible configuration, not only you can find all the guaranteed mines/safe spots, for the others you simply KNOW which one is the lowest probability to be a mine.
The caveat is that there is an exponential number of configurations, hence it is be cheaper to store local configurations, and merge only a few of them to avoid a timeout or memory explosion.
My solution is near perfection but still fails 50% of the time because some situations are truly random! (Even when you know have the perfect knowledge that the probability is 1/3, you still have a chance to pick the wrong tile)
For tiles with no knowledge at all, the probability of the tile being safe is assumed to be ((remainingTiles - remainingMines) / remainingTiles), when the exact counting is too expensive. Sometimes it could be safer to pick one of these, when all the nearby tiles have high probability to be mines 
I donāt think so.
If you can prove one place where there are no mines, then you donāt need to know all the possible configurations. In one round, you cannot click all empty cells at once. You only need to know one cell that is guaranteed not to contain a mine.
If you cannot prove that there is no mine in some cell, then you start looking for the cell with the least probability. Only in this case it may be necessary to know all the configurations.
I am surprised you get to 50% of success. I made a simpler algorithm and when it fails near the end, when I check, it seems to me it plays the best move, with lowest probability of mine, or that each cell has the same probability of having a mine.
So my solution involves clicking on photos of mountains or traffic lights.
I didnāt spend time on it so I donāt know how I would actually implement this exactly but a trained human can play minesweeper optimally without doing millions of calculations for each turn, so it should be possible to have a perfect bot without any costly search.
Most logical deductions you can do are very local and can be done just by working on all 4x4 subgrids individually, which reduces the search spaces a lot.
Even if you limit it to 3x3 subgrids and work on even smaller spaces youād probably not miss a lot.
You are correct. That is what Iām doing. Except I donāt stop my algorithm as soon as a safe spot has been found, because itās the same outcome regardless.
My algorithm computes everything on every turn, and if there is a safe spot is will be labelled with the probability one and then the algorithm will select that tile because it is the highest probability.
Good day dear contributor and participants.
I have an idea, how to make the process of solutions comparisons more reliable and clear, considering that sometimes you cannot avoid the influence of The Great Random.
Unfortunately I cannot estimate how much effort it would take, but suppose that for experienced developers it would not be longer than a polar night.
The test should retry the solution for 10 times. For every round revealed bombs should be counted as 1 point for first 10 bombs, 2 points for next 10 and so on, up to 10 points for last 9 bombs.
I realize that sometimes you just have a bad start, thatās why we need 10 rounds. In the long run a better algorithm should get better results with much higher probability.
Thank you for reading. Please ālikeā if you agree with this idea and share your suggestion how it can be improved.
2 Likes
The event is over.
In the end, it seems the solutions were chosen according to reviews. Which means the simplest and most unreliable codes have won. 
Itās a bit disappointing. It doesnāt matter that an algorithm is better than another. You can write some garbage, as long as it worked once out of 1000 submits and got 100% completion, it is considered valid.
Iāve tested some of the ābestā solutions and they donāt work at all even after 20 submits.
2 Likes
Now letās talk seriously about this puzzle solving. No funny votes, no NP-solutions, no patterns. Just math and logic.
All cells in the grid are variables that can be 1 or 0 (1=mine, 0=empty). In our grid we have 16*30 variables from x[0] to x[479].
For every opened cell ābā with unopened neighbors x[1],ā¦,x[n] and neighbors-mines y[1],ā¦,y[m] we can write equation:
So, we have a system of equations. To solve it we need to do transformation to diagonal matrix
We canāt use the Gauss method, we should develop special operations for row manipulation.
Operation 1.
If in some row b = 0 then all variables in this row are 0.
I stop calculation in this case and open the cell according to the variable from this row.
To continue calculation to get a full solution we should add new rows in the matrix for each variable from this row.
means we should add rows
Operation 2.
If in some row the number of variables equal to b then all variables in this row are 1. We should add new rows in the matrix for each variable from this row.
means we should add rows
Operation 3.
If one row is subset for another row then we can subtract rows.
means we should add row
Operation 4.
Merge variables in rows intersection.
means intersection Z = x[2]+x[3] contains maximum one mine only, and we have temporary row (we will not add Z to matrix) with b3 = min(b1, intersection.length)
And for two rows
Z = 1 (b3)
Z+x[4] = 2 (b2)
and the size of the remaining part x[4] is equal to the difference of b
then we should add new row for second row remaining part
Operation 5.
Delete empty rows.
If we have rows
we will get after subtracting rows
We should exclude the third row from the matrix.
BUT!
If we get ERROR when we have empty row and b != 0 it means this matrix have no solution - you place some bomb incorrectly.
Thatās all.
Each round I make a matrix and solve it.
If the solution has no variables with 0 then we go to STEP 2 - search a cell with minimal chance to be a mine. But this is another story.
3 Likes
Sounds correct and would be happy to compare it with some other solutions in numbers.
I suppose that the approach which I suggested above will show the real quality of any solution - so we will be able to stop compete in logical debates, but see some real numbers that prove one or another approach is better.
Iām not sure your solver will find all the findable mines, because the only constraints that you store are sums and Minesweeper is NP-complete (i.e the sums combined together generate constraints which are not sums, for example, a minimum or maximum amount of mines in a given area)
For the sake of completeness, did you think about the last trick, adding an equation for all the remaining tiles?
i.e
Remaining tile 1 + Remaining tile 2 + ā¦ + Remaining tiles N = (99 - found mines)
The result should be slightly better than only adding sums for the local constraints.
1 Like
Yes, I started with a linear programming task that has constraints
But this path requires the use of the Gauss method and Gomory cut. Are you ready for this? (I have solved some CodinGame puzzles as linear programming tasks, I have a ready js class, I can).
But after I undestend that it was possible not to use ordinary algebraic calculations, I develope especial operations to manipulate strings, then these constraints turned out to be unnecessary.
Youāre right.
This equation is very useful for STEP 2. It gives us the probability of finding a mine in cells that are not neighbors of open cells.
I added this equation to the matrix.
I see that sometimes it opens the cell according to this additional equation.
Thanks!
This is not an NP-complete task. For a matrix with D rows, I would estimate the complexity of the algorithm as
D * D * L operations of each complexity L*L, i.e. D * D * L * L * L, where L is the number of variables in one row (so, maximum L is 8).
There are some cases in which the graphical solution is not working, did it happened to someone else?
I think this one should be hard, not medium
Cummunity success rate is only 14%. I think this should move to hard or even very hard
Thanks for this very fun challenge! I did it with numpy arrays and convolutions and came up with a pretty solution.