Improving my Minesweeper solving algorithm

Question

I have implemented in Python an algorithm for solving the game 'Minesweeper'. The program works as follows:

Say that the solver clicks a square named 'a'. For sake of example let the number thus revealed equal 2. The neighbours of the square which are as yet unclicked are (again by way of example) named 'b' and 'c'. The program then associates the square with the expression [2, {'b', 'c'}], and strips 'a' from all other expressions. The deduction of which squares are mines and which are not proceeds by pairwise simplification of such expressions under two circumstances.

• If the squares in one expression are a subset of the squares of the other expression:

  [2, {'a', 'b', 'c'}], [1, {'a', 'b'}] -> [1, {'c'}], [1, {'a', 'b'}]
  

• If all the squares in one expression are established to be mines:

  [2, {'a', 'b'}], [1, {'b', 'c'}] -> [2, {'a', 'b'}], [0, {'c'}]
  

Then, for some expression X, if X[0] == 0, we are free to click all squares named in X[1], and if X[0] == len(X[1]), then we can flag them.

I am, however, struggling to identify which pairs of expressions to attempt to simplify. My current approach is to maintain a stack of squares; whenever a square is clicked, or has its expression successfully simplified, it is added to the stack (if it is not already there). When a square is popped from the stack, simplification is attempted between its expression (X), and any other expressions Y such that X[1] & Y[1] != set(). The algorithm terminates when the stack is depleted. Currently however, though this works quite well, it is not capable of correctly solving all unambiguous configurations, and how well it performs on a given board changes significantly if I replace the stack with a queue, or use some algorithm to determine which square to pop!

I would be very much appreciative for any examples of precedent to my approach, or avenues of potential exploration.

Broomfield

Do a, b, c refer to potential mines, or just neighboring squares, such that you start off with a reference to each of the 8 neighbors and slowly whittle away what's safe and what's dangerous? – Instructive

You start (as explained in the second paragraph) with a reference to each of the neighbours which is not clicked as of the time when the expression is generated (the square to which the expression belongs is clicked). – Broomfield

Answer 1

Several years ago I wrote a Minesweeper solver, but alas I seem to have lost the code since then. What I remember is that it was a brute-force method, which compiled sets of potential mines, rather than leaving the combinations packed up like you are doing.

I believe it was a bit more capable that the algorithm you're working with. Your approach can "solve" a condition if it is completely full or empty of mines, or if it is a subset of another condition. However, there are some deductions that this won't handle. For instance, consider this small 7x2 board, where the a through h tiles are unknown:

a 2 1 2 1 2 i
b c d e f g h 

Your conditions will be:

[2, {a, b, c, d}],
[1, {c, d, e}],
[2, {d, e, f}],
[1, {e, f, g}],
[2, {f, g, h, i}]

If I've understood it correctly, your algorithm can't make any deductions about this. However, if you're an experienced Minesweeper player, you'll recognize that the 1 2 1 pattern in the center has only a single solution, with mines below the 1s:

a 2 1 2 1 2 i
b 2 * 2 * 2 h

There's still some unknowns, with a mine under a or b and another under h or i, but if this was part of a larger puzzle you might be able to figure those out later on (or you may have to guess).

I believe my set of mines approach worked like this:

For each tile that has been expanded, collect one set of all its unexpanded neighbors (the "area"), and a list containing all the sets of mines that could occur in that area. So for instance, the 5 known tiles in the example above would generate (from left to right):

 ({a, b, c, d}, [{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}])
 ({c, d, e}, [{c}, {d}, {e}])
 ({d, e, f}, [{d, e}, {d, f}, {e, f}])
 ({e, f, g}, [{e}, {f}, {g}])
 ({f, g, h, i}, [{f, g}, {f, h}, {f, i}, {g, h}, {g, i}, {h, i}])

Anyway, to combine two conditions I'd first check that they were overlapping, by intersecting the area sets. If there was no overlap, the conditions can't be usefully combined.

If there was an overlap though, the new condition would span the union of their areas. As for the sets of mines, I'd do an Cartesian product of the outer sets to get pairs of inner sets, then check if the there was a contradiction. A contradiction would be if, within the intersection of the areas, the two sets didn't have exactly the same mines. If there was no contradiction, a new combined set would be formed from the union of the mine locations. Here's how the first two rows above would combine:

 Intersection of areas: {a, b, c, d} & {c, d, e} = {c, d}
 New combined area: {a, b, c, d} | {c, d, e} = {a, b, c, d, e}
 Cartesian product of mine sets (with X marking contradictions):
    |   {a, b}  {a, c}  {a, d}  {b, c}  {b, d}  {c, d}
 ---+-------------------------------------------------
 {c}|     X     {a, c}    X     {b, c}    X       X
 {d}|     X       X     {a, d}    X     {b, d}    X
 {e}| {a, b, e}   X       X       X       X       X

 New condition: ({a, b, c, d, e}, [{a, b, e}, {a, c}, {b, c}, {a, d}, {b, d}])

You can calculate the odds of any tile within the condition's area being a mine by simply counting how many of the sets it is part of, relative to how many sets there are total. So given the combined condition above, you could figure that a is a mine 3/5ths of the time, whereas e is only 1/5th of the time. This information is important for when the program needs to guess a location to expand when there are not any guaranteed-safe tiles. I think I also did some complicated combinatorics to account for the number of mines used (so that the {a, b, e} case above would be weighted a bit differently than the other cases, since it uses three mines rather than two), but I'm afraid I don't remember the details.

Minesweeper is a pretty challenging game. I believe my program was able to solve boards equivalent to the "Hard" difficulty about 50-60% of the time, with most of the losses happening either near the beginning (when you must guess with little information to work from) or right at the end (when there are often a few unsolvable areas that need to be guessed at). It was usually pretty fast, though occasionally there would be a pattern of tiles that caused it to bog down for 10 or 15 seconds before making its next move. (Minesweeper is NP-complete, so it is not surprising that some inputs can't be solved quickly!)

Toil

Answer 2

This is what jumped to mind, I was not fully able to visualize what your method was exactly.
I hope that presenting mine in graphical form will help save you that effort.

The images proceed in "reading order".

It seems to fit with the work I have done since posting this that adding to the value given to an unknown tile the number of known tiles that it is gaining it's temp value from could further increase the likelihood of correctly modeling risk.
(using this, a temp value of 16 (or 8 with the first method) is significant as it is the number one mine can achieve by itself)

---

I feel a little blind for not seeing this sooner.

Anything with a value that normalizes to 100% is in all cases I can find, a mine.

Vietcong