题目描述

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z博士请教，Z博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在9格宽×9格高的大九宫格中有9个3格宽×3格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入1到9的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

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


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

输入描述:

一共9行，每行9个整数（每个数都在0—9的范围内），表示一个尚未填满的数独方格，未填满的空格用“0”表示。每两个数字之间用一个空格隔开。

输出描述:

输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。

示例1

输入
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
输出
2829

示例2

输入
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
输出
2852

备注

40%的数据，数独中非0数的个数不少于30。
80%的数据，数独中非0数的个数不少于26。
100%的数据，数独中非0数的个数不少于24。

解答

我只想说，这题根本不是大家想象的那么坑！！！（可能会被打233）

一个比较显然的事实是，在你玩数独的时候一般思路肯定是先把能确定的填上，比如样例一，第8行第8列，那个位置可能填的数特别少。

基于这种思路，我们先从容易确定的地方dfs，下一步走到下一个最容易确定的点，这样解答树能少枚举很多。

怎样判断一个点的确定度呢？当然是看看它的行填上了几个、列填上了几个、宫填上了几个了。但我比较懒就没判断宫，但可能是数据水？还是过了，虽然跑的不快，3000多ms。

另外，给大家安利一个dfs模板，好记、好应用， 

void dfs(答案,搜索层数,其他参数){
    if(层数==maxdeep){
        更新答案;
        return; 
    }
    (剪枝) 
    for(枚举下一层可能的状态){
        更新全局变量表示状态的变量;
        dfs(答案+新状态增加的价值,层数+1,其他参数);
        还原全局变量表示状态的变量;
    }
}
下面是我巨丑的代码（不喜请喷，别打脸233） 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
int getint(){
    int x=0,f=1; char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return f*x;
}
const int MAXN=12;
const 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 row[MAXN][MAXN],col[MAXN][MAXN],area[MAXN][MAXN],sdk[MAXN][MAXN];
int row_cnt[MAXN],col_cnt[MAXN],cnt,ans=-1;
inline int id(int i,int j){return (i-1)/3*3+1+(j-1)/3;}
inline int calc(){
    int tmp=0;
    for(int i=1;i<=9;++i)
        for(int j=1;j<=9;++j)
            tmp+=score[i][j]*sdk[i][j];
    return tmp;
}
void dfs(int r,int c,int cpl){    
    if(cpl==81){
        ans=max(ans,calc());
        return ;
    }
    for(int k=1;k<=9;++k){
        if(row[r][k]||col[c][k]||area[id(r,c)][k]) continue;
        row[r][k]=true;
        col[c][k]=true;
        area[id(r,c)][k]=true;
        row_cnt[r]++,col_cnt[c]++;
        sdk[r][c]=k;
        int tmpr=-1,nxt_r=0,tmpc=-1,nxt_c=0;
        for(int i=1;i<=9;++i)
            if(row_cnt[i]>tmpr&&row_cnt[i]<9)
                tmpr=row_cnt[i],nxt_r=i;
        for(int j=1;j<=9;++j)
            if(col_cnt[j]>tmpc&&(!sdk[nxt_r][j]))
                tmpc=col_cnt[j],nxt_c=j;
        dfs(nxt_r,nxt_c,cpl+1);
        row[r][k]=false;
        col[c][k]=false;
        area[id(r,c)][k]=false;
        row_cnt[r]--,col_cnt[c]--;
        sdk[r][c]=0;
    }
}
int main(){    
    for(int i=1;i<=9;++i){
        for(int j=1;j<=9;++j){
            sdk[i][j]=getint();
            if(sdk[i][j]!=0){
                row[i][sdk[i][j]]=true;
                col[j][sdk[i][j]]=true;
                area[id(i,j)][sdk[i][j]]=true;
                row_cnt[i]++,col_cnt[j]++;
                cnt++;
            }
        }
    }
    int tmpr=-1,r,tmpc=-1,c;
    for(int i=1;i<=9;++i)
        if(row_cnt[i]>tmpr&&row_cnt[i]<9)
            tmpr=row_cnt[i],r=i;
    for(int j=1;j<=9;++j)
        if(col_cnt[j]>tmpc&&(!sdk[r][j]))
            tmpc=col_cnt[j],c=j;
    dfs(r,c,cnt);
    cout<<ans<<endl;
}



来源：majt