跳舞链接算法 - 解释较少解释但更多的实施？

Question

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

我希望在大多数情况下将其降低到不到一秒钟.因此,我决定使用跳舞链接算法重写它,理解它是更好的强力方法之一,特别是对于诸如Sudoku Puzzle之类的约束问题.

我试图阅读Wiki和Knuth的论文,但是它们都难以理解并且非常冗长.

我还阅读了Sudopedia的版本,似乎一旦它进入数独的实现,它就太抽象了.

有人可以尝试解释Dancing Links算法,而不是根据其推导而是实现吗？(以Sudoku为例非常棒)

谢谢!

Answer 1

您可能对我在javascript中的实现感兴趣.

首先,您必须了解Exact Cover.一个确切的覆盖问题是一个问题,你给了一堆选择,一组约束和你的挑战是选择一堆将完全填充每个约束的选项.

例如,考虑某人创建他们的冰舞例程的情况.他们需要向法官展示一些技巧,并且不想多次执行任何技巧.他们有许多序列,这些序列可以放在一起,他们想要选择理想的序列选择,以涵盖所有的技巧.在这个例子中,约束是它们必须执行每个技巧.选择是他们可以在日常工作中加入的可能序列.

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

事实证明,给定正确的约束和选择,数独可以被描述为精确封面问题.

好吧,假设你有这个,现在你需要理解算法X.Knuth说它"算法X只是一个明显的试错方法的陈述.(事实上,我想不出任何其他合理的一般来说,做这项工作的方式.)".所以这是我对算法X的描述:

1. 如果您的表没有列,请停止 - 您已经解决了.如果您已经存储了部分解决方案,那么它实际上是一个真正的解决方案,请将其返回.
2. 选择一列(表示约束).
3. 在该列中找到一个带十字的行(表示满足该约束的选项).将它添加到某种存储潜在解决方案的结构中.如果你找不到一排,就放弃 - 没有解决方案.
4. 假设您在3中找到的行在解决方案中,因此请删除该行中包含X的所有列.在删除所有这些列的同时,还要删除所有要删除的列中包含X的行(因为您已经满足了约束,因此您被禁止选择能够再次满足它的内容).
5. 现在递归尝试解决缩减表.如果不能,请从潜在的解决方案结构中删除您尝试的行,还原在步骤3和4中删除的所有行和列,然后尝试使用其他行.如果你用完了行,那就放弃 - 没有解决方案.

既然你明白了,你就可以理解舞蹈链接.Dancing Links是一种有效实现该算法的方法.跳舞链接的关键点是,在链接列表中,当您删除节点(可以通过修改其邻居的指针来有效地完成)时,您删除的节点具有将其添加回来所需的所有信息链接列表(如果你猜到它是解决方案的一部分,那么事实证明你错了).如果你把所有的链接列表变成圆形,然后突然你丢失了许多特殊情况,那么几乎所有的跳舞链接都是如此.

Answer 2

虽然这个问题很老,但我想我会补充:

该页面使算法非常容易理解:Zendoku写作.直到我在那个链接上阅读它,我才认为这必须是一个超级先进的算法,但实际上一旦你可以想象它,它只是一个非常巧妙但简单的解决方案.

此外,我在C#中的实现应该相当容易阅读...将有助于将各种类分成不同的文件,我敢肯定.
它主要是来自Knuth的pdf的直接实现,但是有一些面向对象的优化(实际上,因为几个月前我这样做了,我不太记得我从PDF中偏离了多少)