2019-09-14

舞蹈链（dancing links）算法

缘起

【1】中我们使用了dfs求解八皇后问题. 但是一旦这个八变动, 则会导致解的个数爆炸性的增长. 你可以试试【1】中的代码对于16皇后能不能1秒内算出解的个数. 显然是不能的. 于是更高效的Knuth大神发明的舞蹈链算法（dancing links）诞生了. 本文来学习学习该算法.

分析

首先撇开N皇后问题不谈. 我们先来看一个新的问题——01矩阵的精确覆盖问题 （下简称精确匹配）

给定一个由01组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1
例如：如下的矩阵

就包含一个这样的行集合——1、4、5行.

那么这个问题和我们这里的N皇后问题有什么关系呢? 有的. 考虑N皇后的约束——不就是N个行约束、N个列约束、2N-3个左对角线约束（左对角线是从左下角到右上角的对角线）、2N-3个右对角线（右对角线是从左上角到右下角的对角线）约束吗. 所谓的约束就是这些线上面只能恰好出现一个皇后. 所以我们可以构造一个01矩阵——N*N行（按照N*N棋盘从左至右、从上至下），N+N+(2N-3)+(2N-3)=6*N-6列.

其中1~N列刻画的是行约束、N+1~2N刻画的是列约束、2N+1~4N-1列刻画的是左对角线约束，4N~6N-2列刻画的是右对角线约束. 则不放置皇后的格子（注意，01矩阵的每一行其实代表棋盘上的一个格子）对应的01矩阵的一行全部是0. 放置皇后的格子对应的01矩阵的一行恰好有4个1. 而这4个1在1~N列、 N+1~2N列、2N+1~4N-1列、4N~6N-2列各恰好有一个, 即从该棋盘格子所在行、所在列、所在左对角线、所在右对角线四个维度刻画了该放置皇后的棋盘格子. 这四个1所在列数就是刻画了该皇后格子所在的行、所在的列、所在的左对角线、所在的右对角线. 然后其实我们就是要从该01矩阵的N*N行中找一些行（其实恰好就是N行，因为是N皇后嘛~）使得1~N列、N+1~2N列这2N列（刻画行、列）每列恰好一个1. 然后2N+1~6N-2 这4N-2列（刻画左右对角线）每列至多一个1.即可. 这其实不就化归为了类似（只是目标状态稍有不同而已,精确匹配是每一列, 而N皇后是前2N列）上述01矩阵精确匹配问题了么?

其实01矩阵精确匹配问题是很大的一类问题. N皇后只是它的一个应用而已.

那么精确匹配问题该怎么解决呢? 依旧是dfs. 首先，第一列总得有1吧~ 而能在第一列有1的行的集合我们是可以求出来的. 然后逐一去试. 比如对于上图中展示的矩阵. 我们选择第二行去使得第一列出现一个1. 则因为副作用是第二行亦使得4、7列出现1. 所以在第4、7列有1的行也都不能选了（因为精确匹配要求）——例如第四行、第5行，第6行. 即我们缩减了可选择的行的集合（即矩阵去掉2、4、5、6行）. 而且因为1、4、7列已经搞定了，所以矩阵去掉1、4、7列. 所以矩阵的规模缩小了. 然后其实就是在这个缩小规模后的矩阵上解决精确匹配问题.

直至最后如果得到一种方案就输出，如果得不到，就回溯.

上面这种回溯思想其实也不用我多说什么. 写过回溯的人都知道. 但是我论述的过程中，各位回溯巨佬应该已经发现痛点了——我要怎么高效缓存缩小规模的矩阵以及回溯的时候高效还原缩小前的矩阵呢? 如果暴力缓存与还原的话，复杂度就biubiiubiu的上涨咯~ 于是Knuth大神敏锐的注意到双向十字链表（本问题中就换了一个优雅的名字——舞蹈链 DL dancing links）这种数据结构可以用于此场景——用于高效的缩小以及回溯时还原矩阵.

那么怎么针对上面的精确匹配问题构造舞蹈链呢? 这里大量借鉴了【2】

首先将矩阵中出现的1按照从左至右、从上至下的顺序编号一共16个1，就编号1~16，然后按照上下左右织成下面的样子

即每一行、每一列都是一个双向链表. 其中Head和C1、C2、……、C7是辅助元素（辅助元素的作用在下面用舞蹈链求解精确匹配问题的时候就知道有啥用了）（原矩阵有7列）

左侧的是行号，辅助元素所在的行是0行，其余元素所在的行从1到6 （原矩阵有6行）

每两个元素之间有一个双向箭头连线，表示双向链中相邻两个元素的关系（水平的是左右关系、垂直的是上下关
系）
单向的箭头并不是表示单向关系，而因为是循环双向链，左侧的单向箭头和右侧的单向箭头（上边的和下边的）组
成了一个双向箭头，例如元素14左侧的单向箭头和元素16右侧的单项箭头组成一个双向箭头，表示14.Left=16、
16.Right=14；同理，元素14下边的单项箭头和元素C4上边的单向箭头组成一个双向箭头，表示14.Down=C4、
C4.Up=14

接下来，利用图来解释Dancing Links是如何求解精确覆盖问题

1、首先判断Head.Right=Head？若是，求解结束，输出解；若不是，求解还没结束，到步骤2（也可以判断Head.Left=Head？）

2、获取Head.Right元素，即元素C1，

并标识元素C1（标识元素C1，指的是标识C1、和C1所在列的所有元素、以及该元素所在行的元素，并从双向链中移除这些元素（即将这些元素从它们所在的列中移除，例如将5从它所在的列中移除掉它），因为你第一列总得在4和10中选一个, 一旦选择了一个, 则另一个也就不能选了, 例如你选了2，即你选了第二行来覆盖C1中需要出现的1，则第四行你就不能选,从而不仅是10会消失，11也会消失, 而因为选了4，所以4所在的第二行的所有元素也会消失.）。如下图中的紫色部分。

如上图可知，行2和行4中的一个必是答案的一部分（其他行中没有元素能覆盖列C1），先假设选择的是行2

3、选择行2（在答案栈中压入2），标识该行中的其他元素（元素5和元素6）所在的列首元素，即标识元素C4和标识元素C7，下图中的橙色部分。

注意的是，即使元素5在步骤2中就从双向链中移除，但是元素5的Col分量还是指向元素C4的（这就很利于后面回溯恢复），这里体现了双向链的强大作用。

回归正题，因为选了第二行, 所以5、6也被选掉了. 即意味着5和6所在的列也都不能选了. 即14、13、16也都不能选了，所以14、13、16所在的行也都不能选了，是不是突然有种很多点都被干掉了的感觉?

如下图

紫色和橙色的元素都要被删掉（一旦一列上已经没有元素的话, 则此列的标识就被删掉）. 即剩下的部分就是

一下子空了好多，是不是转换为一个少了很多元素的精确覆盖问题？

注意上面我们删除元素的顺序是先确定哪一列，然后将此列上所有元素所在的行上的元素删除(其实就是上面所谓的标识某列). 例如选定第二行之后，将第二行中每个元素(例如5)的所在列（例如C4）选定，然后删除该列上所有元素（例如11和14）所在的行上的元素（例如14、15和16）删除.

4、获取Head.Right元素，即元素C2，并标示元素C2。如下图中的紫色部分。

如图，列C2只有元素7覆盖，故答案只能选择行3

5、选择行3（在答案栈中压入3），标示该行中的其他元素（元素8和元素9）所在的列首元素，即标示元素C3和标示元素C6，下图中的橙色部分。

把上图中的紫色部分和橙色部分移除的话，剩下的绿色部分就如下图所示

6、获取Head.Right元素，即元素C5，元素C5中的垂直双向链中没有其他元素，也就是没有元素覆盖列C5。说明当前求解失败。要回溯到之前的分叉选择步骤（步骤2）。

那要回标列首元素（把列首元素、所在列的元素，以及对应行其余的元素。并恢复这些元素到双向链中），回标列首元素的顺序是标示元素的顺序的反过来(反过来是不难理解的吧?)。从前文可知，顺序是回标列首C6、回标列首C3、回标列首C2、回标列首C7、回标列首C4。表面上看起来比较复杂，实际上利用递归，是一件很简单的事。并把答案栈恢复到步骤2（清空的状态）的时候。又回到下图所示（即只标识了C1）