Siw*_*wel 12 python probability minesweeper
编辑:这是一段时间以前,我已经开始工作,如果你想看到它包含在github.com/LewisGaul/minegaulerQt的代码.
我正在尝试编写一个程序来计算游戏扫雷的概率,并且在如何最好地构建它时遇到了一些困难.虽然首先使用下面的示例看起来很简单,但我想知道允许更复杂配置的最佳方法.注意我不是在寻找有关如何计算概率的帮助 - 我知道方法,我只需要实现它!
为了清楚我想要计算的内容,我将通过一个简单的例子来完成,这个例子可以手工完成.考虑扫雷配置
# # # #
# 1 2 #
# # # #
,其中#表示未被单击的单元格.该1告诉我们有在最左边的7个未点击的细胞正好1矿山,2告诉我们恰好有2在最右边7.要计算含矿每个单独的小区的概率,我们需要确定所有不同的情况下(仅2在这个简单的情况下):
在最左边3个细胞中有1个矿井,在最右边3个细胞中有2个矿井(总共3个矿井,3x3 = 9个组合).
中心4个单元中的1个矿井,最右边3个单元中的1个矿井(总共2个矿井,4x3 = 12个组合).
鉴于矿井在随机单元格中的概率约为0.2,它(在随机选择的单元格中)总共2个地雷的可能性大约是4倍,而不是总共3个,所以地雷总数在配置方面,以及每种配置的组合数量.所以在这种情况下,情况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.我希望代码循环,通过以下方式分配带有地雷的组:
所以我们得出了两种配置.这需要适用于更复杂的设置!
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
小智 2
如果您不想暴力破解，可以将流程建模为决策树。假设我们从你的例子开始：
####
#21#
####
如果我们想开始在有效的配置中放置地雷，我们此时基本上有八种选择。由于我们在等价组中选择哪个方格并不重要，因此我们可以将其范围缩小到三个选择。树枝。让我们沿着一个分支走下去：
*###
#11#
####
我在 G1 放置了一个地雷，用星号表示。另外，我还更新了与该等价组相关的数字（在本例中只有一个数字），以表明这些编号的方块现在可以与地雷少邻接。
这并没有减少我们下一步选择的自由度，我们仍然可以在任何等价组中放置一个地雷。让我们在 G1 中放置另一个：
*XX#
*01#
XXX#
另一个星号标记了新矿井，编号方块再次降低了 1。现在它已经达到零，这意味着它不能再与任何地雷接壤。这意味着，对于我们下一次选择的地雷布置，所有依赖于该编号方块的等价组都被排除。 X标记方块，现在我们不能在其中放置任何地雷。我们现在只能做出一个选择：
*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
如果我们忽略数字的顺序，它们显然属于两个等效的类别。
| 归档时间： |
|
| 查看次数： |
629 次 |
| 最近记录： |