主要是优化搜索顺序
从选择较少的点开始，可以大大提高效率
在search(x,y)找点的时候，对于一个空点（x y），设置一个评分score：
score=min｛ 横线x上能填的数字个数，竖线y上...个数，所在大方块中...个数 ｝
选取score最小的点搜索
代码：
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N = ;
const int Size = N+; int ans=-;
int data[Size][Size];
bool a[Size][Size],b[Size][Size],c[Size][Size];//行 列 大方格
int numA[Size],numB[Size],numC[Size];
int dx[]={,,,-};
int dy[]={,,-,};
int dic[Size][Size]={
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,}
};
int len[Size]={ ,
,,,,
}; int getscore(){
int ans=;
int x,y;
for(int temp=;temp<=N/;temp++){
x=y=temp;
for(int k=;k<;k++){
for(int i=;i<=len[temp];i++){
ans+=data[x][y]*(temp+);
x+=dx[k];y+=dy[k];
}
}
}
ans+=data[][]*;
return ans;
} void search(int& x,int& y){
x=y=;
int best=,score;
for(int i=;i<=N;i++){
for(int j=;j<=N;j++){
if(data[i][j]==){
score=min(numA[i],numB[j]);
score=min(score,numC[dic[i][j]]);
if(score<best){
x=i;y=j;
best=score;
}
}
}
}
} void dfs(){
int x,y;
search(x,y);
if(x==){
ans=max(ans,getscore());
//exit(0);
return;
}
bool num[Size];
memset(num,true,sizeof(num));
int ff=dic[x][y];
for(int k=;k<=N;k++){
if(a[x][k]==true||b[y][k]==true||c[ff][k]==true)
num[k]=false;
}
for(int k=;k<=N;k++){
if(num[k]==true){
data[x][y]=k;
a[x][k]=true;b[y][k]=true;c[ff][k]=true;
numA[x]--;numB[y]--;numC[ff]--;
dfs();
numA[x]++;numB[y]++;numC[ff]++;
a[x][k]=false;b[y][k]=false;c[ff][k]=false;
data[x][y]=;
}
}
return;
} int main(){
freopen("1174.in","r",stdin);
for(int i=;i<=;i++)numA[i]=numB[i]=numC[i]=;
int x;
for(int i=;i<=N;i++){
for(int j=;j<=N;j++){
cin>>x;
if(x!=){
a[i][x]=true;numA[i]--;
b[j][x]=true;numB[j]--;
c[dic[i][j]][x]=true;numC[dic[i][j]]--;
}
data[i][j]=x;
}
}
dfs();
cout<<ans<<endl; fclose(stdin);
return ;
}