Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)

share|improve this question
2  
About the program: I doubt a monte carlo would work well at all. Between the board generation and the 1-click win checking, it would take an reasonably long time to even get a sample average on the order of $1$ in $80000$, much less an accurate estimate. This is a job for combinatorics, not simulation. –  Alexander Gruber Jun 20 '13 at 1:31
    
Yeah, I'd thought about optimizations, like not wasting time on rotations and reflections of the same board pattern. You could also easily take care of several sets of boards, like all combinations with every mine on the edge either touching eachother or separated by 3 or more spaces. You can also rule out sets, like any mine being exactly 1 row or column from the edge (unless there's another mine in between). It may be that some intelligent combination of math and simulation might still be viable. –  Darrel Hoffman Jun 20 '13 at 3:29
    
It's occurred to me that there are similarities between this and the en.wikipedia.org/wiki/Eight_queens_puzzle –  Darrel Hoffman Jun 20 '13 at 3:39
    
I don't think your total number of boards is right. First of all you probably mean to divide instead of subtract. Secondly, you seem to choose the number of ways of placing the first mine, then the second, then... but of course the order in which you place the mines doesn't matter, so you want to divide by $10!$ (the number of possible orderings). The number that results is 1,878,392,407,320. –  Ben Millwood Jun 28 '13 at 18:10
    
@BenMillwood Yeah, I just looked at that again. I think it's correct now. Still a lot of possibilities to go through, but 6 orders of magnitude less, might actually be feasible to run a simulation with these numbers? –  Darrel Hoffman Jun 28 '13 at 21:04

1 Answer 1

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.

share|improve this answer
    
I think user83704's suggestion in the comments above was closer to the mark - start with a fully connected graph, and see if it's still connected after all mines have been placed. It'd be easier to brute-force if we could determine how many possible boards there are when you take rotations and reflections into account. (For every asymmetrical board, you divide the number by 8, so that's a pretty major chunk.) –  Darrel Hoffman Jul 11 '13 at 2:44
    
@DarrelHoffman Did you downvote this? –  Lee Sleek Jul 11 '13 at 16:43
    
Wasn't me. I haven't voted at all, since it isn't a complete answer yet. –  Darrel Hoffman Jul 11 '13 at 16:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.