Minesweeper solving algorithm [closed]

Question

I am pretty sure most of you know about the minesweeper game. I wanted to code (in C#) my own minesweeper game and was looking for some input as to what would be a good algorithm for that game? I have been browsing over the web for quite some time now but could not find a good solution.

Atahualpa

A "good algorithm"? For what? – Atonic

If you want to create a game (rather than a solver), why do you need an algorithm? Just place X mines at random positions on a YxZ field... – Imelda

I think that he meant something like "a good design" instead. – Dread

An algorithm...for what? Mine placement? – Malvern

The minesweeper game is pure logic, not some hard coded foobar! – Maud

Answer 1

Generating the grid is simple. There are a couple simple algorithms that you need when executing the player's move, to determine which squares to open up and whether they have lost or won.

Generating the grid

The simplest algorithm is to place all of the mines randomly. (Make sure you don't overlap them!)

Problem: The player's first click might be a mine.

Improvement: Delay the generation of the grid until the user clicks on the first square, and don't put any mines in that square.

Problem: The player's first click might reveal a non-zero number, and they will be forced to click randomly until something opens up.

Improvement: Don't generate any mines in the (up to) eight squares around the first click, either.

Problem: The player might be forced to guess at some point, making this a sad excuse for a logic puzzle.

Improvement: Run the solver alongside the generator, making sure that the puzzle has a unique solution. This takes some cleverness, and isn't done in most variants.

Another, less common way to resolve ambiguities is to detect when the player knows they are choosing between equally likely possibilities and "collapse the waveform" into the position they decided on. I have never seen this in action, but it would be kind of fun.

Playing the game

Besides marking flags, the player can make two kinds of moves to attempt to uncover squares:

• Single guess: The player clicks on a square with unknown state and no flag. Reveal the square, see if the player died, and put a number in it. If the square contains a 0, repeat this recursively for all the surrounding squares. This should be in a dedicated function, to separate it from the GUI's event handler, to make the recursion easy, and because it's reused in the multiguess.

• Multiguess: The player clicks on a square that is uncovered and known to be safe. If the number of flags surrounding equals the number in this square, we open up the unflagged squares using the same procedure as above.

Winning the game

If the number of squares that are covered up is the same as the number of mines, then the player has won, even if they haven't placed a flag on every square.

When the player loses, it is customary to mark any incorrect guesses that they made, the remaining mines, and the mine that they stepped on.

Garneau

You've clearly thought out minesweeper implementation more than I have, but the OP wanted a solver, I think. – Blastocoel

Checks the comments I see. Still, having seen a couple minesweeper variants that didn't implement everything, I thought it worth being thorough. – Garneau

A solution to Problem 1: "The player's first click might be a mine." that allows you to generate the grid ahead of time: Layout the grid with an extra mine. If the first click is on a mine, just eliminate that mine and everything is in place to proceed. If the first click is NOT on a mine, select a mine that is a fair distance away and eliminate that one. Possibly the easiest is to starts the board with N+1 mines, and insure there is 1 mine at or near each of 2 opposing corners. If the first click is NOT on a mine, eliminate the mine in the corner furthest away from where they clicked. ---> – Highkey

--> The second part is actually not necessary, but it would allow you to pre-compute the grid layout with and without the mine so you could make the adjustment quickly if necessary. – Highkey

Answer 2

I just want to add the following if you try to write a solver - Minesweeper is NP complete (Archive Link). That means until someone proves P = NP it might be possible that you can do nothing better then performing a brute force search in some situations (but maybe the game it is not NP complete for small fields).

Formal

claymath link broken – Sequence

NP does not mean brute force. – Roughhouse

@Shadow, example? – Indevout

@Indevout you may have heuristic solutions which are much faster than brute force. – Roughhouse

Answer 3

As Henri mentioned, the correct way of solving minesweeper is with mathematics, specifically Linear Algebra Matrix mathematics for the deterministic part. I have a whole post here that:

• explains how that method works
• has working code that you can compile and run on any platform
• contains the code to make the game and a solver too

You can see that all here: https://massaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/

I would recommend reading through that and then having a good thought about it. The probabilistic part of Minsweeper can be solved using statistics too but I don't have a good plan for that yet. However, other people have looked into it too.

Han

Answer 4

I'm definitely not a minesweeper expert, but here's the algorithm I use when I try to solve it:

Go over all the squares that are the border of the revealed area. For each of these squares, count the number of mines you have revealed next to it. subtract the number that is written in the square (the true number of mines that are around it). That is the number of unrevealed mines left around this square. Divide that by the number of unrevealed squares around the current square. That is the probability of each of the adjacent square containing a mine. If any square has a probability of 1, you mark it as a mine. If any square has a probability of 0 you mark it as safe. Then you update the relevant numbers.

What do you do if no square has probability 0 or 1? An optimal algorithm would take into consideration constraints from multiple squares. But as a I wrote in the begining, I'm not a minesweeper expert, so I choose randomly from the other squares that has probability closest to 0 or to 1.

Guaco

Answer 5

Here is my minesweeper solver:

• for each number squares:
  • if count of unopened around == square number: all of them are mines
  • if square number - count of flagged around == 0: all of the unopened are not mines
• use subset rule

Here is an actual implementation, notice it used the subset rule, which is harder to explain https://github.com/SHiNKiROU/Minesweeper/blob/master/src/org/shinkirou/minesweeper/MinesweeperSolver.java#L27

Of course, my algorithm can fail sometimes. I'm planning to implement a Prolog-style backtracking solver

Vercelli

Answer 6

The comments are that you don't need an algorithm to build the game. I believe you mean an algorithm in the sense of solving and everyone might be understanding it that way as well.

However any solution to a problem can be considered an algorithm.

Like most math problems you can dissect the whole algorithm into smaller less complex algorithms, until you get down to something small enough to solve. This will get you the first correct solution. Later you can optimize the smaller algorithms in the context of the whole algorithm.

The gameboard can be thought of as a 2 dimensional array. You will have an algorithm associated with each operation. The first operation would probably be a randomly generated set of mine locations with x, y coordinates with a parameter of the number of mines and size of board. You would have another algorithm associated with revealing a square, which takes the board and a location and determines how many mines are adjacent to it. The final algorithm would take the board and check if any squares without mines are left to reveal.

Now you can take each of these algorithms and attempt to optimize each of them for better performance and say "what's the best way to count the squares with mines adjacent to a current square, given a 2 dimensional array using x,y coordinates.

Auden

Answer 7

Check this: http://quantum-p.livejournal.com/19616.html

Any position on the board, that cant be solved intuitively with the monkey-reasoning is a matrix that could be able to solve some individual(or the whole position) squares which can lead to better solving rates. Simple random guessing didn't produce good results. I implemented this method into my solving algorithm in C++ by adding a linear system of equations-solver. I am researching the difficulcy of Minesweeper by running tens of thousands games through the algorithm and doing statistics.

My algorithm solves upto 85% of (9,9,10) easy level minesweepers. I haven't yet ran complete tests on other difficulcy levels, but smaller tests suggest that medium level (16,16,40) has a solving rate of 55-60 % and Hard level(30,16,99) as low as 5-10%. I am going to add a few new things that would make it most optimal.

Mudpack

Answer 8

Have you seen this C# implementation of the game? The source code is downloadable, and the object model is explained.

Dread