DLX算法——实现精确覆盖与重复覆盖问题

问题背景简介：

给定一个 N 行 M 列的矩阵，矩阵中每个元素要么是 1，要么是 0。

你需要在矩阵中挑选出若干行，使得对于矩阵的每一列 j，在你挑选的这些行中，有且仅有一行的第 j 个元素为 1。

 算法的基本思路：

精确覆盖的定义：

对于一个全集S = {1,   2，3， 4， 5， 6， 7}，分别存在着如下的子集：

A = {1,  2,  3}  B = {3，  4， 5， 7}   C = { 4,   5,  6， 7}  D = {1， 5， 6， 7}选择能够最精确覆盖全集的子集显然是 A 与C。

那么我们对于普遍问题怎么一步步得到结果呢？

	元素表头	1	2	3	4	5	6	7
集合
S1		1	1	1	0	0	0	0
S2		0	0	1	1	0	1	1
S3		0	0	0	1	1	1	1
S4		1	0	0	0	1	1	1

 我们若选取S1集合，则删去S1集合这一行，再删去所有包含相同元素的集合（题目中的精确覆盖即是要求不包含重复元素，故有相同元素的即删去）

——这就是本算法的核心删除方法

得到：

	元素表头	4	5	6	7
集合
S3		1	1	1	1

 若再选取S3，则矩阵被全部删除完毕，即得到答案。

若我们在第一步删去集合S2：

得到

	元素表头	1	2	5
集合
S2		0	0	0

 元素1,   2， 5最终也无法补上，故不存在答案。

此方案失败后，集合就要进行回溯。

代码的具体实现：

数据结构使用的是双向十字链表——特点是上，下，左，右都存在相应的指针。

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m, cnt;  //矩阵的长，宽，点的数量
int l[N], r[N], u[N], d[N], row[N], col[N]; //每个点的左，右，上，下，行，列信息
int h[N]; //每行的头结点
int s[N]; //每列的节点数
int ans, ansk[N];  //需要ans个子集，分别为ansk[]//建立空的矩阵——链表初始化，生成每列的头
void inti(int m)  //m个不同元素，列为不同元素的表头
{int i;for(i = 0; i <= m; ++i){r[i] = i + 1;l[i] = i - 1;u[i] = d[i] = i;  //起始情况上下所连的该列的特征值即是本身}r[m] = 0;  //m的右边是0  //列首尾相连，具有循环的性质l[0] = m;  // 0左边是mmemset(h, -1, sizeof h); //标记头结点memset (s, 0, sizeof s);  //拥有节点数为0cnt = m + 1; //开始时编号已经给了m个头节点，包括0节点
}//在r行c列插入点：
void link(int R, int C)
{s[C] ++;  //节点数加1row[cnt] = R; //当前身份码的节点在的是R行col[cnt] = C; //当前身份码的节点在的是C列u[cnt] = C; //头插法的思想，新节点直接连在表头后面，上与特征值相连d[cnt] = d[C]; // 下与原与表头相连的节点相连u[d[C]] = cnt; //将原来的节点与新节点相关联d[C] = cnt;  //将头结点与新节点相连if(h[R] == -1){  //若该行无其他节点， 将第一个加入的节点作为该行的行头节点h[R] = r[cnt] = l[cnt] = cnt;  //头结点的特殊标记——h[i] = i;}else{r[cnt] = h[R]; //右侧与头结点直接相连l[cnt] = l[h[R]];r[l[h[R]]] = cnt;l[h[R]] = cnt;}cnt++;  //身份码更新return;
}//删除与恢复(与传统链表一致，即是取消相连状态
void removen(int c)  //按列删除
{r[l[c]] = r[c];  //先删除哨兵节点l[r[c]] = l[c];//舞蹈线特色删除，删除c列和c列上有值的行for(int i = d[c]; i != c; i = d[i]){ //遍历所有位于该列的点for(int j = r[i];j != i; j = r[j]){  // 删除该行u[d[j]] = u[j];d[u[j]] = d[j];s[col[j]] --; //该列的结点数减1}}
}
void resume(int c)  //即为删除的逆操作，流程类似
{for(int i = u[c]; i != c; i = u[i]){for(int j = l[i]; j != i; j = l[j]){u[d[j]] = j;d[u[j]] = j;s[col[j]] ++;}}r[l[c]] = c;l[r[c]] = c;
}
//核心dance操作：
bool dance(int deep)
{if(r[0] == 0) {  //矩阵已经删完ans = deep;for(int i = 0; i < deep; ++i) cout<<ansk[i]<<" ";return true;}int c = r[0];//找到点最少的列for(int i = r[0]; i != 0; i = r[i]) if(s[i] < s[c]) c = i;removen(c);for(int i = d[c]; i != c; i = d[i]){ansk[deep] = row[i];for(int j = r[i]; j != i; j = r[j]) removen(col[j]);if(dance(deep + 1)) return true; //保持这个选择，遍历下去能解决，返回true（真正返回点）//以这个选择方案，解决不了，故状态回溯for(int j = l[i]; j != i; j = l[j]) resume(col[j]);}resume(c);return 0;
}int main()
{cin>>n>>m;inti(m);for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){int t;cin>>t;if(t) link(i, j);}}if(!dance(0)) cout<<"No Solution!"<<endl;return 0;
}

重复覆盖的问题即是在删除函数发生了改变，不再需要第二层循环，仅仅从上到下删除节点即可。

解决数独问题：

朴素版dfs：

#include<bits/stdc++.h>
using namespace std;const int N = 1010;
int mapn[N][N];
int col[N][10];
int row[N][10];
int jihe[N][10];  //（i - 1) / 3 * 3 + (j - 1) / 3 + 1void init()
{for(int i = 1; i <= 9; ++i){for(int j = 1; j <= 9; ++j){int xu = (i - 1) / 3 * 3 + (j - 1) / 3 +1;if(mapn[i][j]){col[j][mapn[i][j]] = 1;row[i][mapn[i][j]] = 1;jihe[xu][mapn[i][j]] = 1;}}}
}
void dfs(int x, int y, int left)
{if(left == 0){for(int i = 1; i <= 9; ++i){for(int j = 1; j <= 9; ++j){cout<<mapn[i][j]<<" ";}cout<<endl;}exit(0);}for(int i = 0; i < 81; ++i){int nx = i / 9 + 1;int ny = i % 9 + 1;int xu = (nx - 1) / 3 * 3 + (ny - 1) / 3 + 1;if(!mapn[nx][ny]){for(int j = 1; j <= 9; ++j){if(!col[ny][j] && !row[nx][j] && !jihe[xu][j]){mapn[nx][ny] = j;col[ny][j] = 1;row[nx][j] = 1;jihe[xu][j] = 1;dfs(nx, ny, left - 1);mapn[nx][ny] = 0;col[ny][j] = 0;row[nx][j] = 0;jihe[xu][j] = 0;}}return;}}
}int main()
{int used = 0;for(int i = 1; i <= 9; ++i){for(int j = 1; j <= 9; ++j){cin>>mapn[i][j];if(mapn[i][j]) used ++;}}init();int flag = 0;int i, j;for(i = 1; i <= 9; ++i){for(j = 1; j <= 9; ++j){if(!mapn[i][j]) {flag = 1;break;}}}if(flag) dfs(i, j, 81 - used);return 0;
}

利用DLX算法优化解决数独问题：