P1074 靶形数独（搜索+剪枝）

本文主要是介绍P1074 靶形数独（搜索+剪枝），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

洛谷P1074 题目描述

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 1 到 9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

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

游戏规定，将以总分数的高低决出胜负。由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能

够得到的最高分数。

题目分析：
从左上向右下依次搜索
剪枝
可行性剪枝
每格所填的数只能是对应行、列和宫中没出现过的
最优化剪枝
如果后面使用不保证限制条件的贪心仍达不到已经搜到的最优值，则剪枝

对应代码：

#include <stdio.h>
#include<math.h>
using namespace std;
int box[10][10];
bool row[10][10] {{0,0}}; //行
//bool 0为false 其余值均为true
bool column[10][10] {{0,0}}; //列
bool NS[10][10];//第i个九宫格已经填写j
int MaxSum=0;
int Maxx(int a,int b)
{if(a>b)return a;elsereturn b;
}
int sum()//计算值
{int score=0;for(int i=1; i<=9; i++)for(int j=1; j<=9; j++)score+=box[i][j]*(10-Maxx(fabs(i-5),fabs(j-5)));return score;
}
void dfs(int i,int j)
{// printf("%d %d\n",i,j);if(i==9&&j==9){if(box[i][j]!=0){int t=sum();if(t>MaxSum)MaxSum=t;return;}for(int k=1; k<=9; k++){if(row[i][k]||column[j][k]||NS[(i-1)/3*3+(j-1)/3+1][k])continue;else{box[i][j]=k;break;}}box[i][j]=0;int t=sum();if(t>MaxSum)MaxSum=t;return;}if(box[i][j]==0){for(int k=1; k<=9; k++){if(row[i][k]||column[j][k]||NS[(i-1)/3*3+(j-1)/3+1][k])continue;//同一行同一列同一个小九宫格都不可以已经存在Kbox[i][j]=k;row[i][k]=true;column[j][k]=true;NS[(i-1)/3*3+(j-1)/3+1][k]=true;dfs(i+j/9,j%9+1);box[i][j]=0;row[i][k]=false;column[j][k]=false;NS[(i-1)/3*3+(j-1)/3+1][k]=false;}}else{dfs(i+j/9,j%9+1);}
}
int main()
{int i,j;for(i=1; i<=9; i++)for(j=1; j<=9; j++)scanf("%d",&box[i][j]);for(i=1; i<=9; i++)for(j=1; j<=9; j++){if(box[i][j]!=0){row[i][box[i][j]]=true;//第i行有了此数column[j][box[i][j]]=true;//第j列有了此数NS[(i-1)/3*3+(j-1)/3+1][box[i][j]]=true;//对应小九宫格中有了此数}}dfs(1,1);printf("%d",MaxSum);return 0;
}

这种暴力的求解方式，果然好多数据是过不去的。

那么就需要继续剪枝，玩数独的时候我们一般思路肯定是先把能确定的填上，比如样例一，第8行第8列，那个位置可能填的数特别少。基于这种思路，我们先从容易确定的地方dfs，下一步走到下一个最容易确定的点，这样解答树能少枚举很多。
怎样判断一个点的确定度呢？当然是看看它的行填上了几个、列填上了几个、宫填上了几个了。

这里只判断了行和列，试了一下已经可以AC。

#include <stdio.h>
#include<math.h>
using namespace std;
int box[10][10];
bool row[10][10] {{0,0}}; //行
//bool 0为false 其余值均为true
bool column[10][10] {{0,0}}; //列
bool NS[10][10];//第i个九宫格已经填写j
int row_q[10],column_q[10],q=0;//q表示已经有数字的个数
int MaxSum=-1;
const int scoree[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 Maxx(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int sum()//计算值
{
int score=0;
for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
score+=box[i][j]*scoree[i][j];
return score;
}
void dfs(int i,int j,int q)
{
//printf("%d ",q);
if(q==81)
{
MaxSum=Maxx(MaxSum,sum());
return;
}
for(int k=1; k<=9; k++)
{
if(row[i][k]||column[j][k]||NS[(i-1)/3*3+(j-1)/3+1][k])
continue;//同一行同一列同一个小九宫格都不可以已经存在K
box[i][j]=k;
row[i][k]=true;
column[j][k]=true;
NS[(i-1)/3*3+(j-1)/3+1][k]=true;
row_q[i]++,column_q[j]++;
int tempr=-1,nextr=0,tempc=-1,nextc=0;
for(int m=1; m<=9; m++)
{
if(row_q[m]>tempr&&row_q[m]<9)
tempr=row_q[m],nextr=m;
}
for(int n=1; n<=9; n++)
{
if(column_q[n]>tempc&&!box[nextr][n])
tempc=column_q[n],nextc=n;
}
//printf("%d %d ",nextr,nextc);
dfs(nextr,nextc,q+1);
box[i][j]=0;
row[i][k]=false;
column[j][k]=false;
NS[(i-1)/3*3+(j-1)/3+1][k]=false;
row_q[i]--,column_q[j]--;
}
}
int main()
{
int i,j;
for(i=1; i<=9; i++)
for(j=1; j<=9; j++)
scanf("%d",&box[i][j]);
for(i=1; i<=9; i++)
for(j=1; j<=9; j++)
{
if(box[i][j]!=0)
{
row[i][box[i][j]]=true;//第i行有了此数
column[j][box[i][j]]=true;//第j列有了此数
NS[(i-1)/3*3+(j-1)/3+1][box[i][j]]=true;//对应小九宫格中有了此数
row_q[i]++;
column_q[j]++;
q++;
}
}
int tempr=-1,r,tempc=-1,c;
for(int i=1; i<=9; i++)
{
if(row_q[i]>tempr&&row_q[i]<9)
tempr=row_q[i],r=i;
}
for(int j=1; j<=9; j++)
{
if(column_q[j]>tempc&&!box[r][j])
tempc=column_q[j],c=j;
}
//printf("%d %d %d\n",q,r,c);
dfs(r,c,q);
printf("%d",MaxSum);
return 0;
}