135 lines
2.7 KiB
C++
135 lines
2.7 KiB
C++
#include <cstdio>
|
|
#include <cstring>
|
|
using namespace std;
|
|
|
|
#define mx 100100
|
|
int sum = 0;
|
|
int arr[10][10];
|
|
inline int read() {
|
|
char c = getchar();
|
|
if (c == '.')
|
|
c = '0';
|
|
while (c < '0' || c > '9') {
|
|
c = getchar();
|
|
if (c == '.')
|
|
c = '0';
|
|
}
|
|
return c - '0';
|
|
}
|
|
struct dancing_link {
|
|
int n, m, cnt;
|
|
int l[mx], r[mx], u[mx], d[mx], row[mx], col[mx];
|
|
int h[mx];
|
|
int s[mx];
|
|
int ansk[mx];
|
|
void init(int _n, int _m) {
|
|
n = _n, 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;
|
|
l[0] = m;
|
|
memset(h, -1, sizeof(h));
|
|
memset(s, 0, sizeof(s));
|
|
cnt = m + 1;
|
|
}
|
|
void link(int R, int C) {
|
|
s[C]++;
|
|
row[cnt] = R;
|
|
col[cnt] = C;
|
|
u[cnt] = C;
|
|
d[cnt] = d[C];
|
|
u[d[C]] = cnt;
|
|
d[C] = cnt;
|
|
if (h[R] < 0)
|
|
h[R] = r[cnt] = l[cnt] = cnt;
|
|
else {
|
|
r[cnt] = h[R];
|
|
l[cnt] = l[h[R]];
|
|
r[l[h[R]]] = cnt;
|
|
l[h[R]] = cnt;
|
|
}
|
|
cnt++;
|
|
}
|
|
void remove(int c) {
|
|
r[l[c]] = r[c], l[r[c]] = l[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]]--;
|
|
}
|
|
}
|
|
}
|
|
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;
|
|
}
|
|
bool dance(int deep) {
|
|
if (r[0] == 0) {
|
|
int x, y, v;
|
|
for (int i = 0; i < deep; i++) {
|
|
x = (ansk[i] - 1) / 9 / 9;
|
|
y = (ansk[i] - 1) / 9 % 9;
|
|
v = (ansk[i]) % 9;
|
|
if (v == 0)
|
|
v = 9;
|
|
arr[x][y] = v;
|
|
}
|
|
return 1;
|
|
}
|
|
int c = r[0];
|
|
for (int i = r[0]; i != 0; i = r[i])
|
|
if (s[i] < s[c])
|
|
c = i;
|
|
remove(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])
|
|
remove(col[j]);
|
|
if (dance(deep + 1) == 1)
|
|
return 1;
|
|
for (int j = l[i]; j != i; j = l[j])
|
|
resume(col[j]);
|
|
}
|
|
resume(c);
|
|
return false;
|
|
}
|
|
} dlx;
|
|
int main() {
|
|
dlx.init(729, 324);
|
|
int x;
|
|
int o;
|
|
for (int i = 0; i <= 8; i++) {
|
|
for (int j = 0; j <= 8; j++) {
|
|
arr[i][j] = x = read();
|
|
for (int k = 1; k <= 9; k++) {
|
|
if (x != k && x != 0)
|
|
continue;
|
|
o = i * 9 * 9 + j * 9 + k;
|
|
dlx.link(o, i * 9 + j + 1);
|
|
dlx.link(o, i * 9 + 81 + k);
|
|
dlx.link(o, j * 9 + 81 * 2 + k);
|
|
dlx.link(o, 81 * 3 + (i / 3 * 3 + j / 3) * 9 + k);
|
|
}
|
|
}
|
|
}
|
|
dlx.dance(0);
|
|
for (int i = 0; i <= 8; i++) {
|
|
for (int j = 0; j <= 8; j++)
|
|
printf("%d", arr[i][j]);
|
|
printf("\n");
|
|
}
|
|
return 0;
|
|
}
|