Minesweeper - Chance of one-click win
I'd like to know if it's possible to calculate the odds of winning a game of Minesweeper (on easy difficulty) in a single click. This page documents a bug that occurs if you do so, and they calculate the odds to around 1 in 800,000. However, this is based on the older version of Minesweeper, which had a fixed number of preset boards, so not every arrangement of mines was possible. (Also the board size in the current version is 9x9, while the old one was 8x8. Let's ignore the intermediate and expert levels for now - I assume those odds are nearly impossible, though a generalized solution that could solve for any W×H and mine-count would be cool too, but a lot more work I'd think.) In general, the increased board size (with the same number of mines), as well as the removal of the preset boards would both probably make such an event far more common.
So, assuming a 9x9 board with 10 mines, and assuming every possible arrangement of mines is equally likely (not true given the pseudo-random nature of computer random number generators, but let's pretend), and knowing that the first click is always safe (assume the described behavior on that site still holds - if you click on a mine in the first click, it's moved to the first available square in the upper-left corner), we'd need to first calculate the number of boards that are 1-click solvable. That is, boards with only one opening, and no numbered squares that are not adjacent to that opening. The total number of boards is easy enough: $\frac{(W×H)!}{((W×H)-M)! ×M!}$ or $\frac{81!}{71!×10!} \approx 1.878×10^{12}$. (Trickier is figuring out which boards are not one-click solvable unless you click on a mine and move it. We can maybe ignore the first-click-safe rule if it over-complicates things.) Valid arrangements would have all 10 mines either on the edges or far enough away from each other to avoid creating numbers which don't touch the opening. Then it's a simple matter of counting how many un-numbered spaces exist on each board and dividing by 81.
Is this a calculation that can reasonably be represented in a mathematical formula? Or would it make more sense to write a program to test every possible board configuration? (Unfortunately, the numbers we're dealing with get pretty close to the maximum value storable in a 64-bit integer, so overflow is very likely here. For example, the default Windows calculator completely borks the number unless you multiply by hand from 81 down to 72.)
$\endgroup$ 222 Answers
$\begingroup$We must ignore the "cannot lose on first click" rule as it severely complicates things.
In this answer, I will be using a notation similar to chess's FEN (Forsyth-Edwards Notation) to describe minesweeper boards. m is a mine and empty spaces are denoted by numbers. We start at the top of the board and move from left to right, returning to the left at the end of each row. To describe a specific square, the columns are numbered from a to h, left to right, and the rows are numbered from 8 to 1, top to bottom.
On a minesweeper board, all mines are adjacent to numbered squares that say how many mines are next to them (including diagonally). If there is ever a numbered square surrounded only by mines and other numbered squares, new squares will stop being revealed at that square. Therefore, the question is actually:
How many 9 × 9 minesweeper boards with 10 mines exist such that every blank square adjacent to a mine touches a square that is neither a mine nor adjacent to one?
I like to approach problems like these by placing mines down one by one. There are 81 squares to place the first mine. If we place it in a corner, say a1, then the three diagonal squares adjacent to the corner (in this case a3, b2, and c1) are no longer valid (either a2 or b1 is now "trapped"). If we place it on any edge square except the eight squares adjacent to the corners, the squares two horizontal or vertical spaces away become invalid. On edge squares adjacent to the corners (say b1) three squares also become unavailable. On centre squares, either 4 or 3 squares become unavailable.
The problem is that invalid squares can be fixed at any time. For example, placing mines first on a1 and then c1 may be initially invalid, but a mine on b1 solves that.
This is my preliminary analysis. I conclude that there is no way to calculate this number of boards without brute force. However, anyone with sufficient karma is welcome to improve this answer.
$\endgroup$ 5 $\begingroup$First i apologise for my bad english.
A simple rule to use and detect a one clickable grade is: "if every number have a 0 cell (or empty cell) adjacent to it, then, the grade is one clickable." That rule was easy to figure understanding how the automaticaly opens of a cell works. if the opened cell is a 0, then open all the adjecents cells.
This rule is very good for brute force algorithm to determine the favorable cases.
Besides that i tried to find the patterns that prevents one click win to happen in atempt to count the number of possibles grades that cant be win with one click. if you ignore the walls is simple, there are just two that englobe all of the others: B N B and B N N B (B for bomb, N for not bomb.) This N cells are traped becuse have just bombs or numbers adjecent to them and this kind of grades can't be one clickble, as the rule says.
There are the case when bombs make clusters of non openble cells too, without necessarly using the these labels.
But with walls things like non-bombs traps into corners and lines of bombs cross the board make thing a lot difficult. This cases dont necessarly need using BNB or BNNB patterns beacuse wall act like a block to empty cells opnenig domino's chain. So i stoped there.
Even if wee could figure out all paterns including the wall factor, we'll have another problem counting the possible combinations of patterns.. so i think is very hard, virtualy impossible without a pc to count these nunber of grades.
Thats my contribution. I hope that can be usefull
$\endgroup$ 2
