Its always like this … any advice?
So, in 8 hours you made some solution, not the best. 
In your situation, for cell (12, 6) you must merge cells (13, 5) and (13, 6) - they contain one mine only.
Then for cell (12, 5) you will find the mine on which you blew up. (y:x)
no 5h. … whatever. it dosn’t mater …
BUt thx for your tipp … i totaly forgott to implement such logic. That will take me some time to implement. There can’t be a bomb on 13,5 because than there is no space for the second bomb arround 12.5 cause, 12,4 is 1, means its save, but 12.6 is done as well, means no space for the second bomb. … great
- This is not medium dificulty puzzle. I believe it very hard.
- When you press “Submit” system should make 100 tests and save your solution with success rate. Succes rate means how your solution is good.
5 Likes
the keyword here is probability. there is actually a video for this, code examples and I even found a paper about it. But you have to optimize it very well in order not to get a timeout
I used Wave Function Collapse to solve minesweeper. Here is how I approached it
What if we have this puzzle?
? ? ? ? ?
? 1 2 1 ?
? ? ? ? ?
Can we correctly make this progress?
? ? ? ? ? . ? . ? .
? 1 2 1 ? ==> . 1 2 1 .
? ? ? ? ? . ? . ? .
First calculate all the valid possibilities
. b . b . . . . . . . b . . . . . . b .
. 1 2 1 . . 1 2 1 . . 1 2 1 . . 1 2 1 .
. . . . . . b . b . . . . b . . b . . .
There are common areas that are always safe
Encode BOMB(b) = 1 , SAFE(.) = 2 , UNKNOWN(?) = BOMB | SAFE
For each possibility you just boolean ‘OR’ the
corresponding squares together and you get
. ? . ? .
. 1 2 1 .
. ? . ? .
Only modify the unknown squares.
This is expandable up to any size board but it grows
exponentially in runtime with size. Instead use a
smaller size, such as 3x3, 4x4, 5x5 and sample parts
of a larger board. When sampling part of a board
only use the non-perimeter squares for constraining
possibilities.
? . ? . . .
? 1 3 => . 1 3
. b ? . b .
For this 3x3 patch, the “3” is on the perimeter
and so it is not part of the constraints.
Similarly, the 3 does not help the 2 reduce
any unknowns because we lack information about
what is to the right of the 3.
? . ? ? . ?
? 2 3 => ? 2 3
. b ? . b ?
This follows a concept call Wave Function Collapse that you can also find here Coding Games and Programming Challenges to Code Better
405 non blank lines of code, 245 of it is the solver, 160 of it is unit tests
3 Likes
Emergency exit - click on an already open cell.
Try this:
while (1) {
for (let i=0; i<16; i++) readline();
console.log(“20 7”);
}
I used this feature in my first day version to avoid the timeout.
But you need to improve your algorithm actually.
Resubmited the solution - bugs fixed, achieved a 7/10 test pass.
But the vote has already passed two days.
And I understand that it would be possible to improve the random click algorithm when a free cell is not proven.
But when?
I do not think vote is closed. So submit anyway.
Closed after 3 review.
" THANK YOU FOR YOUR PARTICIPATION!
You will receive an email at the end of the event (Sunday, February 13, 11:00 PM) that will present you with the best solutions of the event."
No luck! I submitted just before posting in the forum.
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