经典的搜索题,我用的是简单的暴搜,其实这题用排除法做会更快。
1 #include <stdio.h> 2 #include <string.h> 3 #define index(a,b) 3*(a/3)+(b/3) 4 bool r[10][10],c[10][10],sodu[10][10]; 5 int map[10][10]; 6 bool find; 7 void dfs(int n) 8 { 9 int i,j,k,x,y; 10 if(find) return ; 11 if(n >= 81) 12 { 13 find = 1; 14 for(i = 0; i < 9; i++) 15 { 16 for(j = 0; j < 9; j++) 17 printf("%d",map[i][j]); 18 printf("\n"); 19 } 20 } 21 x = n/9; 22 y = n%9; 23 if(map[x][y]) dfs(n+1); 24 else 25 { 26 for(k = 1; k <= 9; k++) 27 if(!r[x][k] && !c[y][k] && !sodu[index(x,y)][k]) 28 { 29 r[x][k] = c[y][k] = 1; 30 sodu[index(x,y)][k] = 1; 31 map[x][y] = k; 32 dfs(n+1); 33 r[x][k] = c[y][k] = 0; 34 sodu[index(x,y)][k] = 0; 35 map[x][y] = 0; 36 } 37 } 38 } 39 int main() 40 { 41 int n,i,j,t; 42 scanf("%d",&n); 43 while(n--) 44 { 45 memset(map,0,sizeof map); 46 memset(r,0,100); 47 memset(c,0,100); 48 memset(sodu,0,100); 49 find = 0; 50 for(i = 0; i < 9; i++) 51 for(j = 0; j < 9; j++) 52 { 53 scanf("%1d",&map[i][j]); 54 t = map[i][j]; 55 if (t) 56 { 57 r[i][t] = 1; 58 c[j][t] = 1; 59 sodu[index(i,j)][t] = 1; 60 } 61 } 62 dfs(0); 63 } 64 return 0; 65 }