Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


Backward

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

Topics I've Started

A* applied to minesweeper game

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