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?



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 end of current shortest path and depending on heuristic function algorithm will choose next field that needs to be opened.

I don't see why you need A* for this... is it really a graph search?

And click the square above the 2 next to the 2 flags... it's safe ;) EDIT: As are all the uncovered squares next to the 1s

EDIT2: I'm guessing you need to know HOW to identify those spaces as flagged... I still don't see how it involves A* though... you can probably just brute-force it, or encode in some simple rules for cases like that... The problem arises when you have to guess - you need to assign probabilities for each selection and pick the most safe option.

What now? I am using A* because i have to find the shortest path to find all mined fields. When i find all mined fields algorithm is finished. Shortest path in this case means to find all mined fields but to open minimal number of fields.

I'm not sure if you can use A* since there is hidden information. What is the heuristic?

I still didn't think about heuristic. For now i want to complete this part about finding all possible safe fields.

Well, I'd suggest looking at the places with only 1 safe spot first (i.e. N-1 mines for N unknown spaces), starting with the smallest N (so the 2 in the picture next to 1s would fit the bill). Then you can examine all the combinations (there are N of them) looking for a contradiction.

After that it sounds like it is going to be a recursive problem... have you done any googling?

Don't assume A* is your answer. A* is essentially Dijkstra's algorithm with a heuristic applied, and if you don't have a good heuristic to use, then skip it and just use Dijkstra's. But even here, Dijkstra's isn't really what you want, because you don't really want a graph search for an optimal path.

Minesweeper is NP-Complete, so you're not going to solve it with any polynomial time algorithm (assuming P != NP) (both A* and Dijkstra's are polynomial time algorithms, and as such are not powerful enough to solve this problem).

Presumably the OP wants to find a way to solve minesweeper using the least number of clicks. I think that is going to be a hard problem, unless you already know the locations of all the mines, then you could graph search it, but that isn't how the game is played... (EDIT: The game also cheats for you on the first move, it is never a mine... presumably it moves the mine elsewhere in that case - on Windows anyway).

You can get a situation where you have to make a guess, in that case you need to work out the guess least likely to reveal a mine but that is a probability question rather than a graph search one. Sometimes you end up with a 50-50 win/lose choice though... so it can be just a coin flip.

There are some rules for that what you said. I have to make this for my homework but there are 2 rules:

1) I will get already opened minefield at start

2) Those test cases will be made without a need to guess anything. So i am sure there won't be 50/50 cases. I will always be able to find safe fields.

There's a big difference between "opened minefield" and "locations of all mines known at the start"... if you don't know the locations of ALL the mines (i.e. you have missing information) I can't see a way to use a graph search...

Every click removes exactly 1 blank space unless there are no adjacent mines (when it does a flood fill of all 0 neighbouring mine squares)... but there is no way to know which squares will be 0s in advance...