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

Предисловие

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

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

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

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

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

Данная головоломка является классическим представителем задачи о точном покрытии.

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

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

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

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

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

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

Алгоритм X

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

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

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

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

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

Шаг 3. Для выбранной строки r, рассматриваются все столбцы j, такие что S_r,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. А тем, кто дочитал до конца, — бонус в виде визуализации кусочка работы алгоритма. Возможно, этой анимацией будет оправдано прилагательное «танцующий» в названии алгоритма.