靶形数独（dfs+剪枝）

题目描述 Description
小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他
们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z 博士请教，
Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。
靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有9 个3 格宽×3 格
高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些

数字，利用逻辑推理，在其他的空格上填入1 到9 的数字。每个数字在每个小九宫格内不能
重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即
每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。

上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红
色区域）每个格子为9 分，再外面一圈（蓝色区域）每个格子为8 分，蓝色区域外面一圈（棕
色区域）每个格子为7 分，最外面一圈（白色区域）每个格子为6 分，如上图所示。比赛的
要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取
更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字
的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为2829。游
戏规定，将以总分数的高低决出胜负。

由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能
够得到的最高分数。

思路：首先想暴力，枚举每个点放什么数再判断，复杂度。。
由于每个点的价值和位置是不变的，考虑数独要求每行每列每个小九宫格内不允许有重复数字，我们在输入时就把不合法的情况都记录下来，这样每次判断都是O(1),每次更新最大值，这样复杂度就会大大降低。
但是，这样还是可能会超时。我们再考虑，每次放置一个数后，都会对其他还没有放置数字格子产生影响，如果我们可以从产生影响最小的格子开始搜，那我们的dfs树将会大大缩小。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int hang[10][10];
int lie[10][10];
int jgg[10][10];
int a[10][10];
int ans=0;
int val[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 zw[10][10]={0,0,0,0,0,0,0,0,0,0,
                0,1,1,1,2,2,2,3,3,3,
                0,1,1,1,2,2,2,3,3,3,
                0,1,1,1,2,2,2,3,3,3,
                0,4,4,4,5,5,5,6,6,6,            
                0,4,4,4,5,5,5,6,6,6,                
                0,4,4,4,5,5,5,6,6,6,                
                0,7,7,7,8,8,8,9,9,9,                
                0,7,7,7,8,8,8,9,9,9,
                0,7,7,7,8,8,8,9,9,9};//九宫格
int recond[10][10];//影响
int tot=0;//需要填的格子个数
inline void dfs(int t)
{
    if(t>tot)
    {
        int now=0;
        for(int i=1;i<=9;i++)
        {
            for(int j=1;j<=9;j++)
            {
                if(!a[i][j])
                {
                    return;
                }
                else
                {
                    now+=a[i][j]*val[i][j];
                }
            }
        }
        ans=max(ans,now);
        return;
    }
    memset(recond,0,sizeof(recond));
    int x,y;
    int minn=1e9;
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            if(!a[i][j])
            {
                for(int k=1;k<=9;k++)
                {
                    if(!hang[i][k]&&!lie[j][k]&&!jgg[zw[i][j]][k])
                    {
                        recond[i][j]++;
                    }
                }
                if(minn>recond[i][j])
                {
                    x=i,y=j;
                    minn=recond[i][j];
                }
            }
        }
    }
    if(minn==1e9)
    {
        return;
    }
    for(int i=1;i<=9;i++)
    {
        if(!hang[x][i]&&!lie[y][i]&&!jgg[zw[x][y]][i])
        {   
                a[x][y]=i;
                hang[x][i]=lie[y][i]=1;
                jgg[zw[x][y]][i]=1;
                dfs(t+1);
                hang[x][i]=lie[y][i]=jgg[zw[x][y]][i]=0;
                a[x][y]=0;
        }
    }                           
}
int main()
{

    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j])
            {
                lie[j][a[i][j]]=1;
                hang[i][a[i][j]]=1;
                jgg[zw[i][j]][a[i][j]]=1;
            }
            else
            {
                tot++;
            }
        }
    }
    dfs(1);
    if(ans==0)
    {
        printf("-1\n");
    }
    else
    {
        printf("%d\n",ans);
    }

    return 0;
}