新学的东西，然而除了用来做数独以外并没有什么卵用。
考虑一个01矩阵，要从中选出若干行，使得每列上恰好有一个1。这类问题被称为精确覆盖问题。
很容易想出一个简单的搜索算法：
- 寻找一个1最少的列，删除一个在该列上有1的行（表示已经选了这一行）；
- 删除除了选中行以外在该列上有1的行（因为不能再选它们了）；
- 删除在选中行上有1的列（已经覆盖了）和除了选中行以外在这些列上有1的行（同样不能选了）；
- 重新执行第一步。
反复执行这个算法直到所有列都被删除就可以了。
但是这里有一个问题，需要有方法高效地删除或恢复矩阵中的行列。如果每次递归都处理出一个新矩阵，显然时间和空间都不能承受。
这里就需要用到一个奇怪的东西——舞蹈链（Dancing Links）。
舞蹈链是Knuth提出的专门用来解决这个问题的数据结构，它实际上就是一个双向十字交叉链表（自行感受
）。
把矩阵中的所有1用链表串起来，并对每一列的开头分别用一个辅助节点表示（用数组存起来）。删除列时就可以直接把对应列头节点的左右节点连起来，删除行时则把该行所有节点的上下节点连起来。这样这些行列在没有被删除的列里就访问不到了，而实际上这些节点都还存在，通过列头节点就可以访问，恢复时只须把节点的指针恢复。
下面给出删除和恢复给定列头节点所在列及其对应行的代码。
http://www.cnblogs.com/grenet/p/3145800.html
这个博客里有对整个算法流程的详细描述（真的非常详细，每一步都有图）。
http://poj.org/problem?id=3740 代码
一道模板题。
数独可以转化为一个精确覆盖问题来解，这应该也是目前数独最快的解法了。
每行都表示在某个格子填上某个数字（初始时已经填好数的格子用一行表示，没有填的用n行表示）。
然后每列表示一个限制，共有4种限制，每种限制需要$n^2$个列。
- 每个格子恰好填一个数字。每列都表示在某个格子填了数字。
- 每行1~n都恰好出现一次。每列都表示在某行填了某个数字。
- 每列1~n都恰好出现一次。方法同2。
- 每个小方块1~n都恰好出现一次。方法同2。
按照给出的数独问题构造对应的矩阵即可求解。注意这里有一个小优化，可以在搜索前直接删除已经填好数字的方格对应的行以及这些行对应的行列。不过我的代码没有加这个优化，因为懒得改了。。。
这里给出3道数独的例题，其中2道是9×9的，1道是16×16的。
http://poj.org/problem?id=2676 代码
评论 (0)
