poj3074 与 3076 Dancing Links 解数独

发表于 分类于

好吧，我承认这个数独的图不好弄，建图建了好久，才想到每一行就四个结点，数独转化为精确覆盖问题的方法还是参照 Knuth 的论文，如果读取到一个格子是空的，那么加 99 行，分别表示这个格子填 11 到 99 这 99 个数字，如果读取到的格子是一个数字，那么就加一行就可以了，然后列有 9×9×49 \times 9 \times 4 列，前 81 列表示这一行表示填的是第 ii 行第 jj 列的格子，接下来 8181 列表示第 i 行填写 kk，接下来 8181 列表示第 jj 列填写 4，最后 8181 列表示对应九宫格填写 kk。转化为精确覆盖之后，直接跑 dlx 的 dfs 就可以了，主要还是建图，对于 3076 的 16×1616 \times 16 做法如出一辙。

我的代码：

3074：

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX = 1000;
const int oo = 0x3f3f3f3f;
const int nC = 9 * 9 * 4;
const int delta[] = {1, 82, 163, 244};
const int head = 0;

int cnt[MAX], st[MAX];
int left[MAX * MAX], right[MAX * MAX], up[MAX * MAX], down[MAX * MAX];
int row[MAX * MAX], col[MAX * MAX];
struct Ans {
  int r, c, k;
} ans[MAX * MAX];
int M, K;

void remove(const int& c) {
  left[right[c]] = left[c];
  right[left[c]] = right[c];
  for (int i = down[c]; i != c; i = down[i]) {
    for (int j = right[i]; j != i; j = right[j]) {
      up[down[j]] = up[j];
      down[up[j]] = down[j];
      cnt[col[j]]--;
    }
  }
}

void resume(const int& c) {
  for (int i = up[c]; i != c; i = up[i]) {
    for (int j = left[i]; j != i; j = left[j]) {
      down[up[j]] = j;
      up[down[j]] = j;
      cnt[col[j]]++;
    }
  }
  left[right[c]] = c;
  right[left[c]] = c;
}

bool dfs(const int& k) {
  if (right[head] == head) {
    char s[100] = {0};
    for (int i = 0; i < k; i++) {
      s[ans[st[i]].r * 9 + ans[st[i]].c] = ans[st[i]].k + '0';
    }
    puts(s);
    return true;
  }
  int s = oo, c = 0;
  for (int i = right[head]; i != head; i = right[i]) {
    if (cnt[i] < s) {
      s = cnt[i];
      c = i;
    }
  }
  remove(c);
  for (int i = down[c]; i != c; i = down[i]) {
    st[k] = row[i];
    for (int j = right[i]; j != i; j = right[j]) {
      remove(col[j]);
    }
    if (dfs(k + 1)) return true;
    for (int j = left[i]; j != i; j = left[j]) {
      resume(col[j]);
    }
  }
  resume(c);
  return false;
}

void init() {
  left[head] = nC;
  right[head] = 1;
  up[head] = down[head] = head;
  for (int i = 1; i <= nC; i++) {
    left[i] = i - 1;
    right[i] = (i + 1) % (nC + 1);
    up[i] = down[i] = i;
    cnt[i] = 0;
    col[i] = i;
    row[i] = 0;
  }
  M = 0;
  K = nC;
}

int makecolhead(const int& c) {
  K++;
  cnt[c]++;
  col[K] = c;
  row[K] = M;
  left[K] = right[K] = K;
  up[K] = c;
  down[K] = down[c];
  up[down[K]] = K;
  down[up[K]] = K;
  return K;
}

void addcol(const int& id, const int& c) {
  K++;
  cnt[c]++;
  col[K] = c;
  row[K] = M;
  left[K] = id;
  right[K] = right[id];
  left[right[K]] = K;
  right[left[K]] = K;
  up[K] = c;
  down[K] = down[c];
  up[down[K]] = K;
  down[up[K]] = K;
}

void addrow(const int& i, const int& j, const int& k) {
  int id;
  M++;
  ans[M].r = i;
  ans[M].c = j;
  ans[M].k = k + 1;
  id = makecolhead(9 * i + j + delta[0]);
  addcol(id, 9 * i + k + delta[1]);
  addcol(id, 9 * j + k + delta[2]);
  addcol(id, (i / 3 * 3 + j / 3) * 9 + k + delta[3]);
}

int main() {
  char s[100];
  while (*gets(s) != 'e') {
    init();
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        if (s[i * 9 + j] == '.') {
          for (int k = 0; k < 9; k++) {
            addrow(i, j, k);
          }
        } else {
          addrow(i, j, s[i * 9 + j] - '1');
        }
      }
    }
    dfs(0);
  }
  return 0;
}

3076:

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int oo = 0x3f3f3f3f;
const int nR = 16 * 16 * 16 + 10;
const int nC = 16 * 16 * 4;
const int MAX = nR * 4 + nC + 10;
const int delta[] = {1, 16 * 16 + 1, 16 * 16 * 2 + 1, 16 * 16 * 3 + 1};
const int head = 0;

int cnt[nC + 10], st[nC + 10];
int left[MAX], right[MAX], up[MAX], down[MAX];
int row[MAX], col[MAX];
struct Ans {
  int r, c, k;
} ans[MAX];
int M, K;

void remove(const int& c) {
  left[right[c]] = left[c];
  right[left[c]] = right[c];
  for (int i = down[c]; i != c; i = down[i]) {
    for (int j = right[i]; j != i; j = right[j]) {
      up[down[j]] = up[j];
      down[up[j]] = down[j];
      cnt[col[j]]--;
    }
  }
}

void resume(const int& c) {
  for (int i = up[c]; i != c; i = up[i]) {
    for (int j = left[i]; j != i; j = left[j]) {
      down[up[j]] = j;
      up[down[j]] = j;
      cnt[col[j]]++;
    }
  }
  left[right[c]] = c;
  right[left[c]] = c;
}

bool dfs(const int& k) {
  if (right[head] == head) {
    char s[300] = {0};
    for (int i = 0; i < k; i++) {
      s[ans[st[i]].r * 16 + ans[st[i]].c] = ans[st[i]].k + 'A';
    }
    for (int i = 0; i < 16; i++) {
      for (int j = 0; j < 16; j++) {
        putchar(s[i * 16 + j]);
      }
      puts("");
    }
    return true;
  }
  int s = oo, c = 0;
  for (int i = right[head]; i != head; i = right[i]) {
    if (cnt[i] < s) {
      s = cnt[i];
      c = i;
    }
  }
  remove(c);
  for (int i = down[c]; i != c; i = down[i]) {
    st[k] = row[i];
    for (int j = right[i]; j != i; j = right[j]) {
      remove(col[j]);
    }
    if (dfs(k + 1)) return true;
    for (int j = left[i]; j != i; j = left[j]) {
      resume(col[j]);
    }
  }
  resume(c);
  return false;
}

void init() {
  left[head] = nC;
  right[head] = 1;
  up[head] = down[head] = head;
  for (int i = 1; i <= nC; i++) {
    left[i] = i - 1;
    right[i] = (i + 1) % (nC + 1);
    up[i] = down[i] = i;
    cnt[i] = 0;
    col[i] = i;
    row[i] = 0;
  }
  M = 0;
  K = nC;
}

int makecolhead(const int& c) {
  K++;
  cnt[c]++;
  col[K] = c;
  row[K] = M;
  left[K] = right[K] = K;
  up[K] = c;
  down[K] = down[c];
  up[down[K]] = K;
  down[up[K]] = K;
  return K;
}

void addcol(const int& id, const int& c) {
  K++;
  cnt[c]++;
  col[K] = c;
  row[K] = M;
  left[K] = id;
  right[K] = right[id];
  left[right[K]] = K;
  right[left[K]] = K;
  up[K] = c;
  down[K] = down[c];
  up[down[K]] = K;
  down[up[K]] = K;
}

void addrow(const int& i, const int& j, const int& k) {
  int id;
  M++;
  ans[M].r = i;
  ans[M].c = j;
  ans[M].k = k;
  id = makecolhead(16 * i + j + delta[0]);
  addcol(id, 16 * i + k + delta[1]);
  addcol(id, 16 * j + k + delta[2]);
  addcol(id, (i / 4 * 4 + j / 4) * 16 + k + delta[3]);
}

int main() {
  char str[300];
  char s[300];
  int pos;
  bool blocks = false;
  while (~scanf("%s", str)) {
    if (blocks)
      puts("");
    else
      blocks = true;
    init();
    pos = 0;
    for (int i = 0; i < 16; i++) s[pos++] = str[i];
    for (int i = 1; i < 16; i++) {
      scanf("%s", str);
      for (int j = 0; j < 16; j++) {
        s[pos++] = str[j];
      }
    }
    for (int i = 0; i < 16; i++) {
      for (int j = 0; j < 16; j++) {
        if (s[i * 16 + j] == '-') {
          for (int k = 0; k < 16; k++) {
            addrow(i, j, k);
          }
        } else {
          addrow(i, j, s[i * 16 + j] - 'A');
        }
      }
    }
    dfs(0);
  }
  return 0;
}