algorithm - The Dancing Links Algorithm - 一种解释性较差但更多关于实现的解释？

Question

我一直在研究数独求解器，我目前的求解器使用回溯算法，但它仍然需要很长时间。

在大多数情况下，我希望将时间缩短到不到一秒。因此，我决定用 dancing links 算法重写它，理解它是更好的暴力破解方法之一，尤其适用于数独难题等约束问题。

我尝试阅读 Wiki 和 Knuth's paper在上面，但是它们都有点难以理解并且非常冗长。

我也看了数独的版本，好像到了数独的实现，就太抽象了。

有人可以尝试不根据推导而是根据实现来解释 Dancing Links 算法吗？ (以数独为例会很棒)

谢谢!

Answer 1

您可能对 my implementation in javascript 感兴趣.

---

首先你必须了解Exact Cover。精确覆盖问题是给你一堆选择和一组约束的问题，你的挑战是选择一堆将恰好满足每个约束一次的选项。

例如，考虑某人创建他们的冰舞套路的情况。他们有许多技巧需要向评委展示，并且不想重复表演任何技巧。他们有许多序列，这些序列是可以放在一起的技巧组，他们想要选择理想的序列选择来一次涵盖所有技巧。在这个例子中，约束是他们必须执行每一个技巧。这些选择是他们可以纳入日常工作的可能顺序。

表示此类问题的一个好方法是绘制一个表，其中约束是列，选择是行，并且在特定选择满足该约束的单元格中有一个大 X。

事实证明，给定正确的约束和选择，数独可以描述为精确覆盖问题。

---

好吧，假设你已经明白了，现在你需要理解算法 X。Knuth 谈到它“算法 X 只是一种明显的试错法的陈述。(事实上，我想不出一般来说，任何其他合理的方式来完成这项工作。)”。所以这是我对算法 X 的描述:

1. 如果您的表格没有列，请停止 - 您已经解决了它。如果您存储了部分解决方案，那么它实际上是一个真正的解决方案，请将其返回。
2. 选择一列(代表约束)。
3. 在该列中找到带叉号的行(代表满足该限制条件的选择)。将它添加到您存储潜在解决方案的某种结构中。如果找不到一行，请放弃 - 没有解决方案。
4. 假设您在 3 中找到的行在解决方案中，因此删除所有在该行中有 X 的列。在删除所有这些列的同时，还要删除在要删除的列中带有 X 的所有行(因为您已经满足了约束条件，所以您无法选择再次满足它的内容)。
5. 现在递归尝试解决简化表。如果不能，请从潜在的解决方案结构中删除您尝试过的行，恢复您在步骤 3 和 4 中删除的所有行和列，然后尝试不同的行。如果行数用完，则放弃 - 没有解决方案。

---

既然你明白了，你就可以理解舞蹈链接了。 Dancing Links 是一种有效实现该算法的方法。跳舞链接的关键点在于，在链表中，当您删除一个节点时(这可以通过修改其邻居的指针来有效地完成)，您删除的节点具有您需要添加回来的所有信息到链接列表(如果你猜它是解决方案的一部分，结果证明你错了)。再加上如果您将所有链接列表设为循环，那么突然之间您会丢失很多特殊情况，这几乎就是所有跳舞链接。