最近想做一个解数独的小软件，基于对话框的。但是我发现用以前回溯写的解数独程序速度实在太慢了。后来在网上搜到可以用dancinglinks算法优化，dancinglinks算法以前接触过，粗浅的理解过，在这里有一篇文章。刚开始我想应该怎样将数独转换成一个精确覆盖问题，从2*2的小数独开始入手。想过很多方法，但是终究不得要点。最后在网上找到了将数独转换成一个324列，729行的精确覆盖问题。但是这两个数字是怎样得来的？一时理解不了，最后在一个地方看到：可以使用列表达数独的约束条件，使用行表示可能性。亦即81列表示每个位置的数是否填好，81列表示每行的某个数是否填好，81列表示每列（别混淆）的某个数字是否填好，81列表示每个3*3的九宫格某个数字是否填好。所以需要81+81+81+81=324列。每个位置有9种可能性，所以一共有81*9=729个可能，每行表示一种可能性。需要729行。每行有4个元素（4列），分别属于上面不同的81列中的其中。
可以转换成精确覆盖问题了，但是怎样收集它的答案呢?因为在唐纳德论文中的X算法是将答案的元素保存在了一个数组中，然后打印元素的名字就可以了。但是在数独问题中我们需要的是81个确切的数字。怎么办呢？刚开始我的方法和X算法中的一样，将答案保存在一个数组中，再解完题目后在从它的列信息中提取出数字。但是程序运行后我才发现数字完全乱了，a数在位置b，但是解完之后a数不知道到什么地方去了。后来在网上找到一个方法。将每种可能性（每行）的数字保存在一个数组Q中，将每个元素所在的行保存数组X中，然后使用一个visit数组，初始化为0。将答案的行保存在visit中（从X中我们知道了每个元素的行所在），然后根据visit数组和Q打印答案就可以了。在这里不需要担心数字混乱的问题。因为在构建精确覆盖问题的时候我们是从题目的开头向下构建行（可能性），每个位置占9行，而答案是每9行必有一个，否则就不符合题意也就是无解。将visit的访问顺序从小到大访问，我们得到的就是正确的顺序。
基础的理论懂了（dancinglinks X算法的我还是没怎么理解），就要实现代码了。刚开始我自己写了一个代码，出了很多错，尤其是答案的保存。有些题目还解不出来，而且速度极慢。我确认我的X算法是没有错的，有问题的只能在转换成精确覆盖问题的那个步骤了。后来自己按照从网上找到的代码再写了一份，就正常了。这里发现一个问题，我每次都是不事先设计好就写代码。这样的问题是有时候不知道怎么写了。而且容易回头修改代码。所以得出一个经验，先打好腹稿再动手。
感觉自己在编程风格上也有很大的问题，再函数的和变量的命名上在不同的程序中表现不同。有时候用大写有时候用下划线，最后我自己都不懂代码写的什么了。：（
最后要感谢伟大的互联网及那些代码和算法的作者，让我从中学到很多东西。如果你想要具体的C代码的话，自己google吧。：）
（全文完）
若非注明，均为原创文章，转载请注明： 转载自大笨兔
本文链接地址: DancingLinks 算法解数独
