Задача решается методом бэктрекинга (поиск с возвратом). Количество возможных состояний каждого полиомино ограничено. На каждом шаге для очередного полиомино ищется место на столе. Если место найдено, то осуществляется переход к следующему полиомино, если нет -- происходит возврат к предыдущему полиомино, которое переходит в своё следующее состояние (вращением и/или сдвигом).
Задачу также можно решить с использованием SAT
солверов.
Полиомино хранятся поклеточно. Одновременно могут храниться не более N
конфигураций, где N
- количество полиомино. Поэтому сложность по памяти составит k1 + (k1 + k2) + (k1 + k2 + k3) + ... + (k1 + ... + kN) = O(kN^2)
, где k_i
- количество единичных клеток i
-го полиомино, а k = max(k_1, ..., k_N)
.
Задача является NP
-полной. Сложность по времени в худшем случае составит O((4mn)^N)
, где m
и n
- размеры стола.
- Установка необходимых библиотек
pip install -r requirements.lock.txt
- Запуск
python example.py