Я новичок в мире решателей SAT, и мне нужно некоторое руководство по следующей проблеме.
Учитывая, что:
❶ У меня есть выбор из 14 соседних ячеек в сетке 4 * 4
❷ У меня 5 полиомино (A, B, C, D, E) размеров 4, 2, 5, 2 и 1
Poly эти полиомино являются свободными , то есть их форма не является фиксированной и может формировать различные структуры
Как я могу вычислить все возможные комбинации этих 5 свободных полиомино в выделенной области (ячейки серого цвета) с помощью SAT-решателя?
Заимствуя как проницательный ответ @ spinkus, так и документацию по OR-tools, я мог бы сделать следующий пример кода (работает в блокноте Jupyter):
from ortools.sat.python import cp_model
import numpy as np
import more_itertools as mit
import matplotlib.pyplot as plt
%matplotlib inline
W, H = 4, 4 #Dimensions of grid
sizes = (4, 2, 5, 2, 1) #Size of each polyomino
labels = np.arange(len(sizes)) #Label of each polyomino
colors = ('#FA5454', '#21D3B6', '#3384FA', '#FFD256', '#62ECFA')
cdict = dict(zip(labels, colors)) #Color dictionary for plotting
inactiveCells = (0, 1) #Indices of disabled cells (in 1D)
activeCells = set(np.arange(W*H)).difference(inactiveCells) #Cells where polyominoes can be fitted
ranges = [(next(g), list(g)[-1]) for g in mit.consecutive_groups(activeCells)] #All intervals in the stack of active cells
def main():
model = cp_model.CpModel()
#Create an Int var for each cell of each polyomino constrained to be within Width and Height of grid.
pminos = [[] for s in sizes]
for idx, s in enumerate(sizes):
for i in range(s):
pminos[idx].append([model.NewIntVar(0, W-1, 'p%i'%idx + 'c%i'%i + 'x'), model.NewIntVar(0, H-1, 'p%i'%idx + 'c%i'%i + 'y')])
#Define the shapes by constraining the cells relative to each other
## 1st polyomino -> tetromino ##
# #
# #
# # #
# ### #
# #
################################
p0 = pminos[0]
model.Add(p0[1][0] == p0[0][0] + 1) #'x' of 2nd cell == 'x' of 1st cell + 1
model.Add(p0[2][0] == p0[1][0] + 1) #'x' of 3rd cell == 'x' of 2nd cell + 1
model.Add(p0[3][0] == p0[0][0] + 1) #'x' of 4th cell == 'x' of 1st cell + 1
model.Add(p0[1][1] == p0[0][1]) #'y' of 2nd cell = 'y' of 1st cell
model.Add(p0[2][1] == p0[1][1]) #'y' of 3rd cell = 'y' of 2nd cell
model.Add(p0[3][1] == p0[1][1] - 1) #'y' of 3rd cell = 'y' of 2nd cell - 1
## 2nd polyomino -> domino ##
# #
# #
# # #
# # #
# #
#############################
p1 = pminos[1]
model.Add(p1[1][0] == p1[0][0])
model.Add(p1[1][1] == p1[0][1] + 1)
## 3rd polyomino -> pentomino ##
# #
# ## #
# ## #
# # #
# #
################################
p2 = pminos[2]
model.Add(p2[1][0] == p2[0][0] + 1)
model.Add(p2[2][0] == p2[0][0])
model.Add(p2[3][0] == p2[0][0] + 1)
model.Add(p2[4][0] == p2[0][0])
model.Add(p2[1][1] == p2[0][1])
model.Add(p2[2][1] == p2[0][1] + 1)
model.Add(p2[3][1] == p2[0][1] + 1)
model.Add(p2[4][1] == p2[0][1] + 2)
## 4th polyomino -> domino ##
# #
# #
# # #
# # #
# #
#############################
p3 = pminos[3]
model.Add(p3[1][0] == p3[0][0])
model.Add(p3[1][1] == p3[0][1] + 1)
## 5th polyomino -> monomino ##
# #
# #
# # #
# #
# #
###############################
#No constraints because 1 cell only
#No blocks can overlap:
block_addresses = []
n = 0
for p in pminos:
for c in p:
n += 1
block_address = model.NewIntVarFromDomain(cp_model.Domain.FromIntervals(ranges),'%i' % n)
model.Add(c[0] + c[1] * W == block_address)
block_addresses.append(block_address)
model.AddAllDifferent(block_addresses)
#Solve and print solutions as we find them
solver = cp_model.CpSolver()
solution_printer = SolutionPrinter(pminos)
status = solver.SearchForAllSolutions(model, solution_printer)
print('Status = %s' % solver.StatusName(status))
print('Number of solutions found: %i' % solution_printer.count)
class SolutionPrinter(cp_model.CpSolverSolutionCallback):
''' Print a solution. '''
def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.variables = variables
self.count = 0
def on_solution_callback(self):
self.count += 1
plt.figure(figsize = (2, 2))
plt.grid(True)
plt.axis([0,W,H,0])
plt.yticks(np.arange(0, H, 1.0))
plt.xticks(np.arange(0, W, 1.0))
for i, p in enumerate(self.variables):
for c in p:
x = self.Value(c[0])
y = self.Value(c[1])
rect = plt.Rectangle((x, y), 1, 1, fc = cdict[i])
plt.gca().add_patch(rect)
for i in inactiveCells:
x = i%W
y = i//W
rect = plt.Rectangle((x, y), 1, 1, fc = 'None', hatch = '///')
plt.gca().add_patch(rect)
Проблема в том, что у меня есть жестко запрограммированные 5 уникальных / фиксированных полиомино, и я не знаю, как определить ограничения, чтобы каждый возможный шаблон для каждого полиомино учитывался (при условии, что это возможно).
itertools
,numpy
,networkx
?minizinc
теге с подробным ответом, который охватывает мое предыдущее предложение об использованииminizinc
.Ответы:
РЕДАКТИРОВАТЬ: я пропустил слово «свободный» в исходном ответе и дал ответ, используя OR-Tools для фиксированных polyominoes. В ответ добавили раздел, включающий решение для свободных полиомино, которое, как оказалось, довольно сложно выразить AFAICT точно в программировании с помощью OR-Tools.
ФИКСИРОВАННЫЕ ПОЛИОМИНО С ИЛИ ИНСТРУМЕНТАМИ:
Да, вы можете сделать это с помощью программирования ограничений в OR-Tools. OR-Tools ничего не знает о геометрии двумерной сетки, поэтому вам необходимо кодировать геометрию каждой фигуры в терминах позиционных ограничений. Т.е. форма - это набор блоков / ячеек, которые должны иметь определенное отношение друг к другу, должны находиться в пределах сетки и не должны пересекаться. Когда у вас есть модель ограничений, вы просто попросите, чтобы CP-SAT Solver решил ее, в вашем случае, для всех возможных решений.
Вот действительно простое доказательство концепции с двумя прямоугольными фигурами на сетке 4x4 (вы также, вероятно, захотите добавить некоторый код интерпретатора, чтобы перейти от описаний фигур к набору переменных и ограничений OR-Tools в задаче большего масштаба так как ввод ограничений вручную немного утомителен).
дает:
БЕСПЛАТНЫЕ ПОЛИОМИНО:
Если мы рассматриваем сетку ячеек как граф, проблему можно переосмыслить как нахождение k-разбиения ячеек сетки, где каждый раздел имеет определенный размер и, кроме того, каждый раздел является связанным компонентом . Т.е. AFAICT нет никакой разницы между связанным компонентом и polyomino, и остальная часть этого ответа делает это предположение.
Нахождение всех возможных «k-разделов ячеек сетки, где каждый раздел имеет определенный размер» довольно тривиально, чтобы выразить это в программировании ограничений OR-Tools. Но связность - это тяжело (я пытался и терпел неудачу довольно долго ...). Я думаю, что программирование ограничений OR-Tools не является правильным подходом. Я заметил, что в справочнике OR-Tools C ++ для библиотек оптимизации сети есть кое-что о подключенных компонентах, на которые стоит обратить внимание, но я не знаком с этим. С другой стороны, наивное рекурсивное решение поиска в Python вполне выполнимо.
Вот это «от руки» наивное решение. Это довольно медленно, но терпимо для вашего случая 4х4. Адреса используются для идентификации каждой ячейки в сетке. (Также обратите внимание, что вики-страница ссылается на что-то вроде этого алгоритма как наивное решение и выглядит так, как будто предлагает несколько более эффективных для подобных проблем с полиомино).
дает:
источник
Одним из относительно простых способов ограничения односвязной области в OR-Tools является ограничение ее границы как схемы . Если все ваши polyominos должны иметь размер меньше 8, нам не нужно беспокоиться о не просто связанных.
Этот код находит все 3884 решения:
источник
Для каждого polyonomino и каждой возможной верхней левой ячейки у вас есть логическая переменная, которая указывает, является ли эта ячейка верхней левой частью окружающего прямоугольника.
Для каждой ячейки и каждого polyomino у вас есть логическая переменная, которая указывает, занята ли эта ячейка этим polyomino.
Теперь для каждой ячейки и каждого полиомино у вас есть ряд значений: верхняя левая ячейка выбрана означает, что каждая клетка фактически занята этим полиомино.
Тогда ограничения: для каждой ячейки, самое большее одно polyomino занимает это для каждого polyomino, есть точно одна ячейка, которая является ее верхней левой частью.
это чисто логическая проблема.
источник