北京看白癜风哪间医院权威 https://jbk.39.net/yiyuanzaixian/bjzkbdfyy/nxbdf/看完题目之后，你产生的第一个疑问一定是DLX是什么。
除非您是吊打集训队的dalao那还来看我这篇烂文干什么赶紧切题去吧
为了引入，我们先来看一道题。
已知目前有r个集合，请选出其中的一些集合使它们的并集为1,2,3,…,n,并且你要让这些选出的集合的交集为空集。
这种问题有一个名字，叫做精确覆盖问题（ExactCoverProblem）
那么我们先来想想这题该怎么做吧。
我们先用一个r行n列的矩阵来表示一个精确覆盖问题
第i行第j个元素代表第i个集合是否存在元素j
例如对于数据n=7,r=6
它所对应一个6行7列的矩阵
我们考虑采用回溯法解决这个问题。
每一次选择一个没有被覆盖的元素，也就是一列。然后选择包含着个元素的集合进行覆盖，也就是一行。那么在矩阵中，我们每选择一个没有被删除的，接着看一下这一列中还有哪些行是1，尝试删除该行，回溯时恢复改行。当然，如果我们选了一行，那么就把这一行其它的1所在的列也应当删除。恢复同理。
这种思路又被称为算法X（AlgorithmX），可惜的是删除与恢复序列并不是一个简单的操作，这个时候就应当召唤出数据结构来帮我们优化啦。那么这个数据结构支持什么呢？它应当支持删除和恢复一列。所以我们就要把目光转向著名的程序设计大师Knuth所发明的一种数据结构——舞蹈链（DancingLinks）
舞蹈链（DancingLinks）是什么？我们可以简单的将它理解为一个双向循环交叉链表（请大家牢记这个定义）
使用舞蹈链的算法X又被称为DLX
（不会链表的同学可以自行百度哦）
把上面那句话对应到程序中是怎么样的呢，首先处理双向
对于每一个节点，我们都给它两个指针L与R。分别表示这个节点的左边节点编号和右边节点编号。
接着处理交叉
什么叫交叉？横纵即为交叉。横的链表我们已经设计了。那么考虑下纵链表，再给每个节点两个指针U与D。分别表示这个节点上方节点编号与下方节点编号。
最后处理循环
我们让最右边的所有节点的R指向最左边的节点，最左边节点的L指向最右边的节点，上下也是如此。
那矩阵如何对应到舞蹈链里呢？
我们把矩阵的每一个1节点对应到舞蹈链的一个节点
那么问题来了，如何删除一列呢？
我们可以在每个纵链表的顶端添加一个节点——虚拟节点
该节点的U指向其所在列的最后一个节点，D指向其所在列的第一个节点。L与R分别指向旁边两列的虚拟节点。
那么删除一列只需要将该列虚拟节点左边的节点的R指向该列虚拟节点右边的虚拟节点，将该列所对虚拟节点的右边虚拟节点的L指向该列所对虚拟节点的左边的虚拟节点。（好好理解下）
问题是删完了吗？没有，这一列里还有节点跟其他节点连着呢。
所以我们应当将该列所有节点找到，然后再把这列所有节点所在的所有行的其它节点的上下节点互指。这样就删完一列了。
那么恢复一列不就是逆操作嘛？
所以一个DancingLinks大概就是
这样的。
什么？有点晕？不如上上代码看看？不懂的地方可以看一下注释哦。
有没有看到一个舞者在你的链表上跳舞呢？主部分又被称作dance。
你认为舞蹈链就这么点用处？那可就大错特错了！
你听说过八皇后问题吗？你听说过数独问题吗？
没错DLX算法还是一种用来处理数独的方法！
它是目前跑的最快的处理数独的算法！
怎么用它来处理数独呢？那么我们就要把数独问题转换成精确覆盖问题了。
这也谈到了一个精确覆盖问题的建模。不过也非常简单，每列代表一个限制条件，每行代表一种方案，若方案i满足限制j，则矩阵mat[j]=1，因此矩阵的构造既要满足所有限制条件，又不能漏掉可能的方案。
对于数独，我们先看限制
每行中每个数只能出现一遍，ROW(x,v)表示第x行有数字v。每列中每个数只能出现一遍，COL(x,v)表示第x列有数字v。每宫中每个数只能出现一遍，BLOCK(i,v)表示编号为i的九宫格块内有数字v每格中只能填一个数，EXIST(x,y)表示第x行y列有数字。
那么应当会有行
再看决策，定义三元组(r,c,v)代表第r行第c个填v
那么决策(r,c,v)所能满足的限制就是
ROW(r,v)COL(c,v)BLOCK(zu(r,c),v)EXIST(r,c,v)
（其中zu(r,c)代表点(r,c)所在的九宫格的编号）
列应当有列。
那么这样，我们不就把数独转换成了精确覆盖问题了嘛？
作业：LGPP
然后自己找题去吧（逃）
参考文献：
[1]刘汝佳《算法竞赛入门经典训练指南》
[2]图片出处：hihocoder
本文发布于洛谷日报，特约作者：白井黑子
原文
