Алгоритм «Dancing Links» был предложен Дональдом Кнутом и может использоваться для решения задачи точного (полного) покрытия исходной матрицы. Основная задача «Dancing Links» заключается в том, чтобы найти все возможные способы выбора набора строк из данной матрицы, таких что бы в каждом столбце матрицы располагалась только одна ячейка со значением логической единицы, все остальные ячейки в столбце должны иметь значения логического нуля.
Алгоритм «Dancing Links» основан на структуре данных двусвязного циклического списка (косвенная адресация Кнута). Каждый элемент списка представляет собой непустую ячейку хранения информации, которая ссылается на соседние элементы в горизонтальном и вертикальном направлениях. Возможность эффективного удаления и восстановления элементов списков, делает алгоритм быстрым и эффективным.
Алгоритм «Dancing Links» может успешно применяться для решения различных комбинаторных задач, например, судоку, задача размещений N-ферзей и другие. Он также находит применение в различных научных областях, таких как искусственный интеллект и компьютерное зрение.
Ознакомится со статьей Дональда Кнута можно по ссылке: https://arxiv.org/pdf/cs/0011047v1.pdf
Статья с обзором Алгоритма Х на Хабре: https://habrahabr.ru/post/194410/
Использование алгоритма Дональда Кнута для решения задачи Пентамимо