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.

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

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