python - 如何构建程序以使用扫雷艇配置

Question

编辑:这是前一段时间，我已经开始工作了，如果您想查看它包含在 github.com/LewisGaul/minegaulerQt 中的代码.

我正在尝试编写一个程序来计算游戏扫雷的概率，并且在确定如何最好地构建它时遇到了一些困难。虽然在下面的示例中乍一看似乎很简单，但我想知道允许更复杂配置的最佳方法。注意我不是在寻求关于如何计算概率的帮助——我知道这个方法，我只需要实现它!

为了明确我要计算的内容，我将通过一个可以手动完成的简单示例进行工作。考虑一个扫雷艇配置# # # ## 1 2 ## # # #哪里#表示未单击的单元格。 1告诉我们在最左边的 7 个未点击的单元格中正好有 1 个地雷，即 2告诉我们最右边的 7 个中正好有 2 个。要计算每个单元格包含地雷的概率，我们需要 确定所有不同的情况 (在这个简单的情况下只有 2 个):

最左边的 3 个格子里有 1 个地雷，最右边的 3 个格子里有 2 个地雷(总共 3 个地雷，3x3=9 组合)。

1 个地雷在中心 4 个单元格中，1 个地雷在最右边的 3 个单元格中(总共 2 个地雷，4x3=12 组合)。

鉴于地雷在随机单元格中的概率约为 0.2，因此(在随机选择的单元格中)总共有 2 个地雷而不是总共 3 个地雷的可能性大约是其 4 倍，因此 配置中的地雷总数以及每个配置的组合数量很重要 .因此，在这种情况下，情况 1 的概率为 9/(9+4x12)=0.158，因此在给定的最左侧单元格中存在地雷的概率约为 0.158/3=0.05，因为这些单元格实际上是等效的(它们共享完全相同的显示邻居)。

我使用 Tkinter 创建了一个 GUI，它允许我轻松输入配置，例如示例中的配置，它将网格存储为 numpy 数组。然后我做了一个 NumberGroup隔离每个单击/编号单元格的类，存储编号和其未单击邻居的一组坐标。可以减去这些以获得等价组......尽管如果有三个或更多数字而不是两个数字，这将不会那么简单。但是 我不确定如何从这里获得不同的配置 .我玩弄了一个 Configuration类，但我不太熟悉不同的类应该如何协同工作。请参阅下面的工作代码(需要 numpy)。

注意:我知道我可以尝试使用蛮力方法，但如果可能的话，我想避免这种情况，将等效组分开(在上面的示例中，有 3 个等效组，最左边的 3 个，中间的 4 个，最右边的 3)。我想听听您对此的看法。

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]

更新:
我添加了几个其他类并进行了一些重组(参见下面的工作代码)，现在它能够创建和显示等价组，这是朝着正确方向迈出的一步。但是，我仍然需要通过以创建有效配置的方式将多个地雷分配给每个组来解决如何迭代所有可能的地雷配置。任何帮助表示赞赏。

例如， # # # # # 2 1 # # # # #有三个等价组 G1:左侧 3，G2:中间 4，G3:右侧 3。我希望代码循环遍历，按以下方式分配带有地雷的组:

G1=2(最大第一组)=> G2=0 => G3=1(这是 G1=2 的所有配置)

G1=1(减一)=> G2=1 => G3=0(G1=1 都是这样)

G1=0 => G2=2 无效

所以我们得出了两种配置。这需要适用于更复杂的设置!

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

如果您不想对其进行暴力破解，您可以将流程建模为决策树。假设我们从你的例子开始:

####
#21#
####

如果我们想开始在有效配置中放置地雷，此时我们基本上有八种选择。由于我们在等价组中选择哪个方格并不重要，因此我们可以将其缩小到三个选项。 Twig 。让我们走下一个分支:

*###
#11#
####

我在 G1 中放置了一个地雷，用星号表示。此外，我还更新了与该等价组关联的数字(在本例中只有一个数字)，以表明这些带编号的方块现在可以少接一个地雷。

这并没有减少我们对下一步的选择自由，我们仍然可以在任何等价组中放置一个地雷。让我们在 G1 中再放置一个:

*XX#
*01#
XXX#

另一个星号标志着新矿，编号的方块再次降低了一个。它现在已经达到零，这意味着它不能再与任何地雷接壤。这意味着对于我们的下一个地雷放置选择，所有依赖于这个编号方块的等价组都被排除在外。 X s 标记我们现在不能放置任何地雷的方块。我们现在只能做一个选择:

*XX*
*00X
XXXX

到这里分支结束，你已经找到了一个有效的配置。通过以这种方式沿着这棵树中的所有分支运行，您应该找到所有分支。在这里，我们找到了您的第一个配置。当然，到达那里的方法不止一种。如果我们开始在 G3 中放置一个地雷，我们将不得不将另外两个放置在 G1 中。该分支导致相同的配置，因此您应该检查重复项。我现在看不到避免这种冗余的方法。

第二种配置是从 G2 开始，或者在 G1 中放置一个地雷，然后在 G2 中放置第二个。在任何一种情况下，您都会再次到达分支末端:

**XX
X00X
XXXX

像您在 G1 中的零地雷示例这样的无效配置不会弹出。沿着树没有有效的选择可以引导您到达那里。这是有效选择的整个树。

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

有效配置是无法进一步选择的分支末端，即

113
12
131
21
311

如果我们不考虑数字的顺序，这显然分为两个等价的类别。