Танцующие звенья (Dancing Links)

Данный алгоритм решает задачу полного покрытия (cover).

Для начала можно ознакомится со следующими статьями:
- Реализация на С и описание (Xi Chen)
- Разжованное описание + базовые операции с элементами списка

В общем случае задача полного покрытия выглядит так:
Имеется набор битовых строк

A[0] = 100101
A[1] = 101000
A[2] = 011011

Необходимо выделить набор, состоящий из одной или нескольких исходных битовых строк, такой что после операции логического ИЛИ всех элементов этого набора, получилась единичная битовая строка. Т.е. в примере набор может состоять из элементов A[0] и A[1].

Рассмотрим применения алгоритм Dancing Links отностительно решения Судоку.

Итак задача формулируется следующим образом:
1) Имеется квадратное поле размером 9 на 9 (81 клетка). В каждой клетке находится цифра в интервале [1,9]
2) В каждой строке не должно быть повторяющихся цифр.
3) В каждом столбце не должно быть повторяющихся цифр.
4) В каждом блоке (см. рисунок) не должно быть повторяющихся цифр.

Задача расставить недостающие цифры так, чтобы выполнялись вышестоящие 4 правила. 

Сведем задачу решения судоку к задаче решения полного покрытия.
Для этого давайте рассмотрим судоку 4 на 4 с аналогичными правилами.

Рассмотрим таблицу №1, которая прояснит момент получения битовых строк для задачи полного покрытия.
Строки матрицы – это кандидаты на решение (вспоминаем общую формулировку задачи полного покрытия)
Столбцы матрицы – это требования к решению.

На каждую клетку можно поставить любое значение в интервале [1,9], т.е. получается всего N*N*N возможных решений.

Разберемся теперь с требованиями. Всего существует 4 вида требований:
1. Каждая строка должна  иметь все числа от 1..N = N * N требования
2. Каждый столбец должен иметь все числа от 1..N = N * N требования
3. Каждый квадрат должен иметь все числа от 1..N = N * N требования
4. Каждая клетка судоку должна иметь уникальное значение в интервале от 1..n. Другими словами если в клетке [i,j] находится число k, то нужно исключить из рассмотрения оставшиеся N-1 значения не равные k = N * N требования

Таким образом мы имеем 4*N*N требований.

Для случая 4*4 имеем матрицу размерностью [64 на 64]. Теперь вникаем в суть как заполняется матрица. Это можно сделать самостоятельно последовательно рассмотрев все строки сверху вниз.

Допустим начальная расстановка такая:

1---
----
----
----

Чтобы это отразилось на рассматриваемой матрице необходимо найти строку(0) решения, которая соответствует введенному значению.
Затем необходимо выполнить операцию Cover. А именно занулить эту строку + все столбцы, которые пересекает данная строка + все строки, которые пересекают столбцы. Чтобы понять эту игру слов анализируем таблицу №2.

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

Если присмотреться к матрице, то можно заметить, что в каждой строке и столбце находится N единиц. Поэтому следующей нашей задачей будет формирования сжатой копии матрицы в виде, представленном выше. Это дело техники, поэтому не будем останавливаться на этом подробно. Отмечу только один факт, что для отладки я немного модернизировал вывод матрицы, добавив в него вывод последних трех цифр адреса узла в памяти. Смотрим таблицу №3.

Теперь сформулируем процесс нахождения решения.
1. Последовательно перебираем требования начиная с root. Если на текущем шаге не осталось требований, значит нужно проверить получившееся решение на корректность.
2. Для каждого требования пытаемся использовать строку-решение, с которой пересекается данный столбец.
3. Для каждой такой строки выполняем операцию Cover, тем самым исключая не нужные элементы из последующего рассмотрения.
4. Рекурсивно переходим в новое состояние – новое требование.
5. (После выхода из рекурсии) восстанавливаем состояние до вызова функции Cover и пытаемся использоваться следующее решение.

Как можно заметить вышеописанный алгоритм не что иное как Backtracking. Но в отличии от обычного, здесь нахождение следующего корректного кандидата составляет O(1) вместо O(N). Операция Cover и обратная ей также выполняется за O(1). Тем самым обеспечивается быстрота, заявленная в начале поста.

Мои наработки находится в этом исходнике.

P.S.: Вообще взялся за этот алгоритм с одной целью. Зачесть задачу, в которой нужно собрать судоку 16*16. Но как показала практика, DLX(Dancing Links) в том виде, в котором он изложен здесь, работает недостаточно шустро. Если у кого есть идеи по решению этой задачи, будет интересно услышать.