什么是靶形数独，利用靶形数独解题

题目描述：

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。

但普通的数独对他们来说都过于简单了，于是他们向Z博士请教，Z博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。
  

    靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格（用粗黑色线隔开的）。
  

  

    在这个大九宫格中，有一些数字是已知的，根据这些 数字，利用逻辑推理，在其他的空格上填入 1 到9 的数字。
  

  

    每个数字在每个小九宫格内不能 重复出现，每个数字在每行、每列也不能重复出现。
  

  

    但靶形数独有一点和普通数独不同，即 每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）
  

  

    上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈
  
（红 色区域）每个格子为 9 分，再外面一圈（蓝色区域）每个格子为 8 分，蓝色
区域外面一圈（棕 色区域）每个格子为7 分，最外面一圈（白色区域）每个格子为6 
  

     分，如上图所示。
  

  

    比赛的 要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法）
  
，而且要争取 更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填
在相应格上的数字 的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏
中，总分数为 2829。游 戏规定，将以总分数的高低决出胜负。
由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能
够得到的最高分数。
样例输入： 样例输出：
7 0 0 9 0 0 0 0 1								2829
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 

在做这道题之前，我们先做一下这题：

数独游戏：

给出一个9*9的表格，部分格子已经填好数。请填完所有空白格子，使得表格每一行、每
一列、每个3*3的九宫格，都恰好填满这9个数字。
样例输入：
0 6 0 1 0 4 0 5 0
0 0 8 3 0 5 6 0 0
2 0 0 0 0 0 0 0 1
8 0 0 4 0 7 0 0 6
0 0 6 0 0 0 3 0 0
7 0 0 9 0 1 0 0 4
5 0 0 0 0 0 0 0 2
0 0 7 2 0 6 9 0 0
0 4 0 5 0 8 0 7 0

输出样例：
9 6 3   1 7 4   2 5 8
1 7 8   3 2 5   6 4 9
2 5 4   6 8 9   7 3 1

8 2 1   4 3 7   5 9 6
4 9 6   8 5 2   3 1 7
7 3 5   9 6 1   8 2 4 

5 8 9   7 1 3   4 6 2
3 1 7   2 4 6   9 8 5
6 4 2   5 9 8   1 7 3 

没话说，就是纯粹的暴力。
代码如下：

#include <bits/stdc++.h>
using namespace std;
int a[10][10];
bool h[10][10],s[10][10],g[10][10],l;

void cha(int x,int y) {
	if(l) return ;
	if(x==10) {
		for(int i=1;i<=9;i++) {
			for(int j=1;j<=9;j++) {
				printf("%d ",a[i][j]);
				if(j%3==0)
					printf(" ");			
			}
			printf("\n");
			if(i%3==0)
				printf("\n");
		}
		printf("\n");
		l=1;
		return ;
	}
	if(a[x][y]!=0) {
		if(y==9) cha(x+1,1);
		else cha(x,y+1);
		return ;
	}
	for(int i=1;i<=9;i++) {
		if(h[x][i]==0 && s[y][i]==0 && g[(((x-1)/3)*9+((y-1)/3)*3+1)/3+1][i]==0) {
			h[x][i]=1,s[y][i]=1,g[(((x-1)/3)*9+((y-1)/3)*3+1)/3+1][i]=1,a[x][y]=i;
			if(y==9) cha(x+1,1);
			else cha(x,y+1);
			h[x][i]=0,s[y][i]=0,g[(((x-1)/3)*9+((y-1)/3)*3+1)/3+1][i]=0,a[x][y]=0;
		}
	}
	return ;
}

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]) {
				h[i][a[i][j]]=1;
				s[j][a[i][j]]=1;
				g[(((i-1)/3)*9+((j-1)/3)*3+1)/3+1][a[i][j]]=1;				
			}

		}
	}
	cha(1,1);
	return 0;
} 

如上代码，我们可以做靶形数独。
代码：

#include <bits/stdc++.h>
using namespace std;
int a[10][10],ans;
bool h[10][10],s[10][10],g[10][10];
int t[10][10]={{},{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 yu() {
	int sum=0;
	for(int i=1;i<=9;i++) {
		for(int j=1;j<=9;j++)
			sum+=a[i][j]*t[i][j];
	}
	return sum;
}

void cha(int x,int y) {
	if(x==10) {
		if(yu()>ans)
			ans=yu();
		return ;
	}
	if(a[x][y]!=0) {
		if(y==9) cha(x+1,1);
		else cha(x,y+1);
		return ;
	}
	for(int i=1;i<=9;i++) {
		if(h[x][i]==0 && s[y][i]==0 && g[(((x-1)/3)*9+((y-1)/3)*3+1)/3+1][i]==0) {
			h[x][i]=1,s[y][i]=1,g[(((x-1)/3)*9+((y-1)/3)*3+1)/3+1][i]=1,a[x][y]=i;
			if(y==9) cha(x+1,1);
			else cha(x,y+1);
			h[x][i]=0,s[y][i]=0,g[(((x-1)/3)*9+((y-1)/3)*3+1)/3+1][i]=0,a[x][y]=0;
		}
	}
	return ;
}

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]) {
				h[i][a[i][j]]=1;
				s[j][a[i][j]]=1;
				g[(((i-1)/3)*9+((j-1)/3)*3+1)/3+1][a[i][j]]=1;				
			}

		}
	}
	cha(1,1);
	printf("%d",(ans==0?-1:ans));
	return 0;
} 

呜呜呜，打码一小时，超时85分。
我们考虑一下剪枝：
关于优化，一个很广为人知的数独优化就是从未知量少的行开始搜(我还是太弱了，居然不知道)。我不清楚为什么要这样，据说是减小搜索树的高度。但实测表明，这对单个点进行搜索的顺序也有很大的优化，不加只能拿到70分。但关于搜索树的理论只能解释按行搜对搜索树的影响。我更愿意相信这是一种随机的定序方式以应对凑好的不随机的数据。由于最近在研究剪枝，自己又瞎搞出来一种，属于最优性剪枝，就是预判后面的点在最好甚至略优于最好的情况下能否到达已经搜到的最优解，若不能则直接回溯。这个方法经测试表明能在大点优30ms(然并卵)。
代码：

#include <bits/stdc++.h>
using namespace std;
int a[10][10],ans=-1,h[10][10],s[10][10],g[10][10],r[10],n[10];
int t[10][10]={{6,6,6,6,6,6,6,6,6},{6,7,7,7,7,7,7,7,6},{6,7,8,8,8,8,8,7,6},{6,7,8,9,9,9,8,7,6},{6,7,8,9,10,9,8,7,6},{6,7,8,9,9,9,8,7,6},{6,7,8,8,8,8,8,7,6},{6,7,7,7,7,7,7,7,6},{6,6,6,6,6,6,6,6,6}};

bool cmp(int x,int y) {
	return n[x]<n[y];
}

void cha(int dk,int sum,int la) {
	if(dk==81) {
		ans=max(ans,sum);
		return ;
	}
	if(sum+9+la*9<=ans) return ;
	int i=r[dk/9],j=dk%9,q=i/3*3+j/3;
	if(a[i][j])
		cha(dk+1,sum+a[i][j]*t[i][j],la-a[i][j]);
	else {
		for(int k=1;k<=9;k++) {
			if(!h[i][k] && !s[j][k] && !g[q][k]) {
				h[i][k]=1,s[j][k]=1,g[q][k]=1;
				cha(dk+1,sum+k*t[i][j],la-k);
				h[i][k]=0,s[j][k]=0,g[q][k]=0;
			}
		}
	}
	return ;
}

int main() {
	for(int i=0;i<9;i++) {
		r[i]=i;
		for(int j=0;j<9;j++) {
			scanf("%d",&a[i][j]);
			if(a[i][j])
				h[i][a[i][j]]=1,s[j][a[i][j]]=1,g[i/3*3+j/3][a[i][j]]=1;
			else
				n[i]++;
		}
	}
	sort(r,r+9,cmp);
	cha(0,0,405);
	printf("%d",ans);
	return 0;
} 

本文地址：https://blog.csdn.net/sxhlrLX/article/details/107620351