You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
62 lines
1.2 KiB
62 lines
1.2 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
const int N = 9;
|
|
int g[N][N];
|
|
|
|
int check(int r, int c, int x) {
|
|
for (int i = 0; i < 9; i++)
|
|
if (g[r][i] == x || g[i][c] == x) return 0;
|
|
|
|
int row = r / 3 * 3;
|
|
int col = c / 3 * 3;
|
|
|
|
for (int i = 0; i < 3; i++)
|
|
for (int j = 0; j < 3; j++)
|
|
if (g[i + row][j + col] == x) return 0;
|
|
return 1;
|
|
}
|
|
/*
|
|
17.5..8..
|
|
.52.1....
|
|
.....759.
|
|
.8...94.3
|
|
.197.4..8
|
|
7......15
|
|
4.1...6..
|
|
3...2..59
|
|
...96..3.
|
|
*/
|
|
void dfs(int u) {
|
|
if (u == 81) {
|
|
for (int i = 0; i < 9; i++) {
|
|
for (int j = 0; j < 9; j++)
|
|
cout << g[i][j];
|
|
cout << endl;
|
|
}
|
|
exit(0);
|
|
}
|
|
int r = u / 9, c = u % 9;
|
|
if (g[r][c]) dfs(u + 1);
|
|
for (int x = 1; x <= 9; x++) {
|
|
if (check(r, c, x)) {
|
|
g[r][c] = x;
|
|
dfs(u + 1);
|
|
g[r][c] = 0;
|
|
}
|
|
}
|
|
}
|
|
int main() {
|
|
freopen("4.in", "r", stdin);
|
|
|
|
for (int i = 0; i < 9; i++)
|
|
for (int j = 0; j < 9; j++) {
|
|
char x;
|
|
cin >> x;
|
|
if (x != '.') g[i][j] = x - '0';
|
|
}
|
|
|
|
dfs(0);
|
|
|
|
return 0;
|
|
} |