#include<bits/stdc++.h>
using namespace std;
const int score[9][9]={
                    6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,
                    6 ,7 ,7 ,7 ,7 ,7 ,7 ,7 ,6 ,
                    6 ,7 ,8 ,8 ,8 ,8 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,9 ,9 ,9 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,9 ,10,9 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,9 ,9 ,9 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,8 ,8 ,8 ,8 ,7 ,6 ,
                    6 ,7 ,7 ,7 ,7 ,7 ,7 ,7 ,6 ,
                    6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,
                };
struct coor{
    int x,y;
};
coor empty[100];
int cnt,ans=-1;
int broad[20][20];
bool f=true;
int cal(){
    int sum=0;
    for(register int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            sum+=broad[i][j]*score[i][j];
        }
    }
    return sum;
}
bool search(int n,int x,int y){
    for(int i=0;i<9;i++){
        if(broad[x][i]==n){
            return true;
        }
    }
    for(int i=0;i<9;i++){
        if(broad[i][y]==n){
            return true;
        }
    }
    int l=y/3*3,r=l+3;
    int t=x/3*3,b=t+3;
    for(int i=l;i<r;i++){
        for(int j=t;j<b;j++){
            if(broad[j][i]==n){
                return true;
            }
        }
    }
    return false;
}
void dfs(int step){
    if(step==cnt){
        ans=max(ans,cal());
        return ;
    }
    bool flag=false;
    for(int i=1;i<=9;i++){
        if(!search(i,empty[step].x,empty[step].y)){
            broad[empty[step].x][empty[step].y]=i;
            flag=true;
            dfs(step+1);
            broad[empty[step].x][empty[step].y]=0;
        }
    }
    if(!flag){
        return ;
    }
}
int main(){
    // freopen("sudoku.in","r",stdin);
    // freopen("sudoku.out","w",stdout);
    for(register int i=0;i<9;i++){
        for(register int j=0;j<9;j++){
            cin>>broad[i][j];
            if(broad[i][j]==0){
                empty[cnt].x=i;
                empty[cnt++].y=j;
            }
        }
    }
    dfs(0);
    cout<<ans<<endl;
    return 0;
}
/*
test1:
    7 0 0 9 0 0 0 0 1
    1 0 0 0 0 5 9 0 0
    0 0 0 2 0 0 0 8 0
    0 0 5 0 2 0 0 0 3
    0 0 0 0 0 0 6 4 8
    4 1 3 0 0 0 0 0 0
    0 0 7 0 0 2 0 9 0
    2 0 1 0 6 0 8 0 4
    0 8 0 5 0 4 0 1 2
*/
/*
test2:
    0 0 0 7 0 2 4 5 3
    9 0 0 0 0 8 0 0 0
    7 4 0 0 0 5 0 1 0
    1 9 5 0 8 0 0 0 0
    0 7 0 0 0 0 0 2 5
    0 3 0 5 7 9 1 0 8
    0 0 0 6 0 1 0 0 0
    0 6 0 9 0 0 0 0 1
    0 0 0 0 0 0 0 0 6
*/

这是原来的代码，超时；

#include<bits/stdc++.h>
using namespace std;
const int score[9][9]={
                    6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,
                    6 ,7 ,7 ,7 ,7 ,7 ,7 ,7 ,6 ,
                    6 ,7 ,8 ,8 ,8 ,8 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,9 ,9 ,9 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,9 ,10,9 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,9 ,9 ,9 ,8 ,7 ,6 ,
                    6 ,7 ,8 ,8 ,8 ,8 ,8 ,7 ,6 ,
                    6 ,7 ,7 ,7 ,7 ,7 ,7 ,7 ,6 ,
                    6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,
                };
struct coor{
    int x,y;
    int vis;
};
coor empty[100];
int cnt,ans=-1;
int broad[20][20];
bool f=true;
int cal(){
    int sum=0;
    for(register int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            sum+=broad[i][j]*score[i][j];
        }
    }
    return sum;
}
bool search(int n,int x,int y){
    for(int i=0;i<9;i++){
        if(broad[x][i]==n){
            return true;
        }
    }
    for(int i=0;i<9;i++){
        if(broad[i][y]==n){
            return true;
        }
    }
    int l=y/3*3,r=l+3;
    int t=x/3*3,b=t+3;
    for(int i=l;i<r;i++){
        for(int j=t;j<b;j++){
            if(broad[j][i]==n){
                return true;
            }
        }
    }
    return false;
}
void dfs(int step){
    if(step==cnt){
        ans=max(ans,cal());
        return ;
    }
    int scal,mins=10,mini;
    for(int i=0;i<cnt;i++){
        scal=0;
        if(empty[i].vis) continue;
        for(int j=1;j<=9;j++){
            if(!search(j,empty[i].x,empty[i].y)){
                scal++;
            } 
        }
        if(mins>scal){
            mins=scal;
            mini=i;
        }
    }
    empty[mini].vis=1;
    bool flag=false;
    for(int i=1;i<=9;i++){
        if(!search(i,empty[mini].x,empty[mini].y)){
            broad[empty[mini].x][empty[mini].y]=i;
            flag=true;
            dfs(step+1);
            broad[empty[mini].x][empty[mini].y]=0;
        }
    }
    if(!flag){
        return ;
    }
}
int main(){
    // freopen("sudoku.in","r",stdin);
    // freopen("sudoku.out","w",stdout);
    for(register int i=0;i<9;i++){
        for(register int j=0;j<9;j++){
            cin>>broad[i][j];
            if(broad[i][j]==0){
                empty[cnt].x=i;
                empty[cnt].vis=0;
                empty[cnt++].y=j;
            }
        }
    }
    dfs(0);
    cout<<ans<<endl;
    return 0;
}
/*
test1:
    7 0 0 9 0 0 0 0 1
    1 0 0 0 0 5 9 0 0
    0 0 0 2 0 0 0 8 0
    0 0 5 0 2 0 0 0 3
    0 0 0 0 0 0 6 4 8
    4 1 3 0 0 0 0 0 0
    0 0 7 0 0 2 0 9 0
    2 0 1 0 6 0 8 0 4
    0 8 0 5 0 4 0 1 2
*/
/*
test2:
    0 0 0 7 0 2 4 5 3
    9 0 0 0 0 8 0 0 0
    7 4 0 0 0 5 0 1 0
    1 9 5 0 8 0 0 0 0
    0 7 0 0 0 0 0 2 5
    0 3 0 5 7 9 1 0 8
    0 0 0 6 0 1 0 0 0
    0 6 0 9 0 0 0 0 1
    0 0 0 0 0 0 0 0 6
*/

这是修改后的代码，结果炸了 优化思路：每次找到还没有填的格子中可能性最小的格子来搜索

求助，怎么优化啊