Jump to content

  • Log In with Google      Sign In   
  • Create Account


Backward

Member Since 12 Apr 2013
Offline Last Active May 17 2013 04:04 AM

#5052442 A* applied to minesweeper game

Posted by Backward on 12 April 2013 - 08:25 AM

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?

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




PARTNERS