Вас может заинтересовать моя реализация в javascript .
Во-первых, вы должны понять Точное покрытие. Точная проблема покрытия - это проблема, когда вам предоставляется набор вариантов, и набор ограничений, и ваша задача состоит в том, чтобы выбрать набор вариантов, которые будут заполнять каждое ограничение ровно один раз.
Например, рассмотрим случай, когда кто-то создает свою рутину танца на льду. У них есть целый ряд трюков, которые они должны показать судьям, и они не хотят выполнять какие-либо трюки более одного раза. У них есть несколько последовательностей, которые представляют собой группы трюков, которые можно собрать вместе, и они хотят выбрать идеальный выбор последовательностей, чтобы охватить все уловки один раз. В этом примере ограничения заключаются в том, что они должны выполнять каждый трюк. Выбор - это возможные последовательности, которые они могут включить в свою рутину.
Хороший способ представить проблемы такого рода - нарисовать таблицу, в которой ограничения - это столбцы, а выборы - строки, и у вас есть большой X в ячейках, где конкретный выбор удовлетворяет этому ограничению.
Как выясняется, учитывая правильные ограничения и выбор, судоку можно описать как проблему Точного Покрова.
Хорошо, предполагая, что у вас это есть, теперь вам нужно понять алгоритм X. Кнут сказал об этом: «Алгоритм X - это просто утверждение очевидного метода проб и ошибок. (Действительно, я не могу думать о любой другой разумный способ сделать работу, вообще.) ". Итак, вот мое описание алгоритма X:
- Если в вашей таблице нет столбцов, остановитесь - вы решили это. Если у вас есть частичное решение, то это действительно реальное решение, верните его.
- Выберите столбец (представляющий ограничение).
- Найдите строку с крестиком в этом столбце (представляющую выбор, который удовлетворяет этому ограничению). Добавьте его к какой-то структуре, где вы храните потенциальные решения. Если вы не можете найти строку, сдавайтесь - нет решений.
- Предположим, что строка, найденная в 3, находится в решении, поэтому удалите все столбцы, в которых есть X в этой строке. Удаляя все эти столбцы, также удалите все строки, которые имеют X в столбцах, которые вы удаляете (поскольку вы уже выполнили ограничение, поэтому вам запрещено выбирать что-то, что могло бы удовлетворить его снова).
- Теперь рекурсивно попытайтесь решить уменьшенную таблицу. Если вы не можете, удалите строку, которую вы пробовали, из структуры потенциального решения, восстановите все строки и столбцы, которые вы удалили в шагах 3 и 4, и попробуйте другую строку. Если у вас кончились строки, то сдавайтесь - решений нет.
Теперь, когда вы понимаете это, вы можете понимать танцевальные звенья. Dancing Links - это способ эффективной реализации этого алгоритма. Ключевым моментом танцующих ссылок является то, что в связанном списке, когда вы удаляете узел (что можно эффективно сделать, изменяя указатели на его соседей), удаленный вами узел имеет всю информацию, необходимую для его добавления обратно. к связанному списку (в случае, если окажется, что вы ошиблись, когда догадались, что это часть решения). Это плюс тот факт, что если вы сделаете все свои связанные списки круглыми, то внезапно вы потеряете много особых случаев - это почти все танцевальные ссылки.