搜索绝对是解决数独问题的一大利器。
我们将不完整的数独读入。如果爆搜的话显然凉凉O(2^81)?
想一下人类在玩数独的时候会怎样——找出填数比较多的行与列的交点，因为这样能排除更多的非法选择。
放到搜索上就能减小搜索树的规模，降低时间复杂度。
我们统计每一行、每一列已经填完的数的数量，再统计每一行、每一列、每一小区域当中某一个数是否出现。
每一次填数之前，找已经填数最多的一行与最多的一列的交点填（如果还没填的话），当数独都填完了以后统计一下得分即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[10][10],h[10][10],s[10][10],f[10][10]; 4 int hnum[10],snum[10]; 5 int ans=-1,num; 6 int calc(int i,int j) 7 { 8 return (i-1)/3*3+1+(j-1)/3; 9 } 10 int sum[10][10]= 11 { 12 {0,0,0,0,0,0,0,0,0,0}, 13 {0,6,6,6,6,6,6,6,6,6}, 14 {0,6,7,7,7,7,7,7,7,6}, 15 {0,6,7,8,8,8,8,8,7,6}, 16 {0,6,7,8,9,9,9,8,7,6}, 17 {0,6,7,8,9,10,9,8,7,6}, 18 {0,6,7,8,9,9,9,8,7,6}, 19 {0,6,7,8,8,8,8,8,7,6}, 20 {0,6,7,7,7,7,7,7,7,6}, 21 {0,6,6,6,6,6,6,6,6,6}, 22 }; 23 inline int total() 24 { 25 int aaa=0; 26 for(int i=1;i<=9;i++) 27 for(int j=1;j<=9;j++) 28 aaa+=a[i][j]*sum[i][j]; 29 return aaa; 30 } 31 void dfs(int x,int y,int z) 32 { 33 if(z==81) 34 { 35 ans=max(ans,total()); 36 return ; 37 } 38 for(int k=1;k<=9;k++) 39 { 40 if(h[x][k]||s[y][k]||f[calc(x,y)][k]) continue ; 41 h[x][k]=1; 42 s[y][k]=1; 43 f[calc(x,y)][k]=1; 44 a[x][y]=k; 45 hnum[x]++; 46 snum[y]++; 47 int xx=0,yy=0; 48 int maxx=-1,maxy=-1; 49 for(int i=1;i<=9;i++) 50 if(hnum[i]>maxx&&hnum[i]<9) maxx=hnum[i],xx=i; 51 for(int j=1;j<=9;j++) 52 if(snum[j]>maxy&&!a[xx][j]) maxy=snum[j],yy=j; 53 dfs(xx,yy,z+1); 54 h[x][k]=0; 55 s[y][k]=0; 56 f[calc(x,y)][k]=0; 57 hnum[x]--; 58 snum[y]--; 59 a[x][y]=0; 60 } 61 } 62 int main() 63 { 64 ios::sync_with_stdio(false); 65 for(int i=1;i<=9;i++) 66 for(int j=1;j<=9;j++) 67 { 68 cin>>a[i][j]; 69 if(a[i][j]!=0) 70 { 71 h[i][a[i][j]]=1; 72 s[j][a[i][j]]=1; 73 f[calc(i,j)][a[i][j]]=1; 74 num++; 75 hnum[i]++; 76 snum[j]++; 77 } 78 } 79 int x=0,y=0,maxx=-1,maxy=-1; 80 for(int i=1;i<=9;i++) 81 if(hnum[i]>maxx&&hnum[i]<9) maxx=hnum[i],x=i; 82 for(int j=1;j<=9;j++) 83 if(snum[j]>maxy&&!a[x][j]) maxy=snum[j],y=j; 84 dfs(x,y,num); 85 cout<<ans; 86 return 0; 87 }