Algorithmic solution to Minesweeper
algorithm, minesweeper
Solution
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.
Problem
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.