Оптимизация решателя головоломок

На праздники мне подарили игру под названием "Kanoodle Extreme". Детали игры несколько важны, но я думаю, что мне удалось абстрагироваться от них. В 2D-варианте игры (на котором я сосредоточусь) есть несколько частей, которые можно переворачивать/вращать и т.д. Данная головоломка даст вам определенное количество доски с шестигранной сеткой, которую нужно покрыть, и определенное количество частей, которыми ее можно покрыть. Посмотрите на картинку ниже для быстрого визуального представления, я думаю, что это объясняет большую часть этого.

(Атрибуция изображения: скриншот из списка Amazon)

Вот полное руководство по игре, включая правила, конфигурации доски и фигуры (сайт производителя).

Для удобства вот набор частей (отдельные задачи могут включать подмножество этих частей):

Вот пример нескольких конфигураций досок (показанные части фиксированы - открытые места должны быть заполнены оставшимися частями):

Это интересная игра, но я решил, что хочу не просто решить головоломку, я хочу решить все головоломки. Я сделал это не потому, что это было бы легко, а потому, что я думал, что это будет легко. Как оказалось, метод грубой силы/рекурсии довольно прост. Это также весело неэффективно.

Что я сделал до сих пор? Что ж, я с радостью опубликую код, но у меня его довольно много. По сути, я начал с нескольких предположений:

  1. Не имеет значения, кладу ли я фигуру 1, затем 2, затем 3... или 3, затем 1, затем 2... поскольку каждая фигура должна быть размещена, порядок не имеет значения (ну, имеет большое значение: я думаете, размещение больших кусков первым может быть более эффективным, поскольку вариантов меньше?).

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

  3. Я не ДУМАЮ, что есть чистый алгебраический способ решить эту проблему - я не знаю, классифицирует ли это ее как NP-полную или что-то еще, но я думаю, что для поиска решений необходимо изучить некоторое количество комбинаторики. Это мое наименее уверенное предположение.

Мой подход к решению до сих пор:

Для каждой данной фигуры я нахожу все возможные положения/ориентации указанной фигуры на игровом поле. Я кодирую каждую часть/место на доске в виде растрового изображения (где каждый бит представляет место на доске, а 0 означает незанятость, а 1 означает занятость). Теперь для каждой части у меня есть набор из 20-200 целых чисел (в зависимости от размера доски), которые представляют собой технически допустимые места размещения, хотя не все они оптимальны. (Я думаю, что здесь есть место, чтобы обрезать маловероятные ориентации).

Я храню все эти целые числа на карте в виде списка, связанного с ключом, представляющим индекс рассматриваемой части. Начиная с индекса фрагмента 0, я перебираю все возможные итерации (помеченные индексом этой итерации в списке всех возможных итераций для этого фрагмента) и перебираю все возможные итерации следующего фрагмента. Я беру два целых числа и побитово объединяю их вместе: если я получаю «0», это означает, что между частями нет перекрытия, поэтому их МОГУТ быть помещены вместе.

Я храню все допустимые комбинации из фрагмента 0-1 (например, индекс итерации 5 фрагмента 0 совместим с итерациями фрагмента 1 1-3, 6, 35-39 и 42). Как я это храню, вероятно, не имеет значения, но в настоящее время я храню его как вложенный список: индекс 5 списка будет содержать другой список, содержащий [1, 2, 3, 6, 35, 36, 37, 38, 39, 42] .

Я делаю это для частей 0-1, 0-2, 0-3... 1-2, 1-3... 2-3... каждой комбинации частей. Затем я начинаю находить комбинации из 3 последовательностей: перебирать список допустимых частей 0-> 1 списков и для каждой части 1 индекс (таким образом, 1, 2, 3, 6, 35, 36... из приведенного выше примера), найдите список совместимости из части 1->2 для этого индекса. Это даст мне последовательность списков. Для каждого элемента в этой последовательности я фильтрую его, беря пересечение со списком совместимости для части 0->2 для выбранной итерации части 0.

Это дает мне коллекцию «3-списков». Я нахожу все 3-списки ((0, 1, 2), (1, 2, 3), (2, 3, 4)), и повторяю процесс фильтрации, чтобы получить 4-списки: ((0, 1, 2, 3), (1, 2, 3 4)). Повторите, чтобы получить 5 списков. Если у меня есть только 5 штук, список 5 представляет все решения. Если у меня есть более n штук, повторяйте, пока у меня не будет n-списка.

Этот подход ДЕЙСТВИТЕЛЬНО работает, и я не ДУМАЮ, что дублирую многие (если вообще есть) вычисления, но комбинаторика становится настолько большой, что занимает слишком много времени или — когда у меня 8 или 9 штук — занимает 30+ ГБ оперативной памяти. , затем вылетает.

Конечный вопрос: как я могу решить эту проблему (поиск ВСЕХ решений для данной головоломки) более эффективно?

Подвопросы: оптимизация моего алгоритмического подхода? Оптимизация выполненных вычислений (я использовал целые числа и побитовые операции, а затем установил пересечения, потому что думал, что они будут быстрыми)? Отказ от моих предположений, которые могут привести к более быстрым решениям?

Спасибо!

Я знаю, что это не относится к алгоритму и больше к аппаратной стороне, но не думали ли вы переписать это на cython или более быстром языке?

Zachary 02.01.2023 04:28

Это точная проблема покрытия.

David Eisenstat 02.01.2023 04:35

В зависимости от формы вы вычисляете до 12 зеркальных/повернутых решений, где вы могли бы вычислить 1, а затем применить преобразования. Также противоречие как можно быстрее (например, если вы отрежете площадь 7, решения не будет) или размещение ограниченных частей сначала (например, изменение от размещения частей, чтобы сначала закрыть угол, а затем идти по краю, всегда касаясь предыдущего кусок, как этот, выбор обычно очень ограничен, потому что вы не хотите пробелов) может помочь.

maraca 02.01.2023 04:52

Послушайте @DavidEisenstat (всегда хорошая идея!) Если вы будете следовать ссылкам на точную обложку, вы обнаружите, что очень похожие проблемы решались на компьютерах в 1950-х и начале 60-х годов.

Paul Hankin 02.01.2023 08:43

У вас есть какие-то конкретные формы и доски, для которых ваш текущий подход проблематичен с точки зрения времени выполнения?

trincot 02.01.2023 11:37

@DavidEisenstat Я думал, что это решенная проблема, но я не знал терминологии! Я буду копаться в этом!

Helpful 02.01.2023 18:22

@Zachary Это хороший звонок, но я думаю, что у меня все еще будут проблемы с использованием памяти (по крайней мере, с моим нынешним подходом).

Helpful 02.01.2023 18:23

@maraca У меня определенно есть НЕКОТОРАЯ неэффективность, но когда я конвертирую часть в растровое изображение, я проверяю свой список растровых изображений, чтобы убедиться, что его там еще нет, поэтому мы, по крайней мере, избегаем точных дубликатов. Тем не менее, общая плата все еще может оказаться перевернутой/зеркальной, поэтому мы, вероятно, вычисляем в 4 раза больше необходимых решений.

Helpful 02.01.2023 18:23

@PaulHankin Подойдет, и знание того, что она была решена в 50-60-х годах, предполагает, что мой подход ... менее чем оптимален, ха-ха, поскольку он не может работать на современном оборудовании.

Helpful 02.01.2023 18:24

@trincot 5 и 6 штук - это почти мгновенно, 7 - медленно, 8 - 10 минут, а 9 никогда не заканчивается.

Helpful 02.01.2023 18:24

@ Полезно, это 12, потому что возможно иметь 6-стороннюю симметрию вращения (потому что они шестиугольники), и каждое из этих решений может быть зеркально отражено, поэтому 2 * 6 = 12. На практике это, вероятно, больше похоже на 4 (двухстороннее симметрия вращения и зеркальное отображение), потому что на доске нет места для больших фигур с 6-сторонней симметрией вращения.

maraca 02.01.2023 19:37

Извините, я не знаю, о каких произведениях вы говорите. Не могли бы вы дать очень конкретную информацию (фактические формы фигур и размер доски), для которых производительность неприемлема? Я не знаком с этой игрой, поэтому укажите структуру фигур и форму доски. Изображение хорошее, но недостаточно точное — по крайней мере, для меня.

trincot 02.01.2023 20:43

Всегда ли сетка представляет собой «квадрат» из гексагональных плиток? Или он может образовывать какие-то другие, возможно, асимметричные формы «капли»?

Dillon Davis 03.01.2023 19:24

@DillonDavis В конце доски он сужается, но моя абстракция (наборы целых чисел) должна устранить любые проблемы, связанные с физической формой доски (если только вы не считаете, что абстракция не оптимальна).

Helpful 03.01.2023 19:31

Я думаю, что геометрия доски важна — она накладывает планарное ограничение на состав каждого набора (представляющий фигуру + вращение). Это не должно изменить асимптотическую временную сложность, но, вероятно, позволит оптимизировать производительность в реальном времени.

Dillon Davis 03.01.2023 20:21

Я нашел онлайн-руководство, в котором показаны фигуры, доска, все конфигурации головоломок и более подробно объясняются три вида головоломок. Постараюсь отредактировать вопрос с изображением фигур и одной-двух досок, но задач больше 100, так что я не могу загрузить их все. Ссылка: educationinsights.com/amfile/file/download/file/202/produc‌​t/…

Dillon Davis 03.01.2023 20:23

@trincot смотрите мое редактирование - я включил контекст из руководства производителя игры

Dillon Davis 03.01.2023 20:32

Прямой подход грубой силы будет выполняться в памяти O (n). Короче говоря, вы не формируете все списки длины k, прежде чем перейти к длине k+1. Вместо этого у вас всегда есть один (1) список, и вы пробуете все возможные способы добавления в него элемента, используя поиск с возвратом.

n. m. 04.01.2023 09:30

@н.м. Конечно, есть компромисс между скоростью и памятью. На больших досках я видел фигуры, имеющие более 200 допустимых мест размещения. Предполагая, что каждый раунд равен 100, это означает, что с 9 частями у вас есть 100 ^ 9 = 1e18 возможностей, поэтому, чтобы решить это даже за неделю, потребуется 1,6 триллиона комбинаций в секунду. Я надеюсь на большее, как "несколько секунд". Для справки, у меня работает чистый метод грубой силы/возврата, но этот вопрос касается оптимизации.

Helpful 04.01.2023 16:25

«На больших досках»: какие это размеры досок? Вы имеете в виду ту, что с 56 ячейками, для размещения 12 штук?

trincot 04.01.2023 16:38

«Больше» означает 9+ штук для размещения, поэтому обычно 40+ ячеек вызовут проблемы с памятью на моей машине (использование 30+ ГБ).

Helpful 04.01.2023 16:43

Я не вижу никакого компромисса между скоростью и памятью в вашей реализации. Вы наверняка используете больше памяти, но как это перевести на большую скорость?

n. m. 04.01.2023 17:25

@н.м. Наивный подход с возвратом пересчитывал бы множество возможностей, например: конфигурация части 0 0 могла бы проверить, чтобы увидеть p1o0 и p2o0, и обнаружить, что они несовместимы. Затем, когда я проверяю конфигурацию 1 части 0, я могу пересчитать ее для p1o0 и p2o0. Используя векторизованные операции (набор пересечений), я одновременно распараллеливаю (ускорение) и удаляю избыточные вычисления (ускорение). Я могу получить время наивного подхода по сравнению с моим подходом для 5, 6, 7 штук, это довольно важно.

Helpful 04.01.2023 19:25

Проверять все места размещения всех фигур было бы слишком наивно, нужно заранее отбрасывать нежизнеспособных кандидатов. Как насчет проверки тех, которые закрывают крайнюю левую самую верхнюю непокрытую ячейку? Вы можете предварительно вычислить места размещения, чтобы быстро найти кандидатов, и вы сможете отклонить множество тупиковых позиций на раннем этапе. (В основном та же идея, что и @trincot).

n. m. 05.01.2023 07:24

Я предполагаю, что вы до сих пор игнорировали комментарий @DavidEisenstat: вы должны отметить, что эта (почти) точная проблема описана (с решением не кем иным, как Дональдом Кнутом) здесь: en.wikipedia.org/wiki/Exact_cover#Pentomino_tiling Было бы интересно реализовать решение для танцующих ссылок, попробуйте! В качестве альтернативы вы можете использовать существующее программное обеспечение для решения этой проблемы: en.wikipedia.org/wiki/Dancing_Links#External_links

ldog 05.01.2023 09:21
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
14
25
332
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Один из быстрых способов реализовать эффективный алгоритм для этой задачи — закодировать его как экземпляр SAT, а затем применить готовый решатель SAT. Я нахожу Z3py очень удобным для быстрого внедрения.

По сути, у вас есть логические переменные x_{p,l,o}, где x_{p,l,o} истинно, если кусок p помещен в позицию l с ориентацией o. Затем все правила игры можно преобразовать в логические условия для этих переменных (т. е. в предложения). Вы можете объединить все эти условия, а затем использовать решатель SAT для поиска удовлетворяющего задания.

Решатели SAT очень хорошо справляются с такого рода задачами, если количество переменных не слишком велико.

Я не рекомендую вам вручную реализовывать свой собственный алгоритм, основанный на поиске с возвратом и т. д. В некотором смысле вы можете думать о SAT-решателях как о систематическом способе реализации поиска с возвратом, но у них есть много хорошо настроенных оптимизаций, которые ускоряют его работу.

Раньше я не использовал SAT-решатели, но сейчас просматриваю документацию. Сколько переменных/условий считается «слишком большими»? С 9+ фишками у вас есть 40+ мест на доске, и это может легко быть 100 возможных мест на фишку, то есть у нас будет 900 логических значений с таким подходом. Было бы лучше оформить его как точное покрытие с использованием наборов целых чисел?

Helpful 04.01.2023 16:45

@Полезно, нет установленной границы, сколько слишком много. Вы должны попробовать и посмотреть. Интуитивно я ожидаю, что решатель SAT может сработать, но единственный способ узнать это — попробовать. Это не займет много времени, чтобы закодировать его — я предлагаю вам попробовать. Точное покрытие также разумно, но тогда вам придется реализовать свой собственный алгоритм точного покрытия, который в принципе может дать лучший алгоритм, но на практике также может потребовать больше работы по реализации, чем использование готового SAT-решателя. См. пересмотренный ответ об откате.

D.W. 04.01.2023 21:46
Ответ принят как подходящий

Я думаю, что ваш подход к растровым изображениям — хорошее начало.

Одна из проблем заключается в том, что если комбинацией создается узкая область, в которой ячейка никогда не может быть покрыта ни одной из оставшихся частей, поиск методом грубой силы обнаружит это гораздо позже — после успешного добавления нескольких частей в другую. площадь доски. Это означает, что в конечном итоге таких комбинаций очень много, они объединяются в астрономически большее количество комбинаций, при этом уже ясно, что проблемная область не может быть покрыта ни одной из них.

В глубину

Первое предложение — использовать поиск в глубину: выбрать свободную клетку и найти все возможные позиции фигур, которые могли бы занимать эту клетку, и только те. Если ячейка не может быть закрыта ни одной фигурой, то вернитесь назад. Если есть несколько вариантов, попробуйте первый и перейдите к следующей свободной ячейке и т. д. Возвращаясь к этой позиции, попробуйте следующий способ, которым фигура может закрыть эту ячейку, ... и т. д.

Использование поиска в глубину будет, по крайней мере, более эффективным с точки зрения использования памяти, но также будет иметь ту же проблему: некоторые свободные ячейки становятся недоступными, но это может быть обнаружено намного позже, а это означает, что поиск с возвратом будет неэффективным, поскольку последние размещенные фрагменты получат альтернативы. во-первых, что не решает проблему непокрываемой ячейки.

Выбрать свободную ячейку

Я бы предложил это улучшение в подходе, ориентированном на глубину:

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

  • Теперь вы обнаружите раньше, когда есть ячейка, у которой больше нет надежды на покрытие, поэтому вы можете вернуться раньше, чем обычно;

  • Вы можете выбрать ячейку с наименьшим количеством возможных покрытий. Это означает, что вы на самом деле ищете области, в которых вы можете столкнуться с проблемами в ближайшее время, и отдаете им приоритет, опять же с целью отступить раньше.

Выполнение

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

Этот фрагмент начинается с пустой доски (определяемой строками, но немедленно преобразованной в растровое изображение) и определяет 12 фигур с использованием той же логики преобразования строки в растровое изображение.

Для каждой фигуры он находит все допустимые позиции на доске с 6 поворотами и зеркальным преобразованием. Я считаю, что это то, что вы уже сделали в своей реализации.

Затем он начинает поиск в глубину, но с этой дополнительной логикой, чтобы выбрать «самую сложную» ячейку для покрытия. Все возможные покрытия для этой ячейки представляют потомков в дереве рекурсии.

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

В распечатанном виде будут использоваться отдельные буквы (A-L) для идентификации фрагментов, как показано на изображении, которым вы поделились. Звездочки в выходных данных обозначают ячейки, которые существуют в растровом изображении, но являются «стенами». Эти стены могут быть не все действительно необходимы для алгоритма, но я просто оставил это как есть.

// Utility function to introduce delays between asynchronous executions
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));

// Utility function to translate an array of strings to a bitpattern (bigint)
function hexaShape(lines, width) {
    let bits = 0n;
    let bit = 1n;
    for (let [i, line] of lines.entries()) {
        if (line.length > width * 2 + 1) throw `line width is ${line.length}, but expected at most ${width * 2 + 1}`;
        if (!/^([#-] )*[#-]?$/.test(line)) throw `line ${i} has invalid format`;
        for (let j = 0; j < width; j++) {
            if (line[2*j] === "#") bits |= bit;
            bit <<= 1n;
        }
    }
    return bits;
}

// For I/O handling
const output = document.querySelector("pre"); 
const input = document.querySelector("input");

class Board  {
    /* Constructor takes an array of strings representing lines of the board area,
       surrounded by boundaries.
       See example run for the expected format for the parameter */
    constructor(lines) {
        this.width = (lines[0].length + 1) >> 1;
        this.height = lines.length;
        this.bits = hexaShape(lines, this.width);
        if (lines[0].includes ('-') || lines.at(-1).includes('-')) throw "board should have boundaries";
        if (lines.some(line => /^-|-$/.test(line.trim()))) throw "board should have boundaries";
        // Shapes are the pieces. One shape can have more than one actual position/transformation
        this.shapes = [];
    }
    translate(bits, translation) {
        /* Transform the positioned shape by applying the given 
           translation callback to each cell. Used for mirroring and for rotating.
           Returns an array with the transformed position in all its possible locations 
           on the board. */
        // Rotate 60° clockwise around the (0, 0) coordinate. 
        let old = bits;
        bits = 0n;
        let bit = 1n;
        for (let row = 0; row < this.height; row++) {
            for (let col = 0; col < this.width; col++) {
                if (old & bit) bits |= 1n << BigInt(translation(row, col));
                bit <<= 1n;
            }
        }
        // Shift shape's cell up and left as much as possible -- which probably is an invalid position
        while ((bits & 1n) == 0n) bits >>= 1n;
        // Shift it back within the boundaries of the board and append it to the array of valid positions
        const positions = [];
        while (bits < this.bits) {
            if ((bits & this.bits) == 0) positions.push(bits);
            bits <<= 1n;
        }
        return positions;
    }
    mirror(bits) {
        return this.translate(bits, (row, col) => (row + 1) * (this.width - 1) - col)[0];
    }
    rotation(bits) {
        return this.translate(bits, (row, col) => ((row + col) * this.width) - row);
    }
    addShape(color, lines) {
        let bits = hexaShape(lines, this.width);
        if (bits == 0n) throw "empty shape";
        const positions = [];
        const unique = new Set;
        // Apply mirroring and rotation to arrive at all valid positions of this shape on the board.
        for (let mirror = 0; mirror < 2; mirror++) {
            bits = this.mirror(bits);
            for (let rotation = 0; rotation < 6; rotation++) {
                const shifts = this.rotation(bits);
                bits = shifts[0];
                if (unique.has(bits)) continue; // Skip: it's an already processed position
                unique.add(bits);
                positions.push(...shifts);
            }
        }
        if (positions.length == 0) throw "Could not fit shape unto empty board";
        this.shapes.push({
            color,
            positions,
            placement: 0n
        });
    }
    toString() {
        let output = "";
        let bit = 1n;
        for (let row = 0; row < this.height; row++) {
            output += " ".repeat(row);
            for (let col = 0; col < this.width; col++) {
                const shape = this.shapes.find(({placement}) => placement & bit);
                output += shape ? shape.color[0]
                        : (this.bits & bit) ? "*" : " ";
                output += " ";
                bit <<= 1n;
            }
            output += "\n";
        }
        return output;
    }
    getMoves(occupied, cell) {
        /* Return an array will all possible positions of any unused shape
           that covers the given cell */
        const moves = [];
        for (const shape of this.shapes) {
            if (shape.placement) continue;
            for (const position of shape.positions) {
                if ((cell & position) && !(position & occupied)) { // Found candidate
                    moves.push([shape, position]);
                }
            }
        }
        return moves;
    }
    getCriticalCell(occupied) {
        /* This leads to optimisation: do a quick run over all free cells and 
           count how many ways it can be covered. This will detect when there is a 
           cell that cannot be covered. If there are no such cells, the cell with
           the least number of possible coverings is returned */
        let minCount = Infinity, 
            critical = -2n;
        for (let cell = 1n; cell < occupied; cell <<= 1n) {
            if (cell & occupied) continue; // Occupied
            // Count all moves that would cover this cell                
            let count = this.getMoves(occupied, cell).length;
            if (count < minCount) {
                if (!count) return -1n; // Found a cell that cannot be covered
                minCount = count;
                critical = cell;
            }
        }
        return critical;
    }
    async recur(occupied, remaining) {
        /* Depth-first search for solutions */
        if (remaining === 0) { // BINGO!!
            output.textContent = this.toString();
            await delay(+input.value);
            return;
        }
        const cell = this.getCriticalCell(occupied);
        if (cell == -1n) return; // Stuck. Need to backtrack
        for (const [shape, position] of this.getMoves(occupied, cell)) {
            shape.placement = position;
            await this.recur(occupied | position, remaining - 1);
            shape.placement = 0n;
        }
    }
    async solutions() {
        await this.recur(this.bits, this.shapes.length);
    }
}

function main() {
    const board = new Board([
       "# # # # # # # # # # # # # # #",
        "# # # - - - - - - - - - - - #",
         "# # - - - - - - - - - - - # #",
          "# - - - - - - - - - - - - # #",
           "# - - - - - - - - - - - # # #",
            "# - - - - - - - - - - - # # #",
             "# # # # # # # # # # # # # # #"
    ]);
    board.addShape("A", ["- - - #",
                          "- - # #",
                           "# #"]);
    board.addShape("B", ["- - # #",
                          "# # #"]);
    board.addShape("C", ["- - - - #",
                          "- - - #",
                           "# # #"]);
    board.addShape("D", ["- - - #",
                          "# # # #"]);
    board.addShape("E", ["- # #",
                          "# # #"]);
    board.addShape("F", ["- - #",
                          "# # # #"]);
    board.addShape("G", ["- # - #",
                          "# # #"]);
    board.addShape("H", ["- - #",
                          "- #",
                           "# # #"]);
    board.addShape("I", ["- - - #",
                          "# # #"]);
    board.addShape("J", ["# #",
                          "- # #"]);
    board.addShape("K", ["- # #",
                          "# #"]);
    board.addShape("L", ["- - #",
                          "# # #"]);
    board.solutions();
}

main();
<pre></pre>
Delay: <input type = "number" min = "0" max = "5000" step = "50" value = "50" >

Наблюдения

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

Если вы хотите запустить этот код на досках, где уже были размещены некоторые фигуры (например, на изображениях, которыми вы поделились), измените код следующим образом:

  • Инициализируйте доску большим количеством символов «#», чтобы указать, где уже были размещены фигуры.
  • Закомментируйте позывные addPiece произведений, которых больше нет в наличии.

Размер решения

Я запустил вариант приведенного выше кода, который подсчитывает только решения и использует мемоизацию. Примерно через 25 минут работы результат был: 6 029 968 решений.

// Utility function to introduce delays between asynchronous executions
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));

// Utility function to translate an array of strings to a bitpattern (bigint)
function hexaShape(lines, width) {
    let bits = 0n;
    let bit = 1n;
    for (let [i, line] of lines.entries()) {
        if (line.length > width * 2 + 1) throw `line width is ${line.length}, but expected at most ${width * 2 + 1}`;
        if (!/^([#-] )*[#-]?$/.test(line)) throw `line ${i} has invalid format`;
        for (let j = 0; j < width; j++) {
            if (line[2*j] === "#") bits |= bit;
            bit <<= 1n;
        }
    }
    return bits;
}

const output = document.querySelector("pre"); // For I/O handling
let counter = 0;

class Board  {
    /* Constructor takes an array of strings representing lines of the board area,
       surrounded by boundaries.
       See example run for the expected format for the parameter */
    constructor(lines) {
        this.width = (lines[0].length + 1) >> 1;
        this.height = lines.length;
        this.bits = hexaShape(lines, this.width);
        if (lines[0].includes ('-') || lines.at(-1).includes('-')) throw "board should have boundaries";
        if (lines.some(line => /^-|-$/.test(line.trim()))) throw "board should have boundaries";
        // Shapes are the pieces. One shape can have more than one actual position/transformation
        this.shapes = [];
        this.map = new Map;
    }
    translate(bits, translation) {
        /* Transform the positioned shape by applying the given 
           translation callback to each cell. Used for mirroring and for rotating.
           Returns an array with the transformed position in all its possible locations 
           on the board. */
        // Rotate 60° clockwise around the (0, 0) coordinate. 
        let old = bits;
        bits = 0n;
        let bit = 1n;
        for (let row = 0; row < this.height; row++) {
            for (let col = 0; col < this.width; col++) {
                if (old & bit) bits |= 1n << BigInt(translation(row, col));
                bit <<= 1n;
            }
        }
        // Shift shape's cell up and left as much as possible -- which probably is an invalid position
        while ((bits & 1n) == 0n) bits >>= 1n;
        // Shift it back within the boundaries of the board and append it to the array of valid positions
        const positions = [];
        while (bits < this.bits) {
            if ((bits & this.bits) == 0) positions.push(bits);
            bits <<= 1n;
        }
        return positions;
    }
    mirror(bits) {
        return this.translate(bits, (row, col) => (row + 1) * (this.width - 1) - col)[0];
    }
    rotation(bits) {
        return this.translate(bits, (row, col) => ((row + col) * this.width) - row);
    }
    addShape(color, lines) {
        let bits = hexaShape(lines, this.width);
        if (bits == 0n) throw "empty shape";
        const positions = [];
        const unique = new Set;
        // Apply mirroring and rotation to arrive at all valid positions of this shape on the board.
        for (let mirror = 0; mirror < 2; mirror++) {
            bits = this.mirror(bits);
            for (let rotation = 0; rotation < 6; rotation++) {
                const shifts = this.rotation(bits);
                bits = shifts[0];
                if (unique.has(bits)) continue; // Skip: it's an already processed position
                unique.add(bits);
                positions.push(...shifts);
            }
        }
        if (positions.length == 0) throw "Could not fit shape unto empty board";
        this.shapes.push({
            id: 1n << BigInt(this.shapes.length), // Unique bit for shape
            color,
            positions,
            placement: 0n
        });
    }
    toString() {
        let output = "";
        let bit = 1n;
        for (let row = 0; row < this.height; row++) {
            output += " ".repeat(row);
            for (let col = 0; col < this.width; col++) {
                const shape = this.shapes.find(({placement}) => placement & bit);
                output += shape ? shape.color[0]
                        : (this.bits & bit) ? "*" : " ";
                output += " ";
                bit <<= 1n;
            }
            output += "\n";
        }
        return output;
    }
    getMoves(occupied, cell) {
        /* Return an array will all possible positions of any unused shape
           that covers the given cell */
        const moves = [];
        for (const shape of this.shapes) {
            if (shape.placement) continue;
            for (const position of shape.positions) {
                if ((cell & position) && !(position & occupied)) { // Found candidate
                    moves.push([shape, position]);
                }
            }
        }
        return moves;
    }
    getCriticalCell(occupied) {
        /* This leads to optimisation: do a quick run over all free cells and 
           count how many ways it can be covered. This will detect when there is a 
           cell that cannot be covered. If there are no such cells, the cell with
           the least number of possible coverings is returned */
        let minCount = Infinity, 
            critical = -2n;
        for (let cell = 1n; cell < occupied; cell <<= 1n) {
            if (cell & occupied) continue; // Occupied
            // Count all moves that would cover this cell                
            let count = this.getMoves(occupied, cell).length;
            if (count < minCount) {
                if (!count) return -1n; // Found a cell that cannot be covered
                minCount = count;
                critical = cell;
            }
        }
        return critical;
    }
    async recur(occupied, remaining, usedShapes) {
        /* Depth-first search for solutions */
        if (remaining === 0) { // BINGO!!
            output.textContent = ++counter;
            if (counter % 100 == 0) await delay(0);
            return 1;
        }
        let map = this.map.get(usedShapes);
        if (!map) this.map.set(usedShapes, map = new Map);
        const memoCount = map.get(occupied);
        if (memoCount !== undefined) {
            if (memoCount) {
                counter += memoCount;
                output.textContent = counter;
                if (counter % 100 == 0) await delay(0);
            }
            return memoCount;
        }
        let count = 0;
        const cell = this.getCriticalCell(occupied);
        if (cell != -1n) {
            for (const [shape, position] of this.getMoves(occupied, cell)) {
                shape.placement = position;
                count += await this.recur(occupied | position, remaining - 1, usedShapes | shape.id);
                shape.placement = 0n;
            }
        }
        map.set(occupied, count);
        return count;
    }
    async solutions() {
        let start = performance.now();
        await this.recur(this.bits, this.shapes.length, 0n);
        console.info("all done", counter);
        console.info(performance.now() - start, "milliseconds");
    }
}

function main() {
    const board = new Board([
       "# # # # # # # # # # # # # # #",
        "# # # - - - - - - - - - - - #",
         "# # - - - - - - - - - - - # #",
          "# - - - - - - - - - - - - # #",
           "# - - - - - - - - - - - # # #",
            "# - - - - - - - - - - - # # #",
             "# # # # # # # # # # # # # # #"
    ]);
    board.addShape("A", ["- - - #",
                          "- - # #",
                           "# #"]);
    board.addShape("B", ["- - # #",
                          "# # #"]);
    board.addShape("C", ["- - - - #",
                          "- - - #",
                           "# # #"]);
    board.addShape("D", ["- - - #",
                          "# # # #"]);
    board.addShape("E", ["- # #",
                          "# # #"]);
    board.addShape("F", ["- - #",
                          "# # # #"]);
    board.addShape("G", ["- # - #",
                          "# # #"]);
    board.addShape("H", ["- - #",
                          "- #",
                           "# # #"]);
    board.addShape("I", ["- - - #",
                          "# # #"]);
    board.addShape("J", ["# #",
                          "- # #"]);
    board.addShape("K", ["- # #",
                          "# #"]);
    board.addShape("L", ["- - #",
                          "# # #"]);
    
    board.solutions();
}

main();
Number of solutions found: <pre></pre>

Я считаю, что вы, по сути, применяете поиск в ширину, сохраняя в памяти все позиции с k штук, прежде чем перейти к k+1 штукам. Вместо этого поиск в глубину был бы гораздо более жизнеспособным: он не хранил бы ничего, кроме текущего состояния доски и некоторой вспомогательной информации, например, какие фигуры уже размещены.

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

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

Чтобы ускорить его в несколько раз, отслеживайте положение последнего закрытого квадрата, поэтому вам придется искать оттуда, а не с самого начала, а также отслеживать, какие части все еще отсутствуют. Также сохраните плату как битовую маску. Предварительно вычислите маски для всех возможных сдвигов, переворотов и вращений всех частей, чтобы быстро проверить, подходит ли часть, и быстро изменить состояние вперед и назад (xor).

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

Другие вопросы по теме