我一直工作在一个数独解算器，我目前的解算器使用的回溯算法，但它仍然需要太长时间。
我希望得到它下降到不到一秒钟在大多数情况下。 因此，我决定用舞蹈链算法重写它，理解它是更好的方法，暴力破解与约束问题，比如数独题尤其是效果很好的。
我曾尝试阅读维基和Knuth的纸就可以了，但是他们两人都有点难以理解和非常详细。
我也阅读它Sudopedia的版本，它似乎是一旦到了数独的实现，它有太多的抽象。
有人可以尝试在它的推导，但其实施方面没有解释跳舞链接的算法？ （将是巨大的使用数独为例）
谢谢！
Answer 1:
您可能会感兴趣我的JavaScript实现 。
首先，你必须了解精确覆盖。 恰当覆盖问题是你们给了一堆的选择问题，以及一组约束，你的挑战是选择一堆，将填补每一个约束恰好一次的选择。
例如，考虑别人创造他们的冰舞程序的情况下。 他们有一个数字，他们需要展现法官的技巧，而不愿意进行任何伎俩不止一次。 他们有一个数量的，技巧的团体，可以放在一起序列，他们要选择序列的理想选择，以涵盖所有的招数一次。 在这个例子中，约束条件是，他们必须执行每招。 选用的是，他们可以纳入他们的日常可能的序列。
代表这种问题的最好方法是画了一个表，其中约束列和选择是行，你必须在细胞中的大X，其中一个特别的选择满足该约束。
事实证明，只要有正确的约束和选择，数独，可谓恰当覆盖问题。
好吧，假设你已经有了，现在你需要了解算法X.克努特说的是“算法X简直是明显的试错法的声明。（事实上，我想不出任何其他合理的这样做的工作，一般。）”。 因此，这里是我的算法X的说明：
- 如果你的表没有列，停 - 你已经解决了它。 如果你有存储的部分解决方案，那么它实际上是一个真正的解决方案，将其返回。
- 选择（代表约束）的列。
- 找到在该列（表示满足该约束的选择）交叉的行。 将它添加到某种结构，在那里你要存储的潜在解决方案。 如果你不能找到一排，就放弃了 - 有没有解决办法。
- 假设你在3找到行是在溶液中，因此将其删除，它有行中的X中的所有列。 虽然删除所有这些列，也删除在您删除列的X中的所有行（因为你已经满足了约束，所以你从选择的东西，将再次满足它禁止）。
- 现在递归地尝试解决减小的表。 如果不能，删除您从潜在的解决方案结构试过行，恢复所有你在步骤3和4取出的行和列，并尝试不同的行。 如果您运行的行，然后放弃了 - 有没有解决办法。
现在你明白这一点，你可以理解舞蹈链。 舞蹈链是有效实现该算法的一种方式。 舞蹈链的关键点是，在一个链表，当你删除一个节点（可以efficently通过修改其邻居的指针做），你已经删除的节点有你需要重新添加的所有信息到链表（因为它证明你是错误的，当你猜它是解决方案的一部分的情况下）。 这加上如果你让你的所有链接的列表循环，然后你突然失去了很多的特殊情况下的事实是，几乎所有的舞蹈链接是。
Answer 2:
虽然这个问题很老了，我想我要补充：
此页面使得算法很容易理解： Zendoku书面记录 。 直到我在这个链接读到它，我还以为这一定是一个超级先进的算法，但真的一旦你可以想像它，它只是一个非常巧妙的，但简单的解决方案。
另外我的实现在C＃应该是相当容易阅读...会有帮助到不同的文件，我敢肯定，分裂的各种类。
这在很大程度上是由Knuth的PDF直接实现，但有一些面向对象的优化（实际上是因为我在几个月前做这个我不太记得我从PDF多少误入）
文章来源: The Dancing Links Algorithm - An explanation that is less explanatory but more on implementation?
