Задача заполнения поля пазлами. Какие варианты решения?

sample = (("11", "1 1 2"),
          ("1111\n1111\n1111\n0100", "2 1 3\n3 1 1\n3 2 1"),
          ("000101\n001101\n110000\n111111\n001110\n111110",
           "1 1 2\n2 1 3\n3 1 1\n2 2 1\n6 1 2"),
          ("111\n101\n111", "2 1 4"))


class Field:
    def flip(self):
        self.cells[:] = sorted((x, y) for y, x in self.cells)
        self.flipped ^= True

    def dismantle(self, cells, flipped):
        self.cells, self.flipped = cells, flipped
        left, right = cells[0][0], cells[-1][0]
        tmp = sorted(y for _, y in cells)
        top, bottom = tmp[0], tmp[-1]
        h, w = bottom - top + 1, right - left + 1
        if w * h == len(cells):
            wh = (w, h) if h < w else (h, w)
            c = tails.get(wh, 0)
            if c:
                tails[wh] = c - 1
                yield (self,)
                tails[wh] = c
        for lo, hi in (left, right), (top, bottom):
            for i, (x, _) in enumerate(cells):
                if lo < x <= hi:
                    for one in Field().dismantle(cells[:i], self.flipped):
                        for two in Field().dismantle(cells[i:], self.flipped):
                            yield [*one, *two]
                    lo = x
            self.flip()


_field, _tails = sample[0]
tails = {}
for s in _tails.splitlines():
    w, h, c = map(int, s.split())
    if w < h:
        w, h = h, w
    tails[w, h] = c
for partition in Field().dismantle(
        sorted((x, y) for y, s in enumerate(_field.splitlines())
               for x, c in enumerate(s) if c == '1'), False):
    for f in partition:
        if f.flipped:
            f.flip()
        print(*f.cells)
    break
else:
    print('не смогла')

Ломается на 3м примере, "бублике". Это чинится, но лень возиться. Односвязные области должна решать всегда (if possible).

есть так называемая задача рюкзака, но не думаю что её тут можно применить. т.к. нужно вписать блоки не в прямоугольник . можно немного оптимизировать перебор, например, для отдельных площадок (2х палубник на второй схеме). вообще подобный перебор выполняется довольно быстро и оптимизация имеет смысл только для больших площадок.

Полный перебор с возвратом, оптимизированный уточнениями:
1. Элементы стоит отсортировать от больших к меньшим и при переборе отбрасывать повторы.
2. Каждый раз, примеривая очередной элемент на очередное место, проверять, можно ли закрыть каждую из клеток оставшегося поля хоть одним из оставшихся элементов. Отсекая бессмысленный дальнейший перебор.

мы делали подобное для сетки 100*100, блоки были от 1*1 до максимума)))
1 нюанс - за один этап добавляется ОДИН блок, при этом на поле уже может находиться некое количество разных блоков.
2 нюанс - еще были условия - расположить ближе к низу или ближе к центру и т.д.
3 нюанс - блок или квадрат или прямоугольник, змеек или углов не было.
но там весь код в mysql-запросах, вряд ли я его буду для тебя пережевывать в алгоритм...
навскидку - вставка в цикле блока и результат - поместился, не поместился и т.д.
т.е. банальщина, вся суть в оптимизации дикого кол-ва запросов
А по факту - хорошо по алгоритмам подсказал Mike со стэка и еще кто-то с mysql-форума, тут вряд ли есть такие умы, извини, Тостер.

Мне видится метод ветвей и границ (умный перебор).
Грубо говоря, когда ты ставишь фигуру на поле ты получаешь такую же задачу, но с меньшим количеством элементов и с меньшей площадью поля. Пробуя фигуру, ты по определённым критериям можешь оценить доступность варианта, и если он пока доступен - продолжить процедуру рекурсивно.

Алгоритм, примерно, следующий:
1. Выбор фигуры: любой, но для уменьшения количество возможных ветвей решения нужно выбрать фигуру, которая на текущем поле может находиться в наименьших местах. Для этого берём каждый вид фигуры и примеряем на каждое место. При проверке помечаем использованные места поля. Если обнаружится, что есть места, которые невозможно покрыть, то решение в такой конфигурации не существует - отбраковываем ветвь решения.
2. Ставим фигуру в одно из возможных мест, тем самым мы уменьшаем количество фигур и размер доски. И рекурсивно переходим на шаг 1.

Для отсекания ветвей можно разработать дополнительные быстрые проверки.
Выбор места для следующей фигуры также можно делать не случайным образом, а по какому-либо алгоритму.

Для первого примера: 1х2 - 18 возможных мест, 1х3 - 11 мест, 2х3 - 7 мест. Поэтому мы выбираем третью фигуру для первого шага ветвления.
Ставим первую фигуру в угол (0,0) вертикально, получаем такую картину:
0011
0011
0011
0100
При выполнении первого шага алгоритма выясняется, что поле (1,3) невозможно покрыть ни одной фигурой - ветвь обрывается, переходим к следующему варианту.

Данный алгоритм точно найдёт нужное решение, так как он сводится, в худшем случае, к полному перебору.