Я решил эту проблему с графиком , используя рекурсивный возврат алгоритм плюс памятка . Мое решение не очень быстрое и занимает около минуты или около того, чтобы решить сетку 9x12, но этого должно быть достаточно для сетки 8x8 в вашем вопросе (на 9x9 это займет около секунды). Для сеток 7x7 и 8x8 не существует решений, поскольку они не делятся на размер triomino, 3.
Стратегия состоит в том, чтобы начинать с угла сетки и перемещаться по нему ячейка за ячейкой, стараясь размещать каждый блок всякий раз, когда это допустимо, и, таким образом, методично исследовать пространство решения.
Если размещение блока является законным, но создает незаполненный воздушный карман в сетке, удалите блок; мы знаем заранее, что у этого государства не будет решений, и можем отказаться от изучения его детей. Например, в сетке 3x6
abb.c.
aabcc.
......
безнадежно неразрешим.
Как только будет достигнуто состояние, когда все ячейки заполнены, мы можем сообщить счетчик 1 решению его родительскому состоянию. Вот пример решенной сетки 3х6:
aaccee
abcdef
bbddff
Если каждый возможный блок был размещен в позиции, откатитесь назад, сообщая счетчик решений по пути к родительским состояниям по пути и исследуя любые состояния, которые еще не исследованы.
С точки зрения запоминания, назовите любые два состояния сетки эквивалентными, если есть какое-то расположение плиток, чтобы они покрывали точно такие же координаты. Например:
aacc..
abdc..
bbdd..
и
aacc..
bacd..
bbdd..
считаются эквивалентными, даже если два состояния были достигнуты с помощью различных размещений плитки. Оба состояния имеют одинаковую подструктуру, поэтому достаточно подсчета количества решений для одного состояния; добавьте это в памятку, и если мы снова достигнем состояния, мы можем просто сообщить количество решений из памятки, а не пересчитать все.
Моя программа сообщает о 8 решениях в сетке 3x6:
Как я уже говорил, мое решение на Python не является быстрым или оптимизированным. Решить сетку 9x12 можно менее чем за секунду. Если не считать больших оптимизаций, в моей реализации я не учел основные вещи. Например, я скопировал всю сетку для каждого размещения плитки; добавление / удаление плиток на одной сетке было бы простым улучшением. Я также не проверял неразрешимые пробелы в сетке, которые можно увидеть в анимации.
После того, как вы решите проблему, обязательно поищите некоторые из умопомрачительных решений, которые придумали люди. Я не хочу отдавать намного больше, чем это!