Как найти наименьший квадрат из фигур тетрамино?

Question

[Uryuk]

Всем привет! Предлагаю Вашему вниманию вопрос над которым я уже 3 суток не могу нормально спать.
У нас есть определенный конечный набор из фигур тетрамино. В процессе нам запрещено их поворачивать и только переставлять. Представленные они в файле блоками из 4×4 элемента где тетрамино это # а пустая ячейка это . (Точка)
Так как блок 4×4 и каждая строка имеет знак переноса строки то весь блок будет размером (4 × 4) + 4 (знак переноса строки) + 1(обьязательный конец/перенос строки. Например:
Если
n это знак переноса строки
# элемент тетрамино
. Пустой элемент
o конец файла
То исходный файл из 2 блоков будет выглядеть так:
. . . . n
. . . # n
.### n
. . . . n
n
# . . . n
# . . . n
# . . . n
# . . . n
o (конец строки (файла))
В квадрате разрешены пустые клетки. Если хоть одна клетка выходит за пределы квадрата считать минимальным квадратом тот который поместите и выступающая часть.
Задача заключается в том что нужно составить самый меньший возможный квадрат из доступных тетрамино.
Проверить валидность файла, блока я могу без проблем. Так же я определил размеры каждой из фигур тетрамино чтоб выделить для них память и сохранить в массиве указателей. Но что дальше с ними делать я не понимаю! Буду благодарен очень за даже глухую мысль. Спасибо огромное!

Comments

[EVGENY T.]

> В квадрате разрешены пустые клетки. Если хоть одна клетка выходит за пределы квадрата считать минимальным квадратом тот который поместите и выступающая часть.

Как-то эти условия странно звучат в задаче о полиомино. Если их убрать, то тетрамино считаются неспремляемыми, поскольку там есть Z-образный элемент.

Но так как сформулировали вы можно попробовать просто перебрать все комбинации, наверно там не такое большое число их будет.

Answer 1

[Wataru]

Перебор. Фиксируем размер квадрата k, потом рекурсивный перебор: берем самую верхнюю-левую не заполенную клетку. Или помечаем ее пустой в ответе, или ставим любое из непоставленных тетрамино (4 варианта сдвига, раз поворотов нет). Естественно, новое терамино должно вставать только в неразмеченные клетки. Нужно всяких отсечений вставлять - типа есть достаточно неразмеченных клеток, чтобы вместить все оставшиеся тетрамино.

Comments

[longclaps]

4 варианта сдвига

Чево? Может столько:
(k - pent_height + 1) * (k - pent_width + 1)

[Wataru]

longclaps, в тетрамино 4 клетки. Любая одна из них должна покрыть текущую клетку. Вот и 4 варианта. Вариант, что текущая клетка не покрыта рассматривается отдельно.

[longclaps]

wataru, ну да, так тоже можно перебирать - но этот вариант даже хуже моего - надо спецом отслеживать выход оставшихся клеток за пределы поля.

[Wataru]

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

[longclaps]

wataru, пока оставим это. В любом случае полный перебор крайне нехорош (а у вас тоже он), а способов избежать его я не вижу.