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 neighbors 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 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 of any examples of precedent to my approach, or avenues of potential exploration.

Answer 1

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.

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}]

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 are still some unknowns, with 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. I have implemented the following code in python, and it does not get terminated while the stack is depleted.

import stdio

import stdarray

import sys

import random

# Accept integers m and n, and float p as command-line arguments.

# Create a m x n minesweeper game where each cell is a bomb with

# probability p. Write the m x n game and the neighboring bomb counts

# to standard output.

m = int(sys.argv[1])

n = int(sys.argv[2])

p = float(sys.argv[3])

# Create bombs as a m+2 * n+2 array.

bombs = stdarray.create2D(m+2, n+2, False)

# bombs is [1..m][1..n]; the border is used to handle boundary cases.

for r in range(1, m+1):

for c in range(1, n+1):

bombs[r][c] = (random.random() < p)

# Write the bombs.

for r in range(1, m+1):

for c in range(1, n+1):

if bombs[r][c]:

stdio.write('* ')

else:

stdio.write('. ')

stdio.writeln()

# Create solution as m+2*n+2 array.

solution = stdarray.create2D(m+2, n+2, 0)

# solution[i][j] is the number of bombs adjacent to cell (i, j).

for r in range(1, m+1):

for c in range(1, n+1):

# (rr, cc) indexes neighboring cells.

for rr in range(r-1, r+2):

for cc in range(c-1, c+2):

 if bombs[rr][cc]:

 solution[r][c] += 1

# Write solution.

stdio.writeln()

for r in range(1, m+1):

for c in range(1, n+1):

if bombs[r][c]:

stdio.write('* ')

else:

stdio.write(str(solution[r][c]) + ' ')

 stdio.writeln()

If you want to make your career in Artificial Intelligence then go through this video: