NOIP2009第四题&靶形数独&解题报告（搜索&判重）
小城和小华都是热爱数学的好学生，最近，他们
不约而同地迷上了数独游戏，好胜的他
们想用数独来一比高低。但普通的数独对他们来
说都过于简单了，于是他们向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
输出样例1：
输入样例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
输出样例2：
思路：话扯了一大堆，结果是一道加强版的N皇后。。。无语。。
难点在于数的九宫格判断重复。
可以将第一行/列设为0行/列，则九宫格为0——8行，0——8列的矩阵，
开2个布尔型2维数组、一个3维数组
h[i,j]:第i行j是否用过；
l[i,j]:第i列j是否用过；
jiu[i mod 3,j mod 3，k]:将9个格子化为一点，第i行，j列，k是否用过；
剩下的就搜索就行了，本人过了19组数据，最后一个数据貌似可以用乱序搜。。
这是第一种搜索，19组是极限了~~~
在已知数据的情况下，我用了倒序搜，过完了。
还有可以用A*算，这里就不简绍了。。。
DLX更复杂。。。我就说说搜索，这个在考场比较现实。。&
& h,l:array[0..8,1..9]
& jiu:array[0..2,0..2,1..9]
& map:array[0..8,0..8]
& total,time:
//==========================================
& assign(input,'sudoku.in'); reset(input);
& assign(output,'sudoku.out');
rewrite(output);
& for i:=0 to 8 do
&& for j:=0 to 8 do
read(map[i,j]);
if map[i,j]&&0 then
h[i,map[i,j]]:=
l[j,map[i,j]]:=
jiu[i div 3,j div 3,map[i,j]]:=
//==========================================
function jisuan:
& for i:=0 to 8 do
&& for j:=0 to 8 do
if (i=0)or(j=0)or(i=8)or(j=8) then
x:=x+map[i,j]*6;
if (i=4)and(j=4) then
x:=x+map[i,j]*10;
if ( ((i=1)or(i=7))
and(j&=1)and(j&=7) )
or ( ((j=1)or(j=7))
and(i&=1)and(i&=7) )
x:=x+map[i,j]*7;
if ( ((i=2)or(i=6))
and(j&=2)and(j&=6) )
or ( ((j=2)or(j=6))
and(i&=2)and(i&=6) )
x:=x+map[i,j]*8;
if ( ((i=3)or(i=5))
and(j&=3)and(j&=5) )
or ( ((j=3)or(j=5))
and(i&=3)and(i&=5) )
x:=x+map[i,j]*9;
//==========================================
procedure find(x,y:longint);
& if (x=-1)and(y=8) then if
total&jisuan then
&& total:=
& //writeln(x,' ',y);
& if map[x,y]&&0
&&& if k=-1 then
begin k:=8; dec(j);
find(j,k);
& if map[x,y]=0 then
&&& for i:=1 to
inc(time); if time&
if (not h[x,i])and(not l[y,i])and(not jiu[x div 3,y div 3,i])
map[x,y]:=i;
h[x,i]:= l[y,i]:= jiu[x div 3,y div 3,i]:=
j:=x; k:=y-1;
if k=-1 then begin k:=8; dec(j);
find(j,k);
h[x,i]:= l[y,i]:= jiu[x div 3,y div 3,i]:=
map[x,y]:=0;
//==========================================
& time:=0;
& total:=0;
& find(8,8);
& if total=0 then writeln('-1')
& else writeln(total);
& close(input);
& close(output);
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。已收藏本页面
这是三年级的数学题，感觉文化不够用了，就第四题我也是问了度娘才明白的……
回复 2楼：谢谢
600*5=3000
这智商基本告别面包车了，给我吧，我送你一副拐
不要忘记0。题目总容易出错的就是特殊值，极值。
下载个“作业帮”扫一下作业就有答案
作为三年数学英语老师告诉你这道题我们班学生做的比我6
后才能发表评论
你可能喜欢的图片笑话
最受欢迎的爆笑笑话拒绝访问 |
| 百度云加速
请打开cookies.
此网站 () 的管理员禁止了您的访问。原因是您的访问包含了非浏览器特征(3a877db1c49143f5-ua98).
重新安装浏览器，或使用别的浏览器}