Это отличается от генерации полимино, но это и NP-сложная проблема.Мне даны полимино с размерами 4, 5, 6 в виде массива.
'F':{'num':0b011110010,'width':3} #will be mutated to polymino as
((0,1,1),(1,1,0),(0,1,0)) #as printed
(0,1,1)
(1,1,0)
(0,1,0)
И у меня есть двумерный массив, который известен тем, что у него есть хотя бы один способ заполнить его заданным набором полимино.
Задача состоит в том, чтобы найти способы разбиения массива.
Для решения проблемы я создал алгоритм, как,
A1.поменять местами все возможные вращения данных фишек и добавить в словарь
Solver.keyset[tupleall(reverse_binary(objs.rotate(rots).shape))] = [[objs.name, rots, (0,0)]]
A2.проверить, находится ли данный массив в словаре
A3a.разделите массив для решения по осям x, y и найдите для меньших
A3b.добавить массивы, которые имеют решение, из словаря и решить для него
Это очень хорошо работает для небольших массивов,
a = Solver(((0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0)))
a.chips(5,6) #chip sized for 5-6
a.solver()
a.info
[['6C', 3, (0, 0), '6D', 1, (0, 1)], ['6C', 1, (0, 1), '6D', 3, (0, 0)], ['6A', 2, (0, 0), '6A', 0, (1, 0)], ['6A', 3, (1, 0), '6A', 1, (0, 0)], ['6A', 0, (1, 0), '6A', 2, (0, 0)], ['6A', 1, (0, 0), '6A', 3, (1, 0)], ['6D', 3, (0, 0), '6C', 1, (0, 1)], ['6D', 1, (0, 1), '6C', 3, (0, 0)]]
(Ну, мне нужно вырвать некоторые полимино, которые дублируютсяротация) Но для больших массивов это стоит слишком много времени.
1 - Стоит ли делать мой алгоритм?- у меня есть альтернативные алгоритмы, чтобы решить это лучше?Я пытался использовать грубую силу, добавляя все возможные пути, но это заняло слишком много времени, так что я до сих пор не получил ответ для массива (8,6).
2 - Будет ли разрешен только один ответ из каждого деленияпомог бы?- Он будет многократно ускоряться, чтобы найти мало ответов, но его разнообразие уменьшится.