文中提及的一些观点和理论，并非全部个人原创，而是自己的总结和心得， 仅供个人学习编程使用！

Dancing Links（DLX），又 被直译为“神奇的舞蹈链”，本质是一个“双向十字循环链表”！是由斯坦福大学的康纳德 E.Knuth在2000年左右提出的一个解决一种NPC问题的算法！对我们acm的竞赛来说，在处理一类搜索问题时，十分有用。

先分享一下学习这种算法比较好的几份资料：

1. 《Dancing Links》 （Donald E. Knuth）本人的论文。英文版的，也有中文的，而且翻译的也很到位: http://sqybi.com/works/dlxcn/#p11#p11

2.《Dancing Links在搜索中的应用》 （momodi）momodi的这篇文章比较系统的讲述了dlx的原理及处理Exact Cover Problem 和 重复覆盖的方法。

依据做过的题目的特点，在简单描述过dlx的插入和删除的方法之后，结合相应的题目，讲一下自己对“完美覆盖（棋盘问题，数独（sudoku）问题，N皇后问题）” 和 “重复覆盖”的理解。

dlx的节点的存储结构：用结构体来表示：

dlx的节点的删除

dlx的节点的恢复

除此之外，为了遍历的方便，要设置一个总的头节点的head!

完美覆盖（精确覆盖）模型

给定一个0-1矩阵，现在要选择一些行，使得一列有且仅有一个 1，如下左：

取行集合｛1， 4， 5｝便可以使得每一列仅有一个1。如果我们把行集合｛2， 3， 6｝删掉，并用不同的染色将剩余的行中列为1的标记出来，那么就会得到一个一个完全覆盖的board。这也是这个题目的算法的大体思路：任意选择一列（这里我们先选择任意一列，待会再说如何优化），选择为1的一行，然后将该从该行中找出所有的节点值为1的节点，将这些节点所在的列中节点为值为1的行删除掉，这样我们就可以保证选择了改行之后，保证每列中只有一个1。
这样将所有的行试探之后，如果最后存在一种可以使得原矩阵为空的方案，那么就找到一组解。下面简单说一下对优化（即，每次选择剩余列中元素个数最少的来删除）的理解，

我们优化的出发点是选择尽量少的行找到一组可行解，按照我们上面的思路就是选择一行的同时尽量多的删除其它的行。由此，列的值（多少代表着影响的行数）大的删掉的行数也就越多，那么就更大的可能接近可行解。（只是论述，缺乏严密的数学证明）（更为具体的分析，参见momodi的论文P4，下面附上一段伪代码,帮助理解）

完美覆盖的cpp实现。

重复覆盖模型：在0-1矩阵中选择最少的行，是的每一列至少有一个1.

该问题可以想象成二分图的支配集问题的模型：从X集合选择最少的点，是的能否覆盖住Y集合所有的点。（当然X与Y集合是有边（映射）关系的）。

把这个问题和上面的完美覆盖结合起来看，我们就会发现不同的地方就是，上面红色标出的那句话，实际上也是如此。能够想到的一个中直观的搜索方法是：我们每次选择任意选一列，然后从该列选择任意一行，同时将列值为1的节点所在的列删掉（这里不再是将列上值为1的节点所在的行删掉，因为不再要求列值为1）。如果，最后的所有的列都删掉了，那么就可以说找到一组可行解。

这个题目的做法是用迭代加深的启发式搜索（ID_A*)。那么，我们来说一下启发函数的设计。

启发函数的值 = 按一定的规则选择列，是的所有的列都被选择需要的最少的行数。（这里的按一定的规则是说，每次开始选择列的时候都遵守一个规则）。说明估价函数（f() = g() + h()）发函数的正确性,我们只需要说明两点：1. f（）满足单调不减的特性； 2. h()是相容的，也就是说,设pres, curs 为前一个状态和当前状态，weight为状态转移代价，那么h(pres) <= curs + weight。 按通常的dfs的估价函数设计的方法，去实际代价函数g（） = depth of the search.
那么 g()函数值每只增加一个单位“1”。对于h()函数，按照f的不递减的特性，需要满足每次减少的最大值为“1"才可。 如果按照我们我们上面启发函数的设计原则，每次计算的时候记录下计算估价函数值时用到的列，那么，对于当前的此次计算挂架函数值，会出现两种情况，一是，原来记录下的列有被删除的（每次只能删除一个原来记录的列，因为，记录的列之间是没有关系的），这样h（）的函数值减小一；二是，原来记录的列没有被删除的，这样h()的函数值保持不变。由此，weight = 0 或 1，h() 函数是相容的，f() = g()
+ h() 满足单调不递减的特性。 

 简单的来说，对于重复覆盖，我们只删除列，不删除行。由此得到以下的cpp重复覆盖的代码（供参考）

 对于ID_A*,我个人比较喜欢下面的这种实现方法：