我一直在研究数独求解器，我目前的求解器使用回溯算法，但仍然需要很长时间。
在大多数情况下，我希望将其降低到不到一秒。因此，我决定用跳舞链接算法重写它，理解它是更好的蛮力方法之一，尤其适用于数独难题等约束问题。
我试图阅读 Wiki 和Knuth 的论文，但是它们都很难理解并且非常冗长。
我还阅读了 Suododia 的版本，似乎一旦进入数独的实现，它就变得太抽象了。
有人可以尝试解释 Dancing Links 算法，而不是根据它的推导而是它的实现吗？（以数独为例会很棒）
谢谢！
问问题
33744 次
2 回答
31
您可能对我在 javascript 中的实现感兴趣。
首先，您必须了解 Exact Cover。精确覆盖问题是一个问题，你有一堆选择，一组约束，你的挑战是选择一堆选项，这些选项将恰好满足每个约束一次。
例如，考虑某人创建他们的冰舞程序的情况。他们有许多技巧需要向评委展示，并且不想多次表演任何技巧。他们有许多序列，这些序列是可以组合在一起的技巧组，他们希望选择理想的序列选择来覆盖所有技巧。在这个例子中，约束是他们必须执行每一个技巧。选择是他们可以纳入日常活动的可能序列。
表示此类问题的一个好方法是绘制一个表格，其中约束是列，选择是行，并且在特定选择满足该约束的单元格中有一个大 X。
事实证明，给定正确的约束和选择，数独可以描述为精确覆盖问题。
好吧，假设你已经明白了，现在你需要了解算法 X。Knuth 说：“算法 X 只是对明显的试错方法的陈述。（事实上，我想不出任何其他合理的方法）一般来说，完成这项工作的方法。）”。所以这是我对算法 X 的描述：
- 如果您的表格没有列，请停止 - 您已经解决了。如果您存储了部分解决方案，那么它实际上是一个真正的解决方案，请将其退回。
- 选择一列（代表一个约束）。
- 在该列中找到带有叉号的行（表示满足该约束的选择）。将其添加到存储潜在解决方案的某种结构中。如果找不到行，请放弃 - 没有解决方案。
- 假设您在 3 中找到的行在解决方案中，因此删除该行中包含 X 的所有列。在删除所有这些列的同时，还要删除在您要删除的列中具有 X 的所有行（因为您已经满足了约束，所以您被禁止选择能够再次满足它的东西）。
- 现在递归地尝试解决简化表。如果不能，请从潜在的解决方案结构中删除您尝试过的行，恢复您在第 3 步和第 4 步中删除的所有行和列，然后尝试不同的行。如果你用完了行，那就放弃吧——没有解决办法。
既然你明白了，你就可以理解跳舞的链接了。Dancing Links 是一种有效实现该算法的方法。跳舞链接的关键在于，在链表中，当您删除一个节点时（可以通过修改其邻居的指针来有效地完成），您删除的节点具有您需要将其添加回来的所有信息到链表（如果你猜到它是解决方案的一部分时你错了）。再加上如果你把所有的链表都做成循环的，那么你会突然失去很多特殊情况，这几乎就是所有的跳舞链接。
于 2012-05-08T22:29:44.753 回答
23
虽然这个问题很老，但我想我会补充：
这个页面使算法很容易理解：Zendoku writeup。直到我在那个链接上读到它，我一直认为这一定是一个超级高级的算法，但真的一旦你可以想象它，它只是一个非常巧妙但简单的解决方案。
此外，我在 C# 中的实现应该相当容易阅读......我确信将有助于将各种类拆分为不同的文件。
它主要是 Knuth 的 pdf 的直接实现，但有一些面向对象的优化（实际上，自从几个月前我这样做以来，我不太记得我偏离了 pdf 多少）
于 2013-04-18T03:44:28.747 回答