深搜+剪枝

计算方格(x,y)所在小九宫格的公式：(x-1)/3*3+(y-1)/3+1

方格的分值直接用一个数组储存

剪枝：玩过数独的人应该知道，我们需要从未知数字少的一行开始填，所以先按照每一行已知数的数目从大到小排序，先处理已知数多的行

用三维数组vis中的
vis[0][line][i]表示第line行的i是否被取过;
vis[1][column][i]表示第column列的i是否被取过;
vis[3][palace][i]表示第palace个小九宫格的i是否被取过.

Code: 
#include <bits/stdc++.h>
using namespace std;
int score[10][10]=
{
    {0,0,0,0,0,0,0,0,0,0},
    {0,6,6,6,6,6,6,6,6,6},
    {0,6,7,7,7,7,7,7,7,6},
    {0,6,7,8,8,8,8,8,7,6},
    {0,6,7,8,9,9,9,8,7,6},
    {0,6,7,8,9,10,9,8,7,6},
    {0,6,7,8,9,9,9,8,7,6},
    {0,6,7,8,8,8,8,8,7,6},
    {0,6,7,7,7,7,7,7,7,6},
    {0,6,6,6,6,6,6,6,6,6}
};
int mp[15][15];
int vis[4][15][15];
struct node{
   int cnt,id;
}a[15];
int palace(int x,int y)
{
    return (x-1)/3*3+(y-1)/3+1;
}
bool cmp(node x,node y){return x.cnt>y.cnt;}
int tot=1,ans=0,sum=-1;
void dfs(int line,int column)
{
    if(tot>=10)
    {
        sum=max(sum,ans);
        return ;
    }
    if(column==10)
    {
        tot++;
        dfs(a[tot].id,1);
        tot--;
        return ;
    }
    if(!mp[line][column])
    {
        for(int i=1;i<=9;i++)
        {
            if(vis[0][line][i] || vis[1][column][i] || vis[2][palace(line,column)][i])continue;
            vis[0][line][i]=1;
            vis[1][column][i]=1;
            vis[2][palace(line,column)][i]=1;
            mp[line][column]=i;
            ans+=i*score[line][column];
            dfs(line,column+1);
            vis[0][line][i]=0;
            vis[1][column][i]=0;
            vis[2][palace(line,column)][i]=0;
            mp[line][column]=0;
            ans-=i*score[line][column];
        }
    }
    else dfs(line,column+1);
    return;
}
int main()
{
    for(int i=1;i<=9;i++)
    {
        a[i].id=i;
        for(int j=1;j<=9;j++)
        {
            cin>>mp[i][j];
            if(mp[i][j]!=0)
            {
                vis[0][i][mp[i][j]]=1;
                vis[1][j][mp[i][j]]=1;
                vis[2][palace(i,j)][mp[i][j]]=1;
                a[i].cnt++;ans+=mp[i][j]*score[i][j];
            }
        }
    }
    sort(a+1,a+10,cmp);
    dfs(a[1].id,1);
    cout<<sum<<endl;
    return 0;
}