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