舞蹈链学习笔记
# 前言
Dancing Links是一种十字链表，通常用于解决精确覆盖问题。
# 精确覆盖问题
给定一个行列的矩阵，矩阵的元素为或。现在要求选择若干行，使得对于每一列，在选中的行中有且仅有一行的第列为
上述问题可以通过DFS搜索进行解决，但问题在于要如何加速搜索过程中状态的维护。
# 舞蹈链
舞蹈链中，每一个节点都有up/down/left/right四个属性，作为十字链表的基础属性，连接对应方向上的节点
每一行、列都有对应的行标col、列标row，同时还有一个头结点head。
当加入节点时，需要按照从左到右、从上到下地添加新节点nd：在row[r].left与row[r]之间、col[c].up与col[c]之间添加nd。
当遍历时，如果发现head.left == head，说明所有列都已被消除，已找到可行解。
否则，我们遍历所有列，并从中选取col_size最小（即列中1最少）的列，称为opt_col
若opt_col的col_size为，说明没有任何一行可以使得该列存在，回溯。
否则，遍历该列为的所有行，并将所有为的列删除，继续递归。
若都失败，则恢复状态并回溯
删除列时，只需要对列标操作：
c->left->right = c->right;
c->right->left = c->left;
1
2
2
同时，把该列中所有所在的行删除：
for(node * nd=c->down; nd!=c; nd=nd->down){ // 遍历行
for(node * rnd = nd->right; rnd != nd; rnd = rnd->right){ // 遍历行的每一个节点
if(rnd->info.col_head != NULL){ // rnd节点不是行标
rnd->up->down = rnd->down;
rnd->down->up = rnd->up;
rnd->info.col_head->info.col_size--;
}
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
恢复时进行反操作即可
c->left->right = c->right->left = c;
for(node * nd=c->down; nd!=c; nd=nd->down){ // 遍历行
for(node * rnd = nd->right; rnd != nd; rnd = rnd->right){ // 遍历行的每一个节点
if(rnd->info.col_head != NULL){ // rnd节点不是行标
rnd->up->down = rnd->down->up = rnd;
rnd->info.col_head->info.col_size++;
}
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
具体见代码
UPD：尝试了一下数组版舞蹈链（不使用指针），比指针版慢！
# 例题 洛谷P4929
#include <bits/stdc++.h>
using namespace std;
struct danceing_link{
const static int max_node = 3e5 + 1000;
const static int max_col = 500 + 10;
const static int max_row = 500 + 10;
struct node{
int row_index, col_index; // 行标/列标的row_index/col_index无意义
node * up, * down, * left, * right;
union{
node * col_head; // 列头
int col_size; // 仅列标使用该属性
} info;
}nodes[max_node];
int node_cnt, col_cnt, row_cnt;
node col[max_col], row[max_row], head;
void init(int row_c, int col_c){
node_cnt = 0;
col_cnt = col_c, row_cnt = row_c;
head.up = head.down = head.left = head.right = &head;
for(int i=1; i<=col_c; i++){
col[i].up = col[i].down = &col[i];
col[i].left = head.left;
col[i].right = &head;
col[i].left->right = col[i].right->left = &col[i];
col[i].info.col_size = 0;
}
for(int i=1; i<=row_c; i++){
row[i].left = row[i].right = &row[i];
row[i].up = head.up;
row[i].down = &head;
row[i].up->down = row[i].down->up = &row[i];
row[i].info.col_head = NULL;
}
}
void insert(int r, int c){ // 必须按照从左到右，从上到下
node * nd = &nodes[node_cnt++];
nd->row_index = r; // 输出选中的行时要用到
nd->col_index = c; // col_index 只是为了方便debug
nd->left = row[r].left, nd->right = &row[r];
nd->left->right = nd->right->left = nd;
nd->up = col[c].up, nd->down = &col[c];
nd->up->down = nd->down->up = nd;
nd->info.col_head = &col[c];
col[c].info.col_size++; // 列大小加1
}
void remove_col(node * c){
c->left->right = c->right;
c->right->left = c->left;
for(node * nd=c->down; nd!=c; nd=nd->down){
for(node * rnd = nd->right; rnd != nd; rnd = rnd->right){
if(rnd->info.col_head != NULL){ // 不是行标
rnd->up->down = rnd->down;
rnd->down->up = rnd->up;
rnd->info.col_head->info.col_size--;
}
}
}
}
void restore_col(node * c){
c->left->right = c->right->left = c;
for(node * nd=c->down; nd!=c; nd=nd->down){
for(node * rnd = nd->right; rnd != nd; rnd = rnd->right){
if(rnd->info.col_head != NULL){ // 不是行标
rnd->up->down = rnd->down->up = rnd;
rnd->info.col_head->info.col_size++;
}
}
}
}
bool dance(vector<int> & choose){ // 如果用deque会更快
if(head.left == &head) return true;
node * opt_col = head.right;
for(node * ptr = head.right; ptr != &head; ptr = ptr->right){
if(ptr->info.col_size < opt_col->info.col_size) opt_col = ptr;
}
if(opt_col->info.col_size == 0) return false;
remove_col(opt_col);
for(node * ptr = opt_col->down; ptr != opt_col; ptr = ptr->down){
for(node * rptr = ptr->right; rptr != ptr; rptr = rptr->right){
if(rptr->info.col_head != NULL){ // 不是行标
remove_col(rptr->info.col_head);
}
}
choose.push_back(ptr->row_index);
if(dance(choose)) return true;
choose.pop_back();
for(node * rptr = ptr->right; rptr != ptr; rptr = rptr->right){
if(rptr->info.col_head != NULL){ // 不是行标
restore_col(rptr->info.col_head);
}
}
}
restore_col(opt_col);
return false;
}
}dlx;
signed main(){
int n, m;
cin >> n >> m;
dlx.init(n, m);
for(int i=1, v; i<=n; i++){
for(int j=1; j<=m; j++){
cin >> v;
if(v) dlx.insert(i, j);
}
}
vector<int> ans;
if(dlx.dance(ans)){
for(int v:ans) cout << v << ' ';
cout << '\n';
}else{
cout << "No Solution!\n";
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# 舞蹈链解决数独问题
详见夜深人静写算法（九）- Dancing Links X（跳舞链） (opens new window)
转变为精确覆盖问题。行代表问题的所有情况，列代表问题的约束条件。每个格子能够填的数字为[1,9]，并且总共有9×9(即3^2×3^2)个格子，所以总的情况数为729种。也就是DancingLinks的行为729行。
列则分为四种：
[0, 81)列 分别对应了81个格子是否被放置了数字。
[82, 2*81)列 分别对应了9行，每行[1, 9]个数字的放置情况；
[281, 381)列 分别对应了9列，每列[1, 9]个数字的放置情况；
[381, 481)列 分别对应了9个“宫”，每“宫”[1, 9]个数字的放置情况；
所以总的列数为4*81=324列。
宫号的计算方式可以通过行号和列号得出。即 宫号 = (i/3)*3 + (j/3)；
那么构建01矩阵的时候，我们从上到下，从左到右遍历数独，对于在(i, j)上有数字k的只需要插入一行，这行上有四列为“1”。对于没有填写数字的需要枚举[1, 9]，把在(i, j)位置上填[1, 9]的情况都进行插入，一共9行。
此处附上POJ 3074 TLE的代码
#include <iostream>
#include <cstdio>
#include <vector>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;
struct danceing_link{
const static int max_node = 3e5 + 1000;
const static int max_col = 325;
const static int max_row = 729 + 10;
// 以下省略
}dlx;
int grid[10][10], slot_cnt, idx;
int rr[81 * 9 + 1], cr[81 * 9 + 1], vr[81 * 9 + 1];
void insert(int r, int c, int v){
rr[idx] = r, cr[idx] = c, vr[idx] = v;
dlx.insert(idx, r * 9 + c + 1);
dlx.insert(idx, 81 + r * 9 + v);
dlx.insert(idx, 81 * 2 + c * 9 + v);
dlx.insert(idx, 81 * 3 + (r/3*3 + c/3) * 9 + v);
idx++;
}
char buffer[83];
void solve(){
dlx.init(81 - slot_cnt + slot_cnt * 9, 4 * 81);
idx = 1;
for(int r=0; r<9; r++){
for(int c=0; c<9; c++){
if(grid[r][c] == 0){
for(int v=1; v<=9; v++){
insert(r, c, v);
}
}else{
insert(r, c, grid[r][c]);
}
}
}
vector<int> ans;
if(dlx.dance(ans)){
for(int i=0, v; i<ans.size(); i++){
v = ans[i];
grid[rr[v]][cr[v]] = vr[v];
}
for(int i=0; i<81; i++) buffer[i] = grid[i/9][i%9] + '0';
cout << buffer << '\n';
}else{
cout << (idx / 0) << endl;
}
}
signed main(){
Android;
while(cin >> buffer){
if(buffer[0] == 'e') break;
slot_cnt = 0;
for(int i=0; i<81; i++){
if(buffer[i] == '.'){
slot_cnt++;
grid[i/9][i%9] = 0;
}else{
grid[i/9][i%9] = buffer[i] - '0';
}
}
solve();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
PS: 处理精确覆盖问题的时候就别想着用IDA*之类的骚操作了，就以本题为例：任意方案的递归深度一定小于等于81，而正解的递归深度一定等于81。
# 完美覆盖
同精确覆盖的问题相似，只不过要求变为每列中至少有一个
只需要稍稍改动代码，在删除列时不再把对应行的所有列删除，由此导致的搜索树变大，可以通过IDA*等启发式算法解决
# 引用
图片来自 blog.csdn.net/whereisherofrom/article/details/79220897
上次更新: 2021/02/24, 03:37:30