Алгоритм Х или что общего между деревянной головоломкой и танцующим Линком?



Предисловие


Как-то в гостях мне в руки попалась головоломка, в которой из 25 одинаковых фигурок требовалось собрать куб. Я провозился с ней почти весь вечер, и как можно догадаться, абсолютно безрезультатно. Тем не менее, я не мог сдаться просто так.

Не можешь сам — заставь компьютер. Сказано — сделано. В результате написанному по наитию алгоритму пришлось работать всю ночь, чтобы найти все 4 уникальных решения. В процессе гугления решений для сравнения, я нашёл программу Burr Tools, которая справилась с этой задачей за 3 минуты на моём ноутбуке.

Такая разница в скорости заставила меня разобраться, как решается эта задача и ещё целый класс подобных.





Описание головоломки 25N puzzle cube

Вам предоставлены 25 «объёмных» пентаминошек типа N.
Каждая пентаминошка состоит из пяти кубиков.
Из этих фигурок требуется составить куб размера 5×5×5.


Данная головоломка является классическим представителем задачи о точном покрытии.
Математическая формулировка
Пусть у нас дано множество X, и множество его подмножеств S. Тогда задача состоит в том, чтобы из множества S, выделить подмножество S* такое, что каждый элемент из X содержится ровно в одном элементе S*.

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

Для такой задачи существует Алгоритм X Дональда Кнута. Но прежде чем перейти к рассмотрению алгоритма давайте посмотрим, как свести нашу головоломку с составлением куба к задаче о точном покрытии.

Формализация задачи


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



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



Формулировка задачи через матрицу
Пусть нам дана матрица S состоящая из нулей и единиц. Требуется выкинуть из этой матрицы некоторое количество строк, чтобы в оставшейся матрице каждый столбец содержал ровно одну единицу.


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

Алгоритм X


Алгоритм X состоит их нескольких шагов, которые сводят задачу к исходной, но с меньшим количеством столбцов/строк. Причём надо отметить, что алгоритм ветвится на определённом шаге. Иными словами, это всё равно перебор, но умный :-)

Шаг 1. Выбрать какой-нибудь столбец c в матрице S



Выбор столбца на геометрическом языке означает выбор какого-нибудь ещё не покрытого квадратика. В нашем случае это будет квадратик 24.

Шаг 2. Форкнуть алгоритм для каждой строки r, такой что Sr,c=1



Квадратик 24 может закрываться как положением A, так и положением D. У нас нет предпосылок выбрать то или другое, поэтому мы отдельно рассматриваем оба варианта. Это шаг, на котором осуществляется перебор вариантов. Чтобы уменьшить их число, часто на шаге 1 выбирают не произвольный столбец, а столбец, содержащий наименьшее число единиц.

Шаг 3. Для выбранной строки r, рассматриваются все столбцы j, такие что Sr,j=1



Выберем строку A и внесём её в наш стек решения. Теперь нам нужно выделить все квадратики, которые занимает положение A.

Шаг 4. Для всех ненулевых элементов столбцов j удалим строки, в которых они находятся, а потом и сами столбцы j



Все строки, которые имеют ненулевые элементы в выбранных столбцах, уже точно не могут участвовать в построении этой ветки решения. Другими словами, мы избавляемся от всех положений уголка, которые пересекаются (имеют общие квадратики) с положением A. Более того, поскольку квадратики 24, 33, 34 мы уже покрыли (строка А уже сидит в стеке), то нам не нужно о них заботиться дальше, и соответствующие столбцы тоже удаляются.

Шаг 5. Перейти к шагу 1 с уменьшенной матрицей



После удаления строк и столбцов мы получили меньшую таблицу. А с точки зрения геометрии мы получили задачу о покрытии меньшей фигуры, причём оставшиеся строчки автоматически соответствуют возможным положениям уголков в этой фигуре.

Анекдот про кастрюльку
Физика и математика просят вскипятить воду в кастрюльке. Оба решают задачу одинаково: набирают воду в кастрюльку, ставят на плиту и включают её. После чего их просят вскипятить воду, которая уже находится в кастрюльке. Физик ставит кастрюльку на плиту и включает её. Математик выливает воду в раковину и говорит: «А теперь решим предыдущую задачу».


Окончание алгоритма


После перехода к шагу 1, у нас могут возникнуть особые ситуации.

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

Ситуация 2. Мы выбрали столбец, но в нём нет ни одной единицы, как например, у столбца 44 на последней картинке. Это означает, что для выбранного квадратика не осталось ни одного положения уголка, который бы мог его покрыть. Следовательно, эта ветвь не имеет решения. Частный случай такой ситуации — в матрице не осталось строк. Стоит заметить, что выбирая на шаге 1 столбец с наименьшим числом единиц, мы всегда получим пустой столбец, как только он появится.

Поскольку за итерацию алгоритма мы заведомо избавляемся от одной строки и одного столбца, количество строк и столбцов уменьшается, и рано или поздно мы придём к ситуации 1 или ситуации 2.


Dancing links


Для быстрой работы алгоритма необходимо уметь быстро удалять строки и столбцы из матрицы. Если хранить матрицу в виде двумерного массива, то это достаточно проблематично. С другой стороны, получаемая матрица практически всегда очень разреженная (в частности матрица для задачи с пентамино содержит всего 4 % единиц), и поэтому удобно представлять её в виде двумерного двусвязного списка. Такое представление позволяет нам за минимальное время получать все ненулевые элементы строки или столбца.

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

// Удаление элемента
node->next->prev = node->prev;
node->prev->next = node->next;

// Восстановление элемента
node->next->prev = node;
node->prev->next = node;


Именно на этой идее и основан метод танцующих ссылок Кнута. (Кстати, если ввести в гугл название этого метода в единственном числе «dancing link», то в картинках будет много гифок с главным героем Legend of Zelda.)

Решение головоломки


Окончательный код решения исходной головоломки можно посмотреть на гитхабе (большую часть кода занимает подготовка матрицы и функции проверки решений на идентичность). На моём ноутбуке программа за 5 секунд находит 4 уникальных решения (не приводимых друг к другу поворотами и отражениями) и в течение ещё 50 секунд убеждается, что других нет. Было приятно осознать, что твоя реализация работает быстрее, чем решение Burr Tools.


Одна из оптимизаций алгоритма заключалась в том, чтобы оставить только 2 принципиальных положения пентаминошки, закрывающих кубик (0, 0, 0), так как остальные её возможные положения являются поворотами и отражениями. Это уменьшало количество вариантов перебора в 6 раз. (На самом деле, достаточно оставить одно положение, но это нуждается в дополнительном обосновании).

Решение этой (и других головоломок) можно найти на сайте puzzlewillbeplayed.com. А тем, кто дочитал до конца, — бонус в виде визуализации кусочка работы алгоритма. Возможно, этой анимацией будет оправдано прилагательное «танцующий» в названии алгоритма.

Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 14
  • +9
    Всеобщее молчание и в закладках уже у 20 человек — и добавить нечего, и полезно, и красиво. Спасибо!
    • +1
      Пожалуйста :-)
    • +1
      Отличная статья, спасибо.
      • +1
        Кстати, может кому-то понадобится, я тоже недавно накидал имплементацию алгоритма x на C# с использованием пляшущих ссылок и эвристикой, которую предлагает Кнут в своей работе.
        • +1
          Посмотрел на Ваш код, вы без эвристики столбцы выбираете. Кнут советует выбирать столбец с минимальным количеством единиц, чтобы минимизировать ветвления.
          • +4
            При всём уважении, мне кажется, вы не очень внимательно его смотрели.

            /* select column with mininimal number of elements */
            Col *select_col(){
              int min = cptr->length;
              Col *col = cptr->right, *mc = cptr;
              while(col != cptr){
                if(col->length < min){
                  mc = col;
                  min = col->length;
                }
                col = col->right;
              }
              return mc;
            }
            
            • +1
              Да, прошу прощения, не внимательно посмотрел routineX(), выего оттуда вынесли в select_col(), потому бегло посмотрев не увидел.
          • +4
            Танцующие ссылки — интересно. Алгоритм — банальный перебор с возвратом.
            • +1
              Хороший алгоритм. Я попробовал реализовать его на битовых масках, а не на списках. Итог — 180 строк, 12 секунд (на i7, 2.9 GHz).
              Код здесь.
              Интересно, что будет, если фигуры разные. Это должна получиться матрица примерно 150*24000? (дополнительные 25 столбцов — на идентификаторы фигур). Боюсь, что работать будет уже не так быстро…
              • 0
                Важно не только количество строк, но и как быстро они уходят (мы здесь считаем, что удалять строки проще, чем перебирать варианты). Если всего фигур n, то каждая итерация будет удалять ~1/n часть строк. В частности с двумерными пентаминошками задачи по заполнению фигуры разными доминошками считаются быстрее, чем одинаковыми. Матрица в первом случае больше, зато дерево решений не так ветвится.
                • +1
                  Написал сборку параллелепипеда 4*5*7 из 28 пентакубиков (всех, кроме отрезка 5*1*1). Первые решения программа нашла мгновенно, но всё дерево перебирает не быстро (уже есть 20000 решений и счёт продолжается...) Так что дерево очень даже ветвится.
                  Интересный эффект — алгоритм сам выбирает, что делать на очередном шаге — попытаться заполнить какую-нибудь клетку возможными способами, или выбрать какую-нибудь фигуру и перебрать все возможные её расположения. Я его этому не учил…
              • 0
                Торт!
                • +1
                  Чертовски интересно, особенно если фигуры будут неправильной формы и трёхмерные. Дух захватывает от перспектив быстрого решения подобных задач. Если есть ссылки на подобные решения был бы очень благодарен.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.