среда, 6 апреля 2011 г.

Танцующие звенья (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) в том виде, в котором он изложен здесь, работает недостаточно шустро. Если у кого есть идеи по решению этой задачи, будет интересно услышать.

2 комментария:

  1. К сожалению, Ваш код при запуске теста со spoj выдает exception под Windows. Сколько примерно выполняется тест со spoj? Мой java вариант решает его примерно за 700 ms на C2D E7200 3GHz

    ОтветитьУдалить
  2. Если речь идет о задаче SUDOKU(16*16), то я меняю в приведенном исходнике N = 16 и EMPTY = '-' - и exception у меня не появляется. Использую родной компилятор С++ VS 2008. Что же касается времени работы, то здесь ситуация плачевна) Прождав минуту, программа продолжала работать.

    Убедившись, что реализация рабочая для судоку 9*9, я больше и рассматривал метод "Танцующих звеньев", как эффективный. Но если Ваша реализация такая шустрая, значит нужно у себя подумать, откуда такие тормоза.

    ОтветитьУдалить