题目网址：https://www.luogu.com.cn/problem/P1074
大意就是在一个9*9的数独中填数，要求行列宫都是九个互不相同的数字，给定一定的得分机制，要求求解最大得分。思路大致从零最少的行开始搜索（试想现实中你做数独一定是这样的方法）,然后只要将0位置的信息保存，总数就是深度值。按照优先搜索的顺序逐个填写，为了节省计算资源，在搜索之前就预处理0位置的相关信息。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define mem(a) memset(a,0,sizeof(a)) 7 #define prime1 1e9+7 8 #define prime2 1e9+9 9 #define scand(x) scanf("%llf",&x) 10 #define dbg(args) cout<<#args<<":"<<args<<endl; 11 #define pb(i) push_back(i) 12 #define ppb(x) pop_back(x) 13 #define scan(a) scanf("%d",&a) 14 #define pf printf 15 #define f(i,a,b) for(int i=a;i<=b;i++) 16 int n,init,tot,ans=-1,a[10][10],hang[10][10],lie[10][10],gong[10][10],s[100][5]; 17 //s[][0]保存行，s[][1]保存列，s[][2]保存宫，s[][3] 保存得分 18 struct node{ 19 int hang,zero_cnt; 20 }p[10]; 21 bool cmp(node& a, node& b) 22 { 23 return a.zero_cnt<b.zero_cnt; 24 } 25 26 int score(int x,int y) 27 { 28 if(x==5&&y==5)return 10; 29 else if(x>=4&&x<=6&&y>=4&&y<=6)return 9; 30 else if(x>=3&&x<=7&&y>=3&&y<=7)return 8; 31 else if(x>=2&&x<=8&&y>=2&&y<=8)return 7; 32 else return 6; 33 } 34 int which(int x,int y) 35 { 36 if(x>=1&&x<=3&&y>=1&&y<=3)return 1; 37 else if(x>=1&&x<=3&&y>=4&&y<=6)return 2; 38 else if(x>=1&&x<=3&&y>=7&&y<=9)return 3; 39 else if(x>=4&&x<=6&&y>=1&&y<=3)return 4; 40 else if(x>=4&&x<=6&&y>=4&&y<=6)return 5; 41 else if(x>=4&&x<=6&&y>=7&&y<=9)return 6; 42 else if(x>=7&&x<=9&&y>=1&&y<=3)return 7; 43 else if(x>=7&&x<=9&&y>=4&&y<=6)return 8; 44 else if(x>=7&&x<=9&&y>=7&&y<=9)return 9; 45 } 46 void dfs(int dep ,int sum)//搜索深度以及得分总数 47 { 48 if(dep==tot) 49 { 50 // dbg(sum); 51 if(sum>ans)ans=sum; 52 return ; 53 } 54 f(i,1,9)//在dep深度的位置填1-9的数字 55 { 56 //行列宫都不冲突 57 if(!hang[s[dep][0]][i]&&!lie[s[dep][1]][i]&&!gong[s[dep][2]][i]) 58 { 59 hang[s[dep][0]][i]=lie[s[dep][1]][i]=gong[s[dep][2]][i]=1; 60 dfs(dep+1,sum+i*s[dep][3]); 61 hang[s[dep][0]][i]=lie[s[dep][1]][i]=gong[s[dep][2]][i]=0; 62 } 63 } 64 return; 65 } 66 int main() 67 { 68 //freopen("input.txt","r",stdin); 69 //freopen("output.txt","w",stdout); 70 std::ios::sync_with_stdio(false); 71 f(i,1,9) 72 { 73 p[i].hang=i; 74 f(j,1,9) 75 { 76 scan(a[i][j]); 77 if(a[i][j]) 78 { 79 init+=a[i][j]*score(i,j); 80 hang[i][a[i][j]]=1; 81 lie[j][a[i][j]]=1; 82 gong[which(i,j)][a[i][j]]=1; 83 } 84 else 85 { 86 p[i].zero_cnt++; 87 } 88 } 89 } 90 91 sort(p+1,p+10,cmp); 92 93 f(i,1,9) 94 { 95 f(j,1,9) 96 { 97 if(a[p[i].hang][j]==0) 98 { 99 s[tot][0]=p[i].hang;//保存每个零位置的行、列、宫以及得分，否则dfs中将会重复计算 100 s[tot][1]=j; 101 s[tot][2]=which(p[i].hang,j); 102 s[tot++][3]=score(p[i].hang,j); 103 } 104 } 105 } 106 // dbg(init); 107 //dbg(tot); 108 dfs(0,init);//从第0个零的位置开始搜索，初始得分为init 109 pf("%d",ans); 110 return 0; 111 }