这是常规的（也是题解的）的剪枝：

#include<bits/stdc++.h>
#define int long long

int a[10][10];

int h[10][10],l[10][10],g[10][10],dy[10][10],poi[10][10],li[10],sor[10];

int ans=0,mp[82],les=0,tnc=0;

bool find=0;

void dfs(int x,int y,int cnt,int now){
//	std::cout<<sor[x]<<' '<<y<<' '<<cnt<<'\n';
	if(y==0) x++,y=9;
	if(x==10){
		find=1;
		ans=std::max(ans,cnt);
		return ;
	}
	if(a[sor[x]][y]!=0) dfs(x,y-1,cnt,now);
//	if(mp[les]-mp[now]+cnt<=ans) return ;
	for(int i=9;i>=1;i--){
		if(h[sor[x]][i]||l[y][i]||g[dy[sor[x]][y]][i]) continue;
		h[sor[x]][i]=l[y][i]=g[dy[sor[x]][y]][i]=1;
		dfs(x,y-1,cnt+i*poi[sor[x]][y],now+1);
		h[sor[x]][i]=l[y][i]=g[dy[sor[x]][y]][i]=0;
	}
	return ;
}

signed main(){
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			int opt=(i-1)*3+j;
			for(int k=(i-1)*3+1;k<=i*3;k++)
				for(int p=(j-1)*3+1;p<=j*3;p++) dy[k][p]=opt;
		}
	} 
	for(int i=1;i<=9;i++) poi[1][i]=poi[9][i]=6;
	for(int i=2;i<=8;i++) poi[i][1]=poi[i][9]=6;
	for(int i=2;i<=8;i++) poi[2][i]=poi[8][i]=7;
	for(int i=3;i<=7;i++) poi[i][2]=poi[i][8]=7;
	for(int i=3;i<=7;i++) poi[3][i]=poi[7][i]=8;
	for(int i=4;i<=6;i++) poi[i][3]=poi[i][7]=8;
	for(int i=4;i<=6;i++) poi[4][i]=poi[6][i]=9;
	poi[5][4]=poi[5][6]=9;
	poi[5][5]=10;
	for(int i=1;i<=9;i++) 
		for(int j=1;j<=9;j++){
			std::cin>>a[i][j];
			if(a[i][j]==0) {
				li[i]++;
				continue;
			}
			les--;
			if(h[i][a[i][j]]) {
				std::cout<<-1;
				return 0;
			} 
			if(l[j][a[i][j]]){
				std::cout<<-1;
				return 0;
			}
			if(g[dy[i][j]][a[i][j]]){
				std::cout<<-1;
				return 0;
			}
			h[i][a[i][j]]=1;
			l[j][a[i][j]]=1;
			g[dy[i][j]][a[i][j]]=1;
			ans+=poi[i][j]*a[i][j];
		} 
	les=0;
	for(int i=0;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(li[j]==i) sor[++tnc]=j;
		}
	}
	for(int i=1;i<=9;i++){
		for(int j=9;j>=1;j--){
			if(a[sor[i]][j]!=0) continue;
			mp[++les]=mp[les-1]+9*poi[sor[i]][j];
		}
	}
	dfs(1,9,ans,0);
	if(!find) std::cout<<-1;
	else std::cout<<ans;
	return 0;
}

而我又加了一种最优性剪枝，就是每次判断如果将剩下所有没填的数都填上 $9$ （代码中的 mp 数组），如果此时还无法超过最优的答案，就返回掉：

#include<bits/stdc++.h>
#define int long long

int a[10][10];

int h[10][10],l[10][10],g[10][10],dy[10][10],poi[10][10],li[10],sor[10];

int ans=0,mp[82],les=0,tnc=0;

bool find=0;

void dfs(int x,int y,int cnt,int now){
//	std::cout<<sor[x]<<' '<<y<<' '<<cnt<<'\n';
	if(y==0) x++,y=9;
	if(x==10){
		find=1;
		ans=std::max(ans,cnt);
		return ;
	}
	if(a[sor[x]][y]!=0) dfs(x,y-1,cnt,now);
	if(mp[les]-mp[now]+cnt<=ans) return ;
	for(int i=9;i>=1;i--){
		if(h[sor[x]][i]||l[y][i]||g[dy[sor[x]][y]][i]) continue;
		h[sor[x]][i]=l[y][i]=g[dy[sor[x]][y]][i]=1;
		dfs(x,y-1,cnt+i*poi[sor[x]][y],now+1);
		h[sor[x]][i]=l[y][i]=g[dy[sor[x]][y]][i]=0;
	}
	return ;
}

signed main(){
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			int opt=(i-1)*3+j;
			for(int k=(i-1)*3+1;k<=i*3;k++)
				for(int p=(j-1)*3+1;p<=j*3;p++) dy[k][p]=opt;
		}
	} 
	for(int i=1;i<=9;i++) poi[1][i]=poi[9][i]=6;
	for(int i=2;i<=8;i++) poi[i][1]=poi[i][9]=6;
	for(int i=2;i<=8;i++) poi[2][i]=poi[8][i]=7;
	for(int i=3;i<=7;i++) poi[i][2]=poi[i][8]=7;
	for(int i=3;i<=7;i++) poi[3][i]=poi[7][i]=8;
	for(int i=4;i<=6;i++) poi[i][3]=poi[i][7]=8;
	for(int i=4;i<=6;i++) poi[4][i]=poi[6][i]=9;
	poi[5][4]=poi[5][6]=9;
	poi[5][5]=10;
	for(int i=1;i<=9;i++) 
		for(int j=1;j<=9;j++){
			std::cin>>a[i][j];
			if(a[i][j]==0) {
				li[i]++;
				continue;
			}
			les--;
			if(h[i][a[i][j]]) {
				std::cout<<-1;
				return 0;
			} 
			if(l[j][a[i][j]]){
				std::cout<<-1;
				return 0;
			}
			if(g[dy[i][j]][a[i][j]]){
				std::cout<<-1;
				return 0;
			}
			h[i][a[i][j]]=1;
			l[j][a[i][j]]=1;
			g[dy[i][j]][a[i][j]]=1;
			ans+=poi[i][j]*a[i][j];
		} 
	les=0;
	for(int i=0;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(li[j]==i) sor[++tnc]=j;
		}
	}
	for(int i=1;i<=9;i++){
		for(int j=9;j>=1;j--){
			if(a[sor[i]][j]!=0) continue;
			mp[++les]=mp[les-1]+9*poi[sor[i]][j];
		}
	}
	dfs(1,9,ans,0);
	if(!find) std::cout<<-1;
	else std::cout<<ans;
	return 0;
}

为什么第一种AC，第二种 5 分？