How to structure a program to work with minesweeper configurations

Question

EDIT: This was a while ago and I've since got it working, if you'd like to see the code it's included at github.com/LewisGaul/minegaulerQt.

I'm trying to write a program to calculate probabilities for the game minesweeper, and have had some difficulty working out how best to structure it. While it may seem quite simple at first with the example below, I would like to know the best way to allow for more complex configurations. Note I am not looking for help with how to calculate probabilities - I know the method, I just need to implement it!

To make it clear what I'm trying to calculate, I will work through a simple example which can be done by hand. Consider a minesweeper configuration
# # # #
# 1 2 #
# # # #
where # represents an unclicked cell. The 1 tells us there is exactly 1 mine in the leftmost 7 unclicked cells, the 2 tells us there are exactly 2 in the rightmost 7. To calculate the probability of each individual cell containing a mine, we need to determine all the different cases (only 2 in this simple case):

1. 1 mine in leftmost 3 cells, 2 mines in rightmost 3 cells (total of 3 mines, 3x3=9 combinations).

2. 1 mine in center 4 cells, 1 mine in rightmost 3 cells (total of 2 mines, 4x3=12 combinations).

Given the probability of a mine being in a random cell is about 0.2, it is (in a random selection of cells) about 4 times more likely there is a total of 2 mines rather than a total of 3, so the total number of mines in a configuration matters, as well as the number of combinations of each configuration. So in this case the probability of case 1 is 9/(9+4x12)=0.158, and the probability of there being a mine in a given leftmost cell is therefore about 0.158/3=0.05, as those cells are effectively equivalent (they share exactly the same revealed neighbours).

I have created a GUI with Tkinter which allows me to easily enter configurations such as the one in the example, which stores the grid as a numpy array. I then made a NumberGroup class which isolates each of the clicked/numbered cells, storing the number and a set of the coordinates of its unclicked neighbours. These can be subtracted to get equivalence groups... Although this would not be as straightforward if there were three or more numbers instead of just two. But I am unsure how to go from here to getting the different configurations. I toyed with making a Configuration class, but am not hugely familiar with how different classes should work together. See working code below (numpy required).

Note: I am aware I could have attempted to use a brute force approach, but if possible I would like to avoid that, keeping the equivalent groups separate (in the above example there are 3 equivalence groups, the leftmost 3, the middle 4, the rightmost 3). I would like to hear your thoughts on this.

import numpy as np

grid = np.array(
    [[0, 0, 0, 0],
     [0, 2, 1, 0],
     [0, 0, 0, 0]]
    )
dims = (3, 4) #Dimensions of the grid

class NumberGroup(object):
    def __init__(self, mines, coords, dims=None):
        """Takes a number of mines, and a set of coordinates."""
        if dims:
            self.dims = dims
        self.mines = mines
        self.coords = coords

    def __repr__(self):
        return "<Group of {} cells with {} mines>".format(
            len(self.coords), self.mines)

    def __str__(self):
        if hasattr(self, 'dims'):
            dims = self.dims
        else:
            dims = (max([c[0] for c in self.coords]) + 1,
                    max([c[1] for c in self.coords]) + 1)
        grid = np.zeros(dims, int)
        for coord in self.coords:
            grid[coord] = 1
        return str(grid).replace('0', '.').replace('1', '#')

    def __sub__(self, other):
        if type(other) is NumberGroup:
            return self.coords - other.coords
        elif type(other) is set:
            return self.coords - other.coords
        else:
            raise TypeError("Can only subtract a group or a set from another.")


def get_neighbours(coord, dims):
    x, y = coord
    row = [u for u in range(x-1, x+2) if u in range(dims[0])]
    col = [v for v in range(y-1, y+2) if v in range(dims[1])]
    return {(u, v) for u in row for v in col}

groups = []
all_coords = [(i, j) for i in range(dims[0])
    for j in range(dims[1])]
for coord, nr in [(c, grid[c]) for c in all_coords if grid[c] > 0]:
    empty_neighbours = {c for c in get_neighbours(coord, dims)
        if grid[c] == 0}
    if nr > len(empty_neighbours):
        print "Error: number {} in cell {} is too high.".format(nr, coord)
        break
    groups.append(NumberGroup(nr, empty_neighbours, dims))
print groups
for g in groups:
    print g
print groups[0] - groups[1]

UPDATE:
I have added a couple of other classes and restructured a bit (see below for working code), and it is now capable of creating and displaying the equivalence groups, which is a step in the right direction. However I still need to work out how to iterate through all the possible mine-configurations, by assigning a number of mines to each group in a way that creates a valid configuration. Any help is appreciated.

For example,
# # # #
# 2 1 #
# # # #
There are three equivalence groups G1: the left 3, G2: the middle 4, G3: the right 3. I want the code to loop through, assigning groups with mines in the following way:

• G1=2 (max the first group) => G2=0 => G3=1 (this is all configs with G1=2)
• G1=1 (decrease by one) => G2=1 => G3=0 (this is all with G1=1)
• G1=0 => G2=2 INVALID

So we arrive at both configurations. This needs to work for more complicated setups!

import numpy as np

def get_neighbours(coord, dims):
    x, y = coord
    row = [u for u in range(x-1, x+2) if u in range(dims[0])]
    col = [v for v in range(y-1, y+2) if v in range(dims[1])]
    return {(u, v) for u in row for v in col}

class NrConfig(object):
    def __init__(self, grid):
        self.grid = grid
        self.dims = grid.shape # Dimensions of grid
        self.all_coords = [(i, j) for i in range(self.dims[0])
            for j in range(self.dims[1])]
        self.numbers = dict()
        self.groups = []
        self.configs = []
        self.get_numbers()
        self.get_groups()
        self.get_configs()

    def __str__(self):
        return str(self.grid).replace('0', '.')

    def get_numbers(self):
        for coord, nr in [(c, self.grid[c]) for c in self.all_coords
            if self.grid[c] > 0]:
            empty_neighbours = {c for c in get_neighbours(
                coord, self.dims) if self.grid[c] == 0}
            if nr > len(empty_neighbours):
                print "Error: number {} in cell {} is too high.".format(
                    nr, coord)
                return
            self.numbers[coord] = Number(nr, coord, empty_neighbours,
                self.dims)

    def get_groups(self):
        coord_neighbours = dict()
        for coord in [c for c in self.all_coords if self.grid[c] == 0]:
            # Must be a set so that order doesn't matter!
            coord_neighbours[coord] = {self.numbers[c] for c in
                get_neighbours(coord, self.dims) if c in self.numbers}
        while coord_neighbours:
            coord, neighbours = coord_neighbours.popitem()
            equiv_coords = [coord] + [c for c, ns in coord_neighbours.items()
                if ns == neighbours]
            for c in equiv_coords:
                if c in coord_neighbours:
                    del(coord_neighbours[c])
            self.groups.append(EquivGroup(equiv_coords, neighbours, self.dims))

    def get_configs(self):
        pass # WHAT GOES HERE?!


class Number(object):
    """Contains information about the group of cells around a number."""
    def __init__(self, nr, coord, neighbours, dims):
        """Takes a number of mines, and a set of coordinates."""
        self.nr = nr
        self.coord = coord
        # A list of the available neighbouring cells' coords.
        self.neighbours = neighbours
        self.dims = dims

    def __repr__(self):
        return "<Number {} with {} empty neighbours>".format(
            int(self), len(self.neighbours))

    def __str__(self):
        grid = np.zeros(self.dims, int)
        grid[self.coord] = int(self)
        for coord in self.neighbours:
            grid[coord] = 9
        return str(grid).replace('0', '.').replace('9', '#')

    def __int__(self):
        return self.nr


class EquivGroup(object):
    """A group of cells which are effectively equivalent."""
    def __init__(self, coords, nrs, dims):
        self.coords = coords
        # A list of the neighbouring Number objects.
        self.nr_neighbours = nrs
        self.dims = dims
        if self.nr_neighbours:
            self.max_mines = min(len(self.coords),
                max(map(int, self.nr_neighbours)))
        else:
            self.max_mines = len(coords)

    def __repr__(self):
        return "<Equivalence group containing {} cells>".format(
            len(self.coords))

    def __str__(self):
        grid = np.zeros(self.dims, int)
        for coord in self.coords:
            grid[coord] = 9
        for number in self.nr_neighbours:
            grid[number.coord] = int(number)
        return str(grid).replace('0', '.').replace('9', '#')


grid = np.array(
    [[0, 0, 0, 0],
     [0, 2, 1, 0],
     [0, 0, 0, 0]]
    )
config = NrConfig(grid)
print config
print "Number groups:"
for n in config.numbers.values():
    print n
print "Equivalence groups:"
for g in config.groups:
    print g

Answer 1

If you don't want to brute-force it, you could model the process as a decision tree. Suppose we start with your example:

####
#21#
####

If we want to start placing mines in a valid configuration, we at this point essentially have eight choices. Since it doesn't really matter which square we pick within an equivalence group, we can narrow that down to three choices. The tree branches. Let's go down one branch:

*###
#11#
####

I placed a mine in G1, indicated by the asterisk. Also, I've updated the numbers (just one number in this case) associated with this equivalence group, to indicate that these numbered squares can now border one fewer mines.

This hasn't reduced our freedom of choice for the following step, we can still place a mine in any of the equivalence groups. Let's place another one in G1:

*XX#
*01#
XXX#

Another asterisk marks the new mine, and the numbered square has again been lowered by one. It has now reached zero, meaning it cannot border any more mines. That means that for our next choice of mine placement, all the equivalence groups dependent upon this numbered square are ruled out. Xs mark squares where we can now not place any mine. We can only make one choice now:

*XX*
*00X
XXXX

Here the branch ends and you've found a valid configuration. By running along all the branches in this tree in this manner, you should find all of them. Here we found your first configuration. Of course, there's more than one way to get there. If we had started by placing a mine in G3, we would have been forced to place the other two in G1. That branch leads to the same configuration, so you should check for duplicates. I don't see a way to avoid this redundancy right now.

The second configuration is found by either starting with G2, or placing one mine in G1 and then the second in G2. In either case you again end up at a branch end:

**XX
X00X
XXXX

Invalid configurations like your example with zero mines in G1 do not pop up. There are no valid choices along the tree that lead you there. Here is the whole tree of valid choices.

Choice 1:        1     |     2     |     3
Choice 2:    1   2   3 | 1         | 1   
Choice 3:     3     1  |           |1

Valid configurations are the branch ends at which no further choice is possible, i.e.

113
12
131
21
311

which obviously fall into two equivalent classes if we disregard the order of the numbers.