@keeper_123

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

Добрый день!
Имеется поле, которое нужно заполнить пазлами(элементами) из фиксированного набора.
Нужно написать программу, определяющую возможность заполнения всего поля пазлами т.е. нужно заполнить всё поле пазлами(чтобы не осталось пустых мест).
  • Поле состоит из одного или нескольких многоугольников(с прямыми углами). Задан набором 1 и 0 указывающих на наличие поля и его отсутствие по данным координатам(см. примеры данных).
  • Пазлы могут быть исключительно прямоугольными. Заданны шириной, высотой и количеством(см. примеры данных).
  • Пазлов ограниченное количество каждого размера.
  • Могут оставаться лишние пазлы, но поле должно быть заполнено всё.

Примеры данных

Поле:
1111
1111
1111
0100
Блоки: (Ширина Высота Кол-во)
2 1 3
3 1 1
3 2 1
5d792e72dab48024290952.png

Поле может состоять из нескольких частей:
Поле:
000101
001101
110000
111111
001110
111110
Блоки: (Ширина Высота Кол-во)
1 1 2
2 1 3
3 1 1
2 2 1
6 1 2
5d7930bed2609251315294.png

Пытался придумать алгоритм сам, но идеи были неоптимальными(почти полный перебор вариантов расстановки) или работали не всегда корректно.

Возможно есть определённый подход к написанию алгоритма или похожая задача. Какой алгоритм использовать? или действительно перебор лучший вариант?
  • Вопрос задан
  • 170 просмотров
Пригласить эксперта
Ответы на вопрос 5
longclaps
@longclaps
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).
Ответ написан
SilenceOfWinter
@SilenceOfWinter
та еще зажигалка...
есть так называемая задача рюкзака, но не думаю что её тут можно применить. т.к. нужно вписать блоки не в прямоугольник . можно немного оптимизировать перебор, например, для отдельных площадок (2х палубник на второй схеме). вообще подобный перебор выполняется довольно быстро и оптимизация имеет смысл только для больших площадок.
Ответ написан
Adamos
@Adamos
Полный перебор с возвратом, оптимизированный уточнениями:
1. Элементы стоит отсортировать от больших к меньшим и при переборе отбрасывать повторы.
2. Каждый раз, примеривая очередной элемент на очередное место, проверять, можно ли закрыть каждую из клеток оставшегося поля хоть одним из оставшихся элементов. Отсекая бессмысленный дальнейший перебор.
Ответ написан
alex-1917
@alex-1917
мы делали подобное для сетки 100*100, блоки были от 1*1 до максимума)))
1 нюанс - за один этап добавляется ОДИН блок, при этом на поле уже может находиться некое количество разных блоков.
2 нюанс - еще были условия - расположить ближе к низу или ближе к центру и т.д.
3 нюанс - блок или квадрат или прямоугольник, змеек или углов не было.
но там весь код в mysql-запросах, вряд ли я его буду для тебя пережевывать в алгоритм...
навскидку - вставка в цикле блока и результат - поместился, не поместился и т.д.
т.е. банальщина, вся суть в оптимизации дикого кол-ва запросов

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

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

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Poteha Labs Москва
от 100 000 до 160 000 руб.
HttpLab Ростов-на-Дону
от 60 000 до 150 000 руб.