编辑：这是一段时间之前的事情，我已经把它搞定了，如果你想看代码，请访问github.com/LewisGaul/minegaulerQt。
我正在尝试编写一个计算扫雷游戏概率的程序，并且在确定最佳结构方面遇到了一些困难。虽然从下面的示例开始看起来很简单，但我想知道允许更复杂配置的最佳方法。请注意，我不是在寻求如何计算概率的帮助 - 我知道方法，我只需要实现它！
为了清楚地说明我要计算什么，我将通过手动完成一个简单的示例来解释。考虑一个扫雷配置
# # # # # 1 2 # # # # #
其中“＃”表示未点击的单元格。“1”告诉我们，在最左边的7个未点击的单元格中恰好有1个地雷，“2”告诉我们，在最右边的7个未点击的单元格中恰好有2个地雷。为了计算每个单独单元格包含地雷的概率，我们需要确定所有不同的情况（在这种简单情况下仅有2种）：
1. 最左边的3个单元格中有1个地雷，最右边的3个单元格中有2个地雷（总共3个地雷，3x3=9种组合）。 2. 中心4个单元格中有1个地雷，在最右边的3个单元格中有1个地雷（总共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个）。我想听听你的想法。
我添加了一些其他类并进行了重构（请参见下面的工作代码），现在它可以创建和显示等价组，并朝着正确方向迈出了一步。但是，我仍然需要解决如何遍历所有可能的地雷配置的问题，方法是按一种方式分配给每个组一定数量的地雷，从而创建出一个有效的配置。感谢任何帮助。
我正在尝试编写一个计算扫雷游戏概率的程序，并且在确定最佳结构方面遇到了一些困难。虽然从下面的示例开始看起来很简单，但我想知道允许更复杂配置的最佳方法。请注意，我不是在寻求如何计算概率的帮助 - 我知道方法，我只需要实现它！
为了清楚地说明我要计算什么，我将通过手动完成一个简单的示例来解释。考虑一个扫雷配置
# # # # # 1 2 # # # # #
其中“＃”表示未点击的单元格。“1”告诉我们，在最左边的7个未点击的单元格中恰好有1个地雷，“2”告诉我们，在最右边的7个未点击的单元格中恰好有2个地雷。为了计算每个单独单元格包含地雷的概率，我们需要确定所有不同的情况（在这种简单情况下仅有2种）：
1. 最左边的3个单元格中有1个地雷，最右边的3个单元格中有2个地雷（总共3个地雷，3x3=9种组合）。 2. 中心4个单元格中有1个地雷，在最右边的3个单元格中有1个地雷（总共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