EDIT: Это было давно, и с тех пор я начал работать, если вы хотите увидеть код, который он включил в github.com/LewisGaul/minegaulerQt.
Я пытаюсь написать программу для вычисления вероятностей для тральщика игры, и с трудом выяснили, как лучше всего ее структурировать. Хотя сначала может показаться довольно простым пример ниже, я хотел бы знать, как лучше всего обеспечить более сложные конфигурации. Примечание. Я не ищу помощи в том, как рассчитать вероятности - я знаю метод, мне просто нужно его реализовать!
Чтобы понять, что я пытаюсь рассчитать, я проработаю простой пример, который можно сделать вручную. Рассмотрим конфигурацию тральщика
# # # # # 1 2 # # # # #
где # представляет собой незастроенную ячейку. 1 говорит нам, что в самых левых 7 незакрашенных ячейках имеется ровно 1 минута, 2 говорит нам, что в самом правом справа есть ровно 2. Чтобы вычислить вероятность каждой отдельной ячейки, содержащей шахту, нам нужно определить все разные случаи (всего 2 в этом простом случае):
-
1 моя в левых 3 клетках, 2 мин в самых правых 3 клетках (всего 3 мин, 3x3 = 9 комбинаций).
-
1 моя в клетках центра 4, 1 мин в самых правых 3 клетках (всего 2 мин, 4x3 = 12 комбинаций).
Учитывая вероятность того, что шахта в случайной ячейке составляет около 0,2, она (в случайном выборе клеток) примерно в 4 раза более вероятна, всего в общей сложности 2 мин, а не всего 3, поэтому общее количество мин в конфигурации, а также количество комбинаций каждой конфигурации. Таким образом, в этом случае вероятность случая 1 равна 9/(9 + 4x12) = 0,158, а вероятность наличия шахты в данной левой ячейке составляет, таким образом, около 0,158/3 = 0,05, так как эти ячейки являются фактически эквивалентными (они делиться точно такими же обнаруженными соседями).
Я создал графический интерфейс с Tkinter, который позволяет мне легко вводить такие конфигурации, как тот, который приведен в примере, который хранит сетку в виде массива 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]
UPDATE:
Я добавил несколько других классов и немного изменил структуру (см. Ниже рабочий код), и теперь он способен создавать и отображать группы эквивалентности, что является шагом в правильном направлении. Однако мне все же нужно решить, как выполнять итерацию всех возможных минных конфигураций, назначая несколько мин каждой группе таким образом, чтобы создать допустимую конфигурацию. Любая помощь приветствуется.
Например, # # # # # 2 1 # # # # #
Есть три группы эквивалентности G1: левые 3, G2: средний 4, G3: правый 3. Я хочу, чтобы код проходил цикл, назначая группы минами следующим образом:
- G1 = 2 (max первая группа) = > G2 = 0 = > G3 = 1 (это все конфиги с G1 = 2)
- G1 = 1 (уменьшение на единицу) = > G2 = 1 = > G3 = 0 (все это с G1 = 1)
- G1 = 0 = > G2 = 2 INVALID
Итак, мы приходим к обеим конфигурациям. Это необходимо для более сложных настроек!
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
