精确覆盖问题：
给定一个由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]++; //插入一个结点，那么该列的结点个数+1
row[idx] = insertRow;
col[idx] = insertCol; //记录第idx个结点所在的行、列
u[idx] = insertCol; //向上指向列结点头串的insertCol
d[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#include #include 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; }
题：https://www.acwing.com/problem/content/171/
数独问题转化为精确覆盖矩阵：
行代表问题的所有情况，列代表问题的约束条件。
每个格子所能填的数字为 1~9 ， 共有 9 * 9（3^2 * 3^2） 个格子，总情况数为729种。
即Dancing links的行数为729。
列分为四种：
- [0，81)列，分别对应81个格子是否被放置了数字[82， 2 * 81)列，分别对应9行，每行[1，9]个数字的放置情况[2 * 81， 3 * 81)列，分别对应9列，每列[1，9]个数字的放置情况[3 * 81，4 * 81)列，分别对应9个“宫”，每个“宫”[1，9]个数字的放置情况
所以总的列数为 4 * 81 = 324 列
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）