Algorithmic solution to Minesweeper

Question

I am trying to make the minesweeper solver. As you know there are 2 ways to determine which fields in minefield are safe to open, or to determine which fields are mined and you need to flag it. First way to determine is trivial and we have something like this:

if (number of mines around X – current number of discovered mines around X) = number of unopened fields around X then All unopened fields around X are mined

if (number of mines around X == current number of discovered mines around X) then All unopened fields around X are NOT mined

But my question is: What about situation when we can't find any mined or safe field and we need to look at more than 1 field?

http://img541.imageshack.us/img541/4339/10299095.png

For example this situation. We can't determine anything using previous method. So i need a help with algorithm for these cases.

I have to use A* algorithm to make this. That is why i need all possible safe states for next step in algorithm. When i find all possible safe states i will add them to the current shortest path and depending on heuristic function i will sort list of paths and choose next field that needs to be opened.

Chape

You could avoid writing the algorithm and let the computer learn by itself, but I can't tell you any futher.. :/ – Panpipe

I don't understand the example image you provide. The leftmost "2" suggests both the fields in the second row on the left are mined, but the second "2" suggests only one of them is. In what game context would this arise? Are you imagining that the game's information might be contradictory? – Mammillate

But you can find a safe field in that image, using your algorithm. Take the 2 surrounded by the two ones; the number of mines around the two equals the current number of discovered mines around the two. So you may uncover the blank field above it. Or, do you mean, if you had that field with no flags yet marked, how would you know to mark those two flags? – Lashawna

There are more unopened fields on left and right side. Add one column with unopened fields on left and one on right side and you will understand. – Chape

I don't think you'll find a small set of rules to cover every situation, because the set of covered tiles that border an uncovered tile intersects with the set of tiles bordered by the next uncovered tile, and so on. You might have to reason through a long chain of overlapping tiles in order to make the right moves without guessing. In general, this is a job for a constraint solver, which is not trivial to implement from scratch. – Freestone

Anecdotally, long ago I wrote a Minesweeper solver, IIRC with only the two rules the OP describes. It could solve Expert-level fields on its own about 10% of the time. So if you're merely trying to establish an unbeatable best time, and you have unlimited tries, then the simple approach may be good enough. – Lashawna

OP: When you discover any safe move, make it immediately. Why do you want to discover all safe moves and then use A* to choose? – Greenwell

Because i need shortest path to find all mines. And A* finds all possible extensions of existing path and decide who is currently the best solution to continue. – Chape

Answer 1

Awesome problem, before you get too excited though, please read NP Completeness and Minesweeper, as well as the accompanying presentation which develops some good worst case examples and how a human might solve them. Nevertheless, in expectation we most likely won't hit a time barrier, if we use basic pruning and heuristics.

The question of generating the game is asked here: Minesweeper solving algorithm. There is a very cool post on algebraic methods. You can also give backtracking a try (i.e. take a guess and see if that invalidates things), similar to the case where local information is not enough for something like sudoku. See this great discussion about this technique.

Kulp

If you are allowed to back up from your mistakes, then you could just uncover every square once, and keep track of which squares have mines. I think maybe the OP is looking for a solver that follows the same rules as a human - namely that you fail if you make one wrong move. – Freestone

Yes, of course, use backtracking when all else fails otherwise clearly the tree grows exponentially. – Kulp

But how can you backtrack without uncovering a mine and losing the game? – Freestone

Sorry, let me clarify. Backtracking means pretending to click a square (this will not reveal any new squares of course since it is hypothetical). Now think about how the values on other squares change, assuming what you clicked was not a mine. If there is a square that becomes < 1, then clearly there is a contradiction in the configuration, and the current configuration is not possible, so there must have been a mine somewhere along the path of hypothetically clicked squares. – Kulp

My fault - I see what you are saying now. – Freestone

Answer 2

As @tigger said this is not a problem that can be solved with a simple set of rules. Minesweeper is a good example where backtracking algorithms such as DPLL is useful. With something as simple as propositional logic, you can implement a very efficient solver for minesweeper. I am not sure if you are familiar with AI reasoning & logic inference - If not, you might want to have a look at the book "Artificial Intelligence - A Modern Approach" by Stuart Russel and Peter Norvig. For quick reference of DPLL and propositional logic, search "wumpus world propositional logic" on Google.

Dive