跳舞链接算法 - 一种解释性较少但更多关于实现的解释？
我一直在研究数独求解器，我当前的求解器使用回溯算法，但仍然需要很长时间。
我希望在大多数情况下将其减少到不到一秒。因此，我决定用跳舞链接算法重写它，了解它是更好的暴力方法之一，尤其适用于数独谜题等约束问题。
我尝试阅读维基百科和Knuth 的论文 ，但是它们都有点难以理解并且非常冗长。
我还阅读了 Supedia 的版本，似乎一旦涉及数独的实现，它就变得太抽象了。
有人可以尝试解释 Dancing Links 算法而不是其推导而是其实现吗？ （如果能用数独作为例子就好了）
谢谢！
I've been working on a Sudoku Solver, my current solver uses the backtracking algorithm but it still takes too long.
I'm hoping to get it down to less than a second for most cases. As such, I've decided to rewrite it with the dancing links algorithm, understanding it is one of the better bruteforce methods that works well especially with a constraint problem such as the Sudoku Puzzle.
I have tried to read the Wiki and Knuth's paper on it, however both of them are kinda hard to comprehend and extremely verbose.
I also read Sudopedia's version on it, and it seems that once it got to the Sudoku's implementation, it got too abstract.
Can someone try to explain the Dancing Links algorithm not in terms of its derivation but its implementation? (would be great to use the Sudoku as an example)
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可能对我的 JavaScript 实现感兴趣。
首先你必须了解精确覆盖。精确覆盖问题是一个给你一堆选择和一组约束的问题，你的挑战是选择一堆能够一次满足每个约束的选项。
例如，考虑某人正在创作冰舞动作的情况。他们有很多技巧需要向评委展示，并且不想重复表演任何技巧。他们有许多序列，这些序列是可以组合在一起的技巧组，并且他们希望选择理想的序列选择来一次涵盖所有技巧。在这个例子中，限制是他们必须执行每一个技巧。这些选择是他们可以纳入日常工作的可能顺序。
表示此类问题的一个好方法是绘制一个表，其中约束是列，选择是行，并且在单元格中有一个大 X，其中特定选择满足该约束。
事实证明，在给定正确的约束和选择的情况下，数独可以被描述为精确覆盖问题。
好吧，假设你已经明白了，现在你需要理解算法 X。 Knuth 谈到它时说：“算法 X 只是对明显的试错方法的陈述。（事实上，我想不出任何其他合理的方法）一般来说，完成这项工作的方式。）”。所以这是我对算法 X 的描述：
现在你明白了这一点，你就可以理解跳舞的链接了。 Dancing Links 是一种有效实现该算法的方法。跳舞链接的关键点在于，在链表中，当您删除一个节点（可以通过修改其邻居的指针来有效地完成）时，您删除的节点拥有将其添加回来所需的所有信息到链接列表（如果你猜测它是解决方案的一部分，结果证明你错了）。再加上如果你让所有的链接列表都是循环的，那么你会突然失去很多特殊情况，这几乎就是所有跳舞链接的情况。
You might be interested in my implementation in javascript.
Firstly you have to understand Exact Cover. An exact cover problem is a problem where you're given a bunch of choices, and a set of constraints and your challenge is to select a bunch of the choices that will fill every constraint exactly once.
For example, consider the case of someone creating their ice dance routine. They have a number of tricks that they need to show the judges, and don't want to perform any trick more than once. They have a number of sequences which are groups of tricks that can be put together and they want to choose the ideal selection of sequences to cover all the tricks once. In this example, the constraints are that they must perform every trick. The choices are the possible sequences they could incorporate into their routine.
A nice way to represent problems of this sort is to draw out a table where the constraints are columns and the choices are rows, and you have a big X in cells where a particular choice fulfills that constraint.
As it turns out, given the right constraints and choices, sudoku can be described as an Exact Cover problem.
Ok, assuming you've got that, now you need to understand Algorithm X. Knuth said of it "Algorithm X is simply a statement of the obvious trial-and-error approach. (Indeed, I can’t think of any other reasonable way to do the job, in general.)". So here's my description of algorithm X:
Now that you understand that, you can understand dancing links. Dancing Links is a way of implementing that algorithm efficiently. The key point of dancing links is that in a linked list, when you remove a node (which can be done efficently by modifying the pointers of its neighbours), the node that you've removed has all the information you need to add it back to the linked list (in the case that it turns out you were wrong when you guessed it was part of the solution). That plus the fact that if you make all your linked lists circular then suddenly you lose a lot of special cases is pretty much all dancing-links is.
虽然这个问题很老，但我想我应该添加：
此页面使算法非常容易理解：Zendoku 文章。直到我在该链接上读到它之前，我一直认为这一定是一个超级先进的算法，但实际上一旦你可以想象它，它只是一个非常巧妙但简单的解决方案。
另外，我在 C# 中的实现应该相当容易阅读...将有助于将各种类拆分到不同的文件中我确定。
它很大程度上是 Knuth 的 pdf 的直接实现，但有一些面向对象的优化（实际上，自从我几个月前这样做以来，我不太记得我偏离了 pdf 多少）
Although this question is very old, I thought I'd add:
This page makes the algorithm very easy to understand: Zendoku writeup. Until I read about it at that link, I had thought this must be a super advanced algorithm, but really once you can visualize it, its just a really ingenious but simple solution.
Also my implementation in C# should be fairly easy to read... would be helpful to split the various classes out to different files I'm sure.
It is largely a direct implementation from Knuth's pdf, but with a few object orientated optimizations (actually since I did this a few months ago I don't quite remember how much I strayed from the pdf)