РЕДАКТИРОВАТЬ: Я пропустил слово "free" в исходном ответе и дал ответ, используя OR-Tools для фиксированных polyomino. В ответ добавлен раздел, включающий в себя решение для свободных полиомино, которое AFAICT оказывается довольно трудным express для точного программирования с помощью OR-Tools.
ИСПРАВЛЕННЫЕ ПОЛИОМИНО С ИЛИ-ИНСТРУМЕНТАМИ:
Да, вы можете сделать это с помощью программирования ограничений в OR-Tools. OR-Tools ничего не знает о геометрии 2D-сетки, поэтому вы должны кодировать геометрию каждой фигуры, которую вы имеете, в терминах позиционных ограничений. Т.е. форма - это набор блоков / ячеек, которые должны иметь определенное отношение друг к другу, должны находиться в пределах сетки и не должны перекрываться. Если у вас есть модель ограничений, просто попросите CP-SAT Solver решить ее, в вашем случае, для всех возможных решений.
Вот действительно простое доказательство концепции с двумя прямоугольниками фигуры в сетке 4x4 (возможно, вы захотите добавить некоторый код интерпретатора к go от описаний фигур до набора переменных и ограничений OR-Tools в более крупномасштабной задаче, поскольку ввод ограничений вручную немного утомительно).
from ortools.sat.python import cp_model
(W, H) = (3, 3) # Width and height of our grid.
(X, Y) = (0, 1) # Convenience constants.
def main():
model = cp_model.CpModel()
# Create an Int var for each block of each shape constrained to be within width and height of grid.
shapes = [
[
[ model.NewIntVar(0, W, 's1b1_x'), model.NewIntVar(0, H, 's1b1_y') ],
[ model.NewIntVar(0, W, 's1b2_x'), model.NewIntVar(0, H, 's1b2_y') ],
[ model.NewIntVar(0, W, 's1b3_x'), model.NewIntVar(0, H, 's1b3_y') ],
],
[
[ model.NewIntVar(0, W, 's2b1_x'), model.NewIntVar(0, H, 's2b1_y') ],
[ model.NewIntVar(0, W, 's2b2_x'), model.NewIntVar(0, H, 's2b2_y') ],
]
]
# Define the shapes by constraining the blocks relative to each other.
# 3x1 rectangle:
s0 = shapes[0]
model.Add(s0[0][Y] == s0[1][Y])
model.Add(s0[0][Y] == s0[2][Y])
model.Add(s0[0][X] == s0[1][X] - 1)
model.Add(s0[0][X] == s0[2][X] - 2)
# 1x2 rectangle:
s1 = shapes[1]
model.Add(s1[0][X] == s1[1][X])
model.Add(s1[0][Y] == s1[1][Y] - 1)
# No blocks can overlap:
block_addresses = []
for i, block in enumerate(blocks(shapes)):
block_address = model.NewIntVar(0, (W+1)*(H+1), 'b%d' % (i,))
model.Add(block[X] + (H+1)*block[Y] == 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(shapes)
status = solver.SearchForAllSolutions(model, solution_printer)
print('Status = %s' % solver.StatusName(status))
print('Number of solutions found: %i' % solution_printer.count)
def blocks(shapes):
''' Helper to enumerate all blocks. '''
for shape in shapes:
for block in shape:
yield block
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
solution = [(self.Value(block[X]), self.Value(block[Y])) for shape in self.variables for block in shape]
print((W+3)*'-')
for y in range(0, H+1):
print('|' + ''.join(['#' if (x,y) in solution else ' ' for x in range(0, W+1)]) + '|')
print((W+3)*'-')
if __name__ == '__main__':
main()
Дает:
...
------
| |
| ###|
| # |
| # |
------
------
| |
| ###|
| #|
| #|
------
Status = OPTIMAL
Number of solutions found: 60
БЕСПЛАТНЫЕ ПОЛИОМИНО:
Если мы рассмотрим сетка ячеек в виде графика, проблема может быть переосмыслена как нахождение k-раздела ячеек сетки, где каждый раздел имеет определенный c размер, и, кроме того, каждый раздел является связанным компонентом . Т.е. AFAICT нет никакой разницы между подключенным компонентом и polyomino , и остальная часть этого ответа делает это предположение.
Нахождение всех возможных "k-разбиений ячеек сетки, где каждый раздел имеет определенный c размер ", что довольно просто для express в программировании ограничений OR-Tools. Но связность часть жесткая AFAICT (я пытался и потерпел неудачу довольно долгое время ...). Я думаю, что программирование ограничений OR-Tools не является правильным подходом. Я заметил, что в справочнике OR-Tools C ++ для библиотек оптимизации сети есть кое-что о подключенных компонентах , на которые стоит обратить внимание, но я не знаком с этим. С другой стороны, решение наивного рекурсивного поиска в Python вполне выполнимо.
Вот наивное решение «вручную». Это довольно медленно, но терпимо для вашего случая 4х4. Адреса используются для идентификации каждой ячейки в сетке. (Также обратите внимание, что вики-страница ссылается на что-то вроде этого алгоритма как наивное решение и выглядит так, как будто оно предлагает более эффективные алгоритмы для аналогичных проблем с полиомино).
import numpy as np
from copy import copy
from tabulate import tabulate
D = 4 # Dimension of square grid.
KCC = [5,4,2,2] # List of the sizes of the required k connected components (KCCs).
assert(sum(KCC) <= D*D)
VALID_CELLS = range(2,D*D)
def search():
solutions = set() # Stash of unique solutions.
for start in VALID_CELLS: # Try starting search from each possible starting point and expand out.
marked = np.zeros(D*D).tolist()
_search(start, marked, set(), solutions, 0, 0)
for solution in solutions: # Print results.
print(tabulate(np.array(solution).reshape(D, D)))
print('Number of solutions found:', len(solutions))
def _search(i, marked, fringe, solutions, curr_count, curr_part):
''' Recursively find each possible KCC in the remaining available cells the find the next, until none left '''
marked[i] = curr_part+1
curr_count += 1
if curr_count == KCC[curr_part]: # If marked K cells for the current CC move onto the next one.
curr_part += 1
if curr_part == len(KCC): # If marked K cells and there's no more CCs left we have a solution - not necessarily unique.
solutions.add(tuple(marked))
else:
for start in VALID_CELLS:
if marked[start] == 0:
_search(start, copy(marked), set(), solutions, 0, curr_part)
else:
fringe.update(neighbours(i, D))
while(len(fringe)):
j = fringe.pop()
if marked[j] == 0:
_search(j, copy(marked), copy(fringe), solutions, curr_count, curr_part)
def neighbours(i, D):
''' Find the address of all cells neighbouring the i-th cell in a DxD grid. '''
row = int(i/D)
n = []
n += [i-1] if int((i-1)/D) == row and (i-1) >= 0 else []
n += [i+1] if int((i+1)/D) == row and (i+1) < D**2 else []
n += [i-D] if (i-D) >=0 else []
n += [i+D] if (i+D) < D**2 else []
return filter(lambda x: x in VALID_CELLS, n)
if __name__ == '__main__':
search()
Дает:
...
- - - -
0 0 1 1
2 2 1 1
4 2 3 1
4 2 3 0
- - - -
- - - -
0 0 4 3
1 1 4 3
1 2 2 2
1 1 0 2
- - - -
Number of solutions found: 3884