Boj2580_스도쿠
-
완전탐색을 이용하여 문제를 해결하였다.
-
Bfs + 이분탐색을 통해 문제를 해결하였다.
#include<cstdio>
int b[9][9], dx[] = { 0,3,6,9 }, dy[] = { 0,3,6,9 }, cnt;
bool c[9][9][10];
bool go(int x, int y, int zero) {
if (zero == 0)
return 1;
for (int i = 1; i < 10; i++) c[y][x][i] = 0;
for (int i = 0; i < 9; i++) c[y][x][b[i][x]] = 1, c[y][x][b[y][i]] = 1;
int xd = x / 3, yd = y / 3;
for (int i = dy[yd]; i < dy[yd + 1]; i++)
for (int j = dx[xd]; j < dx[xd + 1]; j++)
c[y][x][b[i][j]] = 1;
for (int i = 1; i < 10; i++)
if (!c[y][x][i]) {
b[y][x] = i;
bool flag = false;
for (int j = 0; j < 9; j++) {
if (flag) break;
for (int k = 0; k < 9; k++) {
if (flag) break;
if (!b[j][k]) {
if (go(k, j, zero - 1)) return 1;
b[y][x] = 0;
flag = true;
break;
}
}
}
}
return false;
}
int main() {
for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) {
scanf("%d", &b[i][j]);
if (b[i][j] == 0) cnt++;
}
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (!b[i][j]) go(j, i, cnt-1);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) printf("%d ", b[i][j]);
puts("");
}
return 0;
}