Menu
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.
522
Early algorithms developed to solve Minesweeper focus on the deterministic deductions needed to uncover safe moves. Adamatzky modeled Minesweeper as a cellular automaton or CA [3]. The cell state is given two components. The first component indicates whether the cell is either covered, uncovered, or a mine.
In games such as Go and Minesweeper, flood fill is used to determine which pieces are cleared. Flood fill is usually implemented as a recursive algorithm which makes four recursive calls.
A simple trick is to press both buttons ("chord") on a number to depress (but not open) the squares it touches. This shows you how many squares are touching the number. The pink 2 touches three squares and cannot be solved. The yellow 2 touches two squares and can be solved.
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.
137
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
