舞蹈链（Dancing Links）算法 —

本文主要是介绍舞蹈链（Dancing Links）算法 —— 求精确覆盖问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

精确覆盖问题：
给定一个由0、1组成的矩阵，是否能找到一个行的集合，使得集合中每一列恰好包含一个1。
在这里插入图片描述

这类问题就是经典的精确覆盖问题，没有多项式算法，属于NP完全问题。

回溯穷举：

选择第一行(红色)，同一列中有1会与之冲突的元素用蓝色标识出来。
从列看下去，同样有1的使用蓝色标识的这些行不能选择，用绿色标识。
选择了第一行红色后，蓝色与绿色不予考虑，那么将红色记录，将红蓝绿删除后，问题简化。
继续用同样的方式求解这个小规模矩阵。
再次缩小问题规模，删除完后剩下的矩阵变成了空矩阵。
本次搜索一共选择两行，选中行中有‘1’的列数为5，而总列数为7，故这种方案宣告失败。
回溯，选择第二行。
缩小问题规模，剩下的为一个1*3的矩阵，且三个数字均为‘1’。
很明显，这行必选。
至此，找到了一个精确覆盖的可行解。

传统用二维数组存储矩阵，但是这样搜索删除回溯的时间复杂度很高，理解繁琐，实现易错。

（舞蹈链）Dancing Links

一种链式的数据结构，利用链表的性质，在缓存和回溯矩阵中运用得恰到好处，不需要额外开辟空间。
在这种结构存储的矩阵，列删除是O(1)，行删除是O©。
因这种删除、恢复的操作是指针之间的跳跃仿佛精妙的舞蹈一般而得名。

删除算法 ：
x 的左结点的右指向指向 x 的右结点
x 的右结点的左指向指向 x 的左结点

恢复算法：
x 左结点的右指向指向 x
x 右结点的左指向指向 x

矩阵的十字交叉双向循环链表的数据结构表示：
所有箭头的左右边界循环相连（上下边界亦循环相连）。
每个元素结点代表了原矩阵中的‘1’，即图中的蓝色方块，其中的数字代表对应内存池中的编号。
初始化时，所有的行首结点的左右指针和列首结点的上下指针都指向自己。
然后对矩阵进行行、列分别递增的顺序进行读取，读到‘1’就执行行结点插入操作，这正对应了图中蓝色结点的递增序。

在这里插入图片描述
初始化

插入结点

删除、恢复

选取（dancing）

代码模板
数组版：

struct DLX
{int n, m, idx;	//行数、列数、元素索引int l[MAX_NUM], r[MAX_NUM], u[MAX_NUM], d[MAX_NUM];	//记录某个idx索引点上下左右的索引int col[MAX_NUM], row[MAX_NUM];	//记录某个索引点的 行、列 号int nodeIdxPerRow[MAX_NUM];	//记录每行开头的结点的索引int nodeNumPerCol[MAX_NUM];	//记录每列结点的个数int ansd, ans[MN];void init(int n, int m)	//初始化 十字链表的 头结点 和 列结点表头串{for (int i = 0; i <= m; ++i)	//头结点数组索引 = 0， 列结点表头共m个 索引1~m{r[i] = i + 1;l[i] = i - 1;u[i] = d[i] = i;	//列结点头串只有互相横向连接，上下连接均指向自己}r[m] = 0;	//循环连接， col[m]的右端指向头结点l[0] = m;	//头结点的左端指向col[m]memset(nodeIdxPerRow, 0, sizeof(nodeIdxPerRow));memset(nodeNumPerCol, 0, sizeof(nodeNumPerCol));idx = m + 1;	//目前使用0头结点与m个列结点表头串，0~m共m+1个结点}void link(int insertRow, int insertCol)	//插入结点 进行的一些数据记录{//更新列nodeNumPerCol[insertCol]++;	//插入一个结点，那么该列的结点个数+1row[idx] = insertRow;col[idx] = insertCol;	//记录第idx个结点所在的行、列u[idx] = insertCol;	//向上指向列结点头串的insertCold[idx] = d[insertCol];	//向下指向原来列结点头串的向下指向点u[d[insertCol]] = idx;	//原来列结点头串指向的结点 向上由指向列结点头串指向插入的结点(使用索引)d[insertCol] = idx;	//列结点头串向下指向新插入的结点(使用索引)//更新行if (!nodeIdxPerRow[insertRow])	//如果该结点是第一个插入的结点nodeIdxPerRow[insertRow] = r[idx] = l[idx] = idx;	//该行没有点，直接加入else{r[idx] = nodeIdxPerRow[insertRow];	//新结点的右端指向原来行记录中的第一个结点l[idx] = l[nodeIdxPerRow[insertRow]];	//新结点的左端指向原来行记录第一个结点的左端r[l[nodeIdxPerRow[insertRow]]] = idx;	//原来行记录第一个结点的左端的右端 指向 新插入的点(使用索引)l[nodeIdxPerRow[insertRow]] = idx;	//原来行记录第一个结点的左端 指向 新插入结点(使用索引)}idx++;return ;}void remove(int deleteCol)	//删除涉及c列的集合，将要删除的列的左右两端连接起来，也等于将自己摘除出来{r[l[deleteCol]] = r[deleteCol], l[r[deleteCol]] = l[deleteCol];for (int i = d[deleteCol]; i != deleteCol; i = d[i])for (int j = r[i]; j != i; j = r[j]){u[d[j]] = u[j];d[u[j]] = d[j];nodeNumPerCol[col[j]]--;}}void resume(int resCol)	//恢复涉及c列的集合{for (int i = u[resCol]; i != resCol; i = u[i])for (int j = l[i]; j != i; j = l[j]){u[d[j]] = j;d[u[j]] = j;nodeNumPerCol[col[j]]++;}r[l[resCol]] = resCol;l[r[resCol]] = resCol;}bool dance(int deep)	//选取了d行{if (!r[0])	//全部覆盖了{ansd = deep;return 1;}int c = r[0];	//表头结点指向的第一个列for (int i = r[0]; i != 0; i = r[i])	//枚举列头指针if (nodeNumPerCol[i] < nodeNumPerCol[c])c = i;remove(c);	//将该列删去for (int i = d[c]; i != c; i = d[i])	//枚举该列的元素{ans[deep] = row[i];	//记录该列元素的行for (int j = r[i]; j != i; j = r[j])remove(col[j]);	//将该列的某个元素的行上的元素所在列都删去if (dance(deep + 1))return 1;for (int j = l[i]; j != i; j = l[j])resume(col[j]);}resume(c);return 0;}
}

指针版：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf  = (-1u>>1); 
#define m 4
#define n 16
#define N n*n*n
#define M 4*n*n
char s[20][20];
struct node{int r,c;node *L,*R,*U,*D;
};
node DD[N*4+5], row[N+5], col[M+5], head;
int cnt, size[M+5], ans[n+5][n+5];
inline void init(int r, int c){cnt = 0;head.L = head.R = head.U = head.D = &head;for (int i = 0; i < c; i++){col[i].c = i;col[i].r = r;col[i].L = &head;col[i].R = head.R;col[i].L->R = col[i].R->L = &col[i];col[i].U = col[i].D = &col[i];size[i] = 0; } for (int i = r - 1; i >= 0; i--){row[i].r = i;row[i].c = c;row[i].D = &head;row[i].U = head.U;row[i].U->D = row[i].D->U = &row[i];row[i].L = row[i].R = &row[i]; }
}inline void delLR(node *p){p->L->R = p->R;p->R->L = p->L;
}
inline void delUD(node *p){p->U->D = p->D;p->D->U = p->U;
} 
inline void recLR(node *p){p->L->R = p->R->L = p;
}
inline void recUD(node *p){p->U->D = p->D->U = p;
} 
inline void add(int r, int c){node *p = &DD[cnt++];p->c = c;p->r = r;p->U = &col[c];p->D = col[c].D;p->U->D = p->D->U = p;p->R = &row[r];p->L = row[r].L;p->L->R = p->R->L = p;size[c]++;
} void cover(int c){if (c == M)return;delLR(&col[c]);node *p, *q;for (p = col[c].D; p != (&col[c]); p = p->D){for (q = p->L ; q != p; q = q->L){if (q->c == M)continue;delUD(q);size[q->c]--;}}
} void resume(int c){if (c == M)return ;node *p, *q;for (p = col[c].U; p != (&col[c]); p = p->U){for (q = p->R; q != p; q = q->R){if (q->c == M)continue;recUD(q);size[q->c]++;}}recLR(&col[c]);
}bool DLX(int k){node *p;if (head.L == (&head)){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++)printf("%c", ans[i][j] + 'A');puts("");}puts(""); return true;}int MIN = inf, c = 1;for (p = head.R; p != (&head); p = p->R){if (size[p->c] < MIN){MIN = size[p->c];c = p->c;}}cover(c);for (p = col[c].D; p != (&col[c]); p = p->D){node *q;for (q = p->L; q != p; q = q->L){cover(q->c);}int rr = p->r;ans[rr / (n*n)][(rr/n) % n] = rr % n;if (DLX(k + 1))return true;for (q = p->R; q != p; q = q->R)resume(q->c);}resume(c);return false;
} void insert(int i, int j, int k){int r = (i * n + j) * n + k - 1;add(r, i * n + k - 1);add(r, n * n + j * n + k - 1);add(r, 2 * n * n + (i / m * m + j / m ) * n + k - 1);add(r, 3 * n * n + i * n + j);
} void Sudoku(){int k; for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (s[i][j] != '-')insert(i, j, s[i][j] - 'A' + 1);else {for (int k = 1; k <= n; k++)insert(i, j, k);}}}if (!DLX(0))puts("NO Solution!");
} int main(){//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout); while (scanf("%s", s[0]) != EOF){for (int i = 1; i < n; i++)scanf("%s", s[i]); init(N, M);Sudoku();}// getchar();return 0;
}