我一直在研究数独求解器，我现在的求解器使用回溯算法，但它仍然需要很长时间。
我希望在大多数情况下将其降低到不到一秒钟。因此，我决定使用跳舞链接算法重写它，理解它是更好的强力方法之一，特别是对于诸如Sudoku Puzzle之类的约束问题。
我试图阅读Wiki和Knuth's paper，但是它们都很难理解并且非常冗长。
我还阅读了Sudopedia的版本，似乎一旦它进入数独的实现，它就太抽象了。
有人可以尝试解释Dancing Links算法，而不是根据其推导而是实现吗？ （以Sudoku为例非常棒）
谢谢！
您可能感兴趣的my implementation in javascript。
首先，您必须了解Exact Cover。一个确切的覆盖问题是一个问题，你给了一堆选择，一组约束和你的挑战是选择一堆选项，将恰好填充每个约束一次。
例如，考虑某人创建他们的冰舞例程的情况。他们需要向法官展示一些技巧，并且不想多次执行任何技巧。他们有许多序列，这些序列可以放在一起，他们想要选择理想的序列选择来覆盖所有的技巧。在这个例子中，约束是它们必须执行每个技巧。选择是他们可以在日常工作中加入的可能序列。
表示此类问题的一种很好的方法是绘制一个表，其中约束是列，选择是行，并且在单元格中有一个大的X，其中特定选项满足该约束。
事实证明，给定正确的约束和选择，数独可以被描述为精确封面问题。
好吧，假设你有这个，现在你需要理解算法X.Knuth说它“算法X只是一个明显的试错方法的陈述。（事实上，我想不出任何其他合理的一般来说，做这项工作的方式。）“。所以这是我对算法X的描述：
既然你明白了，你就可以理解舞蹈链接。 Dancing Links是一种有效实现该算法的方法。跳舞链接的关键点是，在链接列表中，当您删除节点（可以通过修改其邻居的指针来有效地完成）时，您删除的节点具有将其添加回来所需的所有信息链接列表（如果你猜到它是解决方案的一部分，那么事实证明你错了）。如果你把所有的链接列表变成圆形，然后突然你丢失了许多特殊情况，那么几乎所有的跳舞链接都是如此。
虽然这个问题很老，但我想我会补充：
这个页面使算法很容易理解：Zendoku writeup。直到我在那个链接上阅读它，我才认为这必须是一个超级先进的算法，但实际上一旦你可以想象它，它只是一个非常巧妙但简单的解决方案。
此外，C＃中的my implementation应该相当容易阅读...将有助于将各种类分成不同的文件，我敢肯定。 它主要是来自Knuth的pdf的直接实现，但是有一些面向对象的优化（实际上，因为几个月前我这样做了，我不太记得我从PDF中偏离了多少）