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
| #include <stdio.h>
#include <stdlib.h>
int sudoku[9][9];
int info[81][2],info_idx;
int left=0,prevleft;
void pM(){
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j)
printf("%d ",sudoku[i][j]);
printf("\n");
}
}
int vertical_check(int y, int x){
int arr[10] = {0, };
int cnt = 9;
int posy = y/3*3, posx = x/3*3;
for(int i = 0; i < 9; ++i) {
if (sudoku[y][i]&&!arr[sudoku[y][i]]) ++arr[sudoku[y][i]], --cnt;
if (sudoku[i][x]&&!arr[sudoku[i][x]]) ++arr[sudoku[i][x]], --cnt;
}
for(int i = posy; i < posy+3; ++i)
for(int j = posx; j < posx+3; ++j)
if(sudoku[i][j]&&!arr[sudoku[i][j]]) ++arr[sudoku[i][j]], --cnt;
if(cnt==1){
for(int i = 1; i <= 9; ++i)
if(!arr[i]) return i;
}
return 0;
}
int possible(int y, int x){
int arr[10] = {0,};
int posy = y/3*3, posx = x/3*3;
int ret = 0;
for(int i = 0; i < 9; ++i) {
if (sudoku[y][i]) ++arr[sudoku[y][i]];
if (sudoku[i][x]) ++arr[sudoku[i][x]];
}
for(int i = posy; i < posy+3; ++i)
for(int j = posx; j < posx+3; ++j)
if(sudoku[i][j]) ++arr[sudoku[i][j]];
for(int i = 1; i <= 9; ++i)
if(!arr[i]) ret+=(1<<(i-1));
return ret;
}
void initsudoku(){
for(int i = 0; i < 9; ++i)
for(int j = 0; j < 9; ++j){
if(sudoku[i][j]) continue;
int ret = vertical_check(i,j);
if(ret){
sudoku[i][j] = ret;
--left;
}
}
}
void DFS(int c){
if(c==info_idx){
pM();
exit(0);
}
int comb = possible(info[c][0],info[c][1]);
if(!comb) return;
for(int i = 0; i < 9; ++i) {
if(comb&(1<<i)) {
sudoku[info[c][0]][info[c][1]] = i+1;
DFS(c + 1);
sudoku[info[c][0]][info[c][1]] = 0;
}
}
}
int main(){
for(int i = 0; i < 9; ++i)
for(int j = 0; j < 9; ++j) {
scanf("%d", &sudoku[i][j]);
if(!sudoku[i][j]) ++left;
}
while(left!=prevleft) {
prevleft = left;
initsudoku();
}
for(int i = 0; i < 9; ++i)
for(int j = 0; j < 9; ++j){
if(sudoku[i][j]) continue;
info[info_idx][0] = i;
info[info_idx++][1] = j;
}
DFS(0);
}
|
