思维训练游戏-数独
最好的奶茶-家长会黑板报
数独
数独,是一种源自18世纪末的瑞士,后在美国发展、并在日本得以发扬光大的<
br>数字谜题。数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一
定的已知数字和解
题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。
使1-9每个数字在每一行、每一列和每
一宫中都只出现一次。这种游戏全面考验
做题者观察能力和推理能力,虽然玩法简单,但数字排列方式却
千变万化,所以
不少教育者认为数独是训练头脑的绝佳方式。
数独
数独的历史
数独是一种源自18世纪末的瑞士,后在美国发展、并在日本
得以发扬光
大的数学智力拼图游戏。拼图是九宫格(即3格宽×3格高)的正方形状,每
一格又
细分为一个九宫格。在每一个小九宫格中,分别填上1至9的数字,
让整个大九宫格每一列、每一行的数
字都不重复。
数独的基础是数字魔方,它的解也一定是数字魔方。制作一个数独,便
是
使用一个一般的数字魔方,盖住部分数字,成为一个拥有唯一解的数独。
数独前身为“九宫格”
,最早起源于中国。数千年前,我们的祖先就发
明了洛书,其特点较之现在的数独更为复杂,要求纵向、
横向、斜向上的三
个数字之和等于15,而非简单的九个数字不能重复。中国古籍《易经》中的
“九宫图”也源于此,故称“洛书九宫图”。而“九宫”之名也因《易经》
在中华文化发展史上的重要地
位而保存、沿用至今。
1783年,瑞士数学家莱昂哈德·欧拉发明了一种当时称作“拉丁方块”
(Latin Square
)的游戏,这个游戏是一个n×n的数字方阵,每一行和每一
列都是由不重复的n个数字或者字母组成的
。
19世纪70年代,美国的一家数学逻辑游戏杂志《戴尔铅笔字谜和词语游
戏》(Dell
Puzzle Mαgαzines)开始刊登现在称为“数独”的这种游戏,
当时人们称之为“数字拼
图”(Number Place),在这个时候,9×9的81格
数字游戏才开始成型。
填充完整后
1984年4月,在日本游戏杂志《字
谜通讯Nikoil》(《パズル通信ニコリ》)
上出现了“数独”游戏,提出了“独立的数字”的概念
,意思就是“这个数
字只能出现一次”或者“这个数字必须是唯一的”,并将这个游戏命名为
“
数独”(sudoku)。
一位前任香港高等法院的新西兰籍法官高乐德(Wayne Gou
ld)在1997
年3月到日本东京旅游时,无意中发现了。他首先在英国的《泰晤士报》上
发
表,不久其他报纸也发表,很快便风靡全英国,之后他用了6年时间编写
了电脑程式,并将它放在网站上
,使这个游戏很快在全世界流行。从此,这
个游戏开始风靡全球。后来更因数独的流行衍生了许多类似的
数学智力拼图
游戏,例如:数和、杀手数独。
中国大陆是在2007年2月28日正式引入数独. 2007年2月28日,北京
晚报智力休闲数独俱
乐部(数独联盟sudokufederation前身)在新闻大厦举行
加入世界谜题联合会的颁证仪
式,会上谜题联合会秘书长皮特-里米斯特和俱
乐部会长在证书上签字,这标志着北京晚报智力休闲俱乐
部成为世界谜题联
合会的39个成员之一,这也标志着俱乐部走向国际舞台,它将给数独爱好者
带来更多与世界数独爱好者们交流的机会。
元素构成
数独基本元素示意图
单元格:数独中最小的单元,标准数独中共有81个;
行:横向9个单元格的集合;
列:纵向9个单元格的集合;
宫:粗黑线划分的区域,标准数独中为3×3的9个单元格的集合;
已知数:数独初始盘面给出的数字;
候选数:每个空单元格中可以填入的数字。
规则
标准数独的规则为:数独每行、每列及每宫填入数字1-9且不能重复。
基本解法举例
数独解法全是由规则衍生出来的,基本解法分为两类思路,一类为排除法,一类为唯一法。更复杂的解法,最终也会归结到这两大类中。
下边以图
示简单介绍几种解法,只要你花几分钟看一遍,马上就可以开始做数独了。
基础摒除法
基础摒除法就是利用1 ~ 9 的数字在每一行、每一列、每一宫都只能出
现一次的规则进行解题的方法。基础摒除法可以分为行摒除、列摒除、九宫
格摒除。
实际寻找解的过程为:
寻找九宫格摒除解:找到了某数在某一个九宫格可填入的位置只余一个
的情形;意即找到了
该数在该九宫格中的填入位置。
寻找列摒除解:找到了某数在某列可填入的位置只余一个的情形;意即
找到了该数在该列中的填入位置。
寻找行摒除解:找到了某数在某行可填入的位置只余一个的情形;意即
找到了该数在该行中的填入位置。
基础摒除法的提升方法是区块摒除法,是直观法中使用频率最高的方法
之一.
唯一解法
当某列已填数字的宫格达到8个,那么该列剩余宫格能填的数字就只剩下
那个还没出现过的数字了。成为列唯一解.
当某九宫格已填数字的宫格达到8个,那么该九宫
格剩余宫格能填的数字
就只剩下那个还没出现过的数字了。成为九宫格唯一解.
唯余解法
唯余解法就是某宫格可以添入的数已经排除了8个,那么这个宫格的数字
就只能添入那个没
有出现的数字.
区块摒除法
区块摒除法是基础摒除法的提升方法,是直观法中使用频率最高的方法
之一.
余数测试法
所谓余数测试法就是在某行或列,九宫格所填数字比较多,剩余2个或3
个
时,在剩余宫格添入值进行测试的解题方法.
隐性唯一候选数法
当某个数字在某一列
各宫格的候选数中只出现一次时,那么这个数字就
是这一列的唯一候选数了.这个宫格的值就可以确定为
该数字. 这是因为,
按照数独游戏的规则要求每一列都应该包含数字1~9,而其它宫格的候选数都不含有该数,则该数不可能出现在其它的宫格,那么就只能出现在这个宫
格了.
对于唯一候选数出现行,九宫格的情况,处理方法完全相同。
三链数删减法
找出某一列、某一行或某一个九宫格中的某三个宫格候选数中,相异的
数字不超过3个的情形,
进而将这3个数字自其它宫格的候选数中删减掉的
方法就叫做三链数删减法。
隐性三链数删减法
在某行,存在三个数字出现在相同的宫格内,在本行的其它宫格均不包
含这三个数字,我们称这个数对是隐形三链数.那么这三个宫格的候选数中
的其它数字都可以排
除.
当隐形三链数出现在列,九宫格,处理方法是完全相同的.
---------------------------------
修改为:在某行,存在三个候选数字分别出现在三个宫格内,
在本行的其它宫格均不包含这三个
数字,我们称这个数对是隐形三链
数.那么这三个宫格的其它候选数都可以排除.
当隐形三链数出现在列,九宫格,处理方法是完全相同的
或者: 利用“找出某3个数字仅出现
在某行、某列或某一个九宫格的某
三个宫格候选数中的情形,进而将这三个宫格的候选数删减成该3个数
字”
的方法就叫做隐性三链数删减法(Hidden Triples)。
矩形顶点删减法
矩形顶点删减法和直观法讲到的矩形摒除法分析方法是一样的。矩形顶
点删减法在识别时比
较不容易找到,所以最好先使用其它的方法。
三链列删减法
三链列删减法是矩形顶点
删减法的扩展,如果不清楚矩形顶点删减法,
可以参考矩形顶点删减法,以便于更容易理解本节内容。
利用“找出某个数
字在某三列仅出现在相同三行的情形,进而将该数字自这三行其他宫格候选
数
中删减掉”; 或“找出某个数字在某三行仅出现在相同三列的情形,进而
将该数字自这三列其他宫格候
选数中删减掉”的方法 就叫做三链列删减法。
关键数删减法
在进入到解题后期,利用前面讲到的唯一候选数法、隐性唯一候选数法、
区块删减法、数对删减法、隐性数对删减法、
三链数删减法、隐性三链数删
减法、矩形顶点删减法、 三链列删减法都无法有进展的时候,可以考虑使
用
关键数删减法。关键数删减法就是在后期找到一个数,这个数在行(或列,
九宫格)仅出现两
次的数字。我们假定这个数在其中一个宫格类,继续求解,
如果发生错误,则确定我们的
假设错误。如果继续求解仍然出现困难,不妨
假设这个数在另外一个宫格,看能不能得到错误。这就是关
键数删减法.
排除法
当某一列,某一行或某一宫里已填7个数字时,可采用排除法
,排除不
可能出现在这个格子的数,从而确定格子里应该填什么数。比如某一行已填1,
3,4
,5,7,8,9,还剩2,6,而其中一个空格所在的列上已有了2,可知
这个空格里不可能是2,那
么另外一个空格里一定是2,那么这个空格里一定
是6。
当某一列,某一行或某一宫里已填6个数字时,也可采用排除法。
变形数独概述
数独发展到今天,类型已经多种多样,如果按不同条件细分绝不下百种,
而且数量还在增加
中。大家平时可以常见的变形数独,如:对角线数独、锯
齿数独、杀手数独等等。
对角线数独
锯齿数独
杀手数独
所谓变形数独,即改变一些标准数独的条
件或规则,形成的新型数独题目,
有的变形数独也会同时具备多种变形条件,变形条件如下:
1、使用数字的数量不同可以有4字数独、6字数独、16字数独、25字数
独等等;
2、增加限制区域的类别可以有对角线数独、额外区域数独、彩虹数独等
等;
3、宫形发生变化有锯齿数独;多个数独叠加起来有连体数独、武士数独、
超级数独等等
4、用其它元素代替已知数字有字母数独、骰子数独、数码数独等等;
5、利用单元格内数字之和或乘积等关系有杀手数独、边框数独、箭头数
独、魔方数独、算式数独等等;
6、利用相邻单元格内数字的关系有连续数独、不等号数独、堡垒数独、
XV数独、黑白点数独等等;
7、单元格限制数字属性有奇偶数独、大中小数独等等;
8、利用数独外提示数字有边缘观测数独、摩天楼数独等等;
9、按禁止同一数字位置有无缘数独、无马数独等等;
10、非方形数独有圆环数独、立方体数独、六角数独、蜂窝数独等等;
11、需要多个数独条件配合才能解题的有三合一数独、双胞数独等等。
以上11种分类并非全部变
化条件,只是常见的大类,还有不少变形数独
未举例,其实变形的条件不会有极限的,只要你有想象力,
可以创造出属于
你自己的新型变形数独。虽然数独条件变换多端,但有一条始终不变的绝对
条件
——同一限制区域内不能出现重复数字。只要符合这个条件,就没有脱
离“数独”的范畴。
靶形数独
Noip2009赛题
Noip2009提高组复赛最后一题:靶形数独。
靶形数独
考察搜索顺序优化,预处理出所有结点的决策,卡时搜索方法。
问题描述
小城和小华都是热爱数学的好学生,最近,他们不约而同地迷上了数独
游戏,好胜的他们想用数独来一比
高低。但普通的数独对他们来说都过于简
单了,于是他们向 Z博士请教,Z
博士拿出了他最近发明的“靶形数独” ,
作为这两个孩子比试的题目。
靶形数独的方格同普通数独一样,在 9 格宽×9 格高的大九宫格中有 9
个 3
格宽×3 格高的小九宫格(用粗黑色线隔开的)
。在这个大九宫格中,
有一些数字是已知的,根据这些数字,利用逻辑推理,在其他的空格上填入
1
到 9 的数字。每个数字在每个小九宫格内不能重复出现,每个数字在每行、
每列也不能重
复出现。但靶形数独有一点和普通数独不同,即每一个方格都
有一个分值,而且如同一个靶子一样,离中
心越近则分值越高。
上图具体的分值分布是:最里面一格(黄色区域)为 10
分,黄色区域
外面的一圈(红色区域)每个格子为 9
分,再外面一圈(蓝色区域)每个格
子为 8分,蓝色区域外面一圈(棕色区域)每个格子为
7分,最外面一圈(白
色区域)每个格子为 6 分,如上图所示。
比赛的要求是:每个人必须完成一个给定的数独(每个给定数独可能有
不同的填法) ,而且要
争取更高的总分数。而这个总分数即每个方格上的分
值和完成这个数独时填在相应格上的数字的乘积的总
和。如图,在以下的这
个已经填完数字的靶形数独游戏中,总分数为
2829。游戏规定,将以总分数
的高低决出胜负。
由于求胜心切,小城找到了善于编程的你,让你帮他求出,对于给定的
靶形数独,能够得到的最高分数。
输入数据
一共 9 行。每行 9 个整数(每个数都在 0—9 的范围内)
,表示一个
尚未填满的数独方格,未填的空格用“0”表示。每两个数字之间用一个空格
隔开。
输出数据
输出可以得到的靶形数独的最高分数。如果这个数独无解,则输出整数
-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
数据规模
40%的数据,数独中非 0数的个数不少于 30。
80%的数据,数独中非 0数的个数不少于 26。
100%的数据,数独中非 0
数的个数不少于 24。
解题报告
首先进行最原始的数独搜索,我们可以开3个标记数组
heng,shu,box:array[0..9,0..9] of boolean;
我们每次就填入数字可以进行如下判断
if (heng[x,i]=false) and
(shu[y,i]=false) and (box[((x-1) div
3)*3+((y-1) div 3)+1,i]=false) then
这次的数据我们倒的搜索要比正的搜索效率高
对于完全不加优化的程序期望分值为70分
如果加上卡时间的操作,期望得分95分
如果随机化搜索顺序,期望得分100分
如果加入启发函数信息,期望得分100分
代码清单(pascal实现)
program sudoku;
const
value:array[1..9,1..9] of
integer=((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));
type node=record
juece:array[0..9] of integer;
square,lie,hang:integer;
end;
var
way:array[1..81] of node;
temp:node;
find:boolean;
i,j,k,w,point,bestpoint:integer;
square,lie,hang:array[1..9,1..9] of boolean;
map:array[1..9,1..9] of integer;
function
fs(i,j:integer):integer;
begin
if (i<=3)
and (j<=3) then fs:=1;
if (i<=3) and (j>=4)
and (j<=6) then fs:=2;
if (i<=3) and (j>=7)
then fs:=3;
if (i>=4) and (i<=6) and (j<=3)
then fs:=4;
if (i>=4) and (i<=6) and (j>=4)
and (j<=6) then fs:=5;
if (i>=4) and (i<=6)
and (j>=7) then fs:=6;
if (i>=7) and (j<=3)
then fs:=7;
if (i>=7) and (j>=4) and (j<=6)
then fs:=8;
if (i>=7) and (j>=7) then fs:=9;
end;
procedure
search(i:integer);
var k:integer;
begin
if i=82 then
begin
if
point>bestpoint then bestpoint:=point;
find:=true;
exit;
end;
if
way[i].juece[0]=0 then search(i+1);
for
k:=1 to way[i].juece[0] do
if not
hang[way[i].hang,way[i].juece[k]] and not
lie[way[i].lie,way[i].juece[k]] and not
square[way[i].square,way[i].juece[k]] then
begin
hang[way[i].hang,way[i].juece[k]]:=true;
lie[way[i].lie,way[i].juece[k]]:=true;
square[way[i].square,way[i].juece[k]]:=true;
point:=point+way[i].juece[k]*value[way[i].hang,way
[i].lie];
search(i+1);
hang[way[i].hang,way[i].juece[k]]:=false;
lie[way[i].lie,way[i].juece[k]]:=false;
square[way[i].square,way[i].juece[k]]:=false;
point:=point-
way[i].juece[k]*value[way[i].hang,way[i].lie];
end;
end;
begin
point:=0;
bestpoint:=0;
find:=false;
assign(input,'datasudokusudoku1 in');
reset(input);
for i:=1 to 9 do
begin
for j:=1 to 9 do
begin
read(map[i,j]);
if map[i,j]>0 then
begin
point:=point+map[i,j]*value[i,j];
hang[i,map[i,j]]:=true;
lie[j,map[i,j]]:=true;
square[fs(i,j),map[i,j]]:=true;
end;
end;
readln;
end;
close(input);
for i:=1 to 9 do
for
j:=1 to 9 do
begin
way[(i-1)*9+j].hang:=i;
way[(i-1)*9+j].lie:=j;
way[(i-1)*9+j].square:=fs(i,j);
w:=0;
way[(i-1)*9+j].juece[0]:=w;
if map[i,j]=0
then
begin
for k:=1 to 9 do
if not hang[i,k] and not lie[j,k] and not
square[fs(i,j),k] then
begin
inc(w);
way[(i-1)*9+j].juece[0]:=w;
way[(i-1)*9+j].juece[w]:=k;
end;
end;
end;
for i:=1 to 80 do
for j:=1 to 81-i do
if
way[j].juece[0]>way[j+1].juece[0] then
begin
temp:=way[j+1];
way[j+1]:=way[j];
way[j]:=temp;
end;
search(1);
assign(output,'');
rewrite(output);
if not find then
writeln('-1')
else writeln(bestpoint);
close(output);
end.
数独的近亲
谜题(Pazzle):排除文化差异对做题者的影响,只用数字和图形表示
的逻辑推理游戏。
数独是谜题(Pazzle)中的一个分支,由于其规则简单、种类众多从而
从众多谜题脱
颖而出,成为大众熟知的数字谜题。
不过除了数独以外,还有不少谜题也非常出
色,也有众多的拥护者,而
且与数独有千丝万缕的关系。数独爱好者同样不能错过这些优秀的逻辑推理<
br>游戏。下面简单介绍几类谜题:
数和(Kakuro):与杀手数独很像的一类谜题,规
则要求同行、同列(同
一段)数字不能重复,且每段数字之和等于左边和上边的提示数字。
数图(NonogramsGriddlers):根据盘面周围的数字提示,把盘中涂成
符合条件的图
案,很像“十字绣”。
数回(Slither Link):游戏由0,1,2,3四个数字组
成。每一个数字,
代表四周划线的数目,并在最后成为一个不间断、不分岔的回路。
数
墙(Nurikabe):数墙的世界,是一个非黑即白的二元世界;在游戏
中,你要决定的是,那些格
子需要涂黑,那一些应该留白。
数连(Number Link):与数独一样,数连是一个简
单明快的游戏。你只
需要把属于相同数字的同伴,以线连接起来。不过,这个游戏看起来非常简
单,实际上是很有深度的。
图独(tudoku):数独的一种扩展,将数字换成有趣的图形,看似
一样,
但换成图形后大大增强了数独趣味性,使游戏不会那么枯燥,很合适小孩子
玩,即动脑又
锻炼记忆力。
给出最少数字且有唯一解的数独
数独初盘最少可以有17个数。
与数独终盘相对应,一个数独游戏给出的初始条件称为初盘。由
于规则
所限,给出的初盘数字个数必须在32以下。
一般常见的初盘数字个数在22—
28之间,而数独爱好者们常问的一个问
题是:最少给出多少个数字,数独游戏才确保有唯一解?具体地
说:最少需
要在初盘中给出多少个数字,使得移除其中任何一个数字该数独游戏便没有
唯一解。
事实上,这个问题是数独中最有数学趣味的问题之一,并且至今仍未得
到解决。但数学家们
估计,这个数字很可能是17.17个数字的最小唯一解初
盘是由一名日本数独爱好者发现的。澳大利亚
数学家GordonRoyle已经收集
了36628个17个数字的唯一解初盘,而爱尔兰数学家Ga
ry McGuire则致力
于寻找16个数字的唯一解初盘,但至今仍无发现。部分数学家开始退而求
其
次,转而寻找只有两个解的16个数字初盘。
统计学家根据一个统计学原理曾随机地
构造了大量17个数字的初盘,发
现其中有唯一解的初盘只有数个未被GordonRoyle教授发现
,这意味着,最
小唯一解初盘问题的最终答案可能正是17:因为从理论上说,如果16个数字
的唯一解终盘存在,那么每一个必将引起65个17个数字唯一解终盘的增加,
而在研究中至今没有观察
到这一效应。
17个数的数独
求解数独的程序代码
求解数独所有解(适合所有数独)的PASCAL程序
var a:packed array[1..9,1..9] of longint;
i,j,k,p,l,m,n,ii,ans,mm,oo:longint;
s,s1:packed array[0..100,1..4] of longint;
x,y,xy:packed array[0..9,-1..9] of boolean;
横向,纵向,九宫
的检验
t,tt,u:boolean;
opo:longint;
ll:packed
array[0..9,0..9,-1..11] of longint;
存储每个空格可
能出现的数字 提高程序效率
function
max(a,b:longint):longint;
begin
if
b>a then exit(b)
else exit(a);
end;
function choose2(x:longint):longint;
begin
case x of
0..3:exit(1);
4..6:exit(2);
7..9:exit(3);
end;
end;
function iff:boolean; 搜索结束条件
begin
if (k<1) then exit(false)
else exit(true);
end;
function
pa(i,j:longint):longint; 得到九宫格编号
var
o,kk,jj,ii:longint;
begin
o:=choose2(i);
kk:=choose2(j);
case o of
1:jj:=0;
2:jj:=3;
3:jj:=6;
end;
exit(jj+kk);
end;
begin
fillchar(x,sizeof(x),true);
fillchar(y,sizeof(y),true);
fillchar(xy,sizeof(xy),true);
for i:=1 to
9 do
for j:=1 to 9 do
begin
read(ii);
a[i,j]:=ii;
if ii=0 then
begin
inc(n);
s1[n,1]:=j;
s1[n,2]:=i;
end
else begin
x[i,ii]:=false;
y[j,ii]:=false;
xy[pa(i,j),ii]:=false;
end;
end;
for i:=1 to 9 do
for j:=1 to 9 do
begin
for oo:=1 to 9 do
if
x[i,oo]and y[j,oo] and xy[pa(i,j),oo] then
begin
inc(ll[i,j,-1]);
ll[i,j,ll[i,j,-1]]:=oo;
end;
end;
for i:=1 to n do
s[i]:=s1[n-i+1];
k:=1; i:=0;
t:=true;tt:=false;
while iff do
begin
if t
then
begin
for
i:=ll[s[k,2],s[k,1],-1] downto 0 do
if
(x[s[k,2],ll[s[k,2],s[k,1],i]]and
y[s[k,1],ll[s[k,2],s[k,1],i]]) and
xy[pa(s[k,2],s[k,1]),ll[s[k,2],s[k,1],i]] then
begin
t:=true;
break;
end;
end
else begin i:=s[k,4];
tt:=false;
repeat
dec(i);
until ((x[s[k,2],ll[s[k,2],s[k,1],i]]and
y[s[k,1],ll[s[k,2],s[k,1],i]]) and
xy[pa(s[k,2],s[k,1]),ll[s[k,2],s[k,1],i]])or
(i<1);
end;
if i<1 then begin
s[k,3]:=0; a[s[k,2],s[k,1]]:=0;
dec(k);
t:=false;i:=s[k,3];
x[s[k,2],i]:=true;y[s[k,1],i]:=true;
向上回溯
xy[pa(s[k,2],s[k,1]),i]:=true;
end
else t:=true;
if t then
begin
s[k,4]:=i;
s[k,3]:=ll[s[k,2],s[k,1],i];
a[s[k,2],s[k,1]]:=s[k,3];
x[s[k,2],s[k,3]]:=false;
y[s[k,1],s[k,3]]:=false;
xy[pa(s[k,2],s[k,1]),s[k,3]]:=false;
inc(k);
end;
tt:=false;
if
k>n then
begin
inc(opo);
writeln(opo); 计数器
for i:=1 to 9 do
begin
for j:=1 to 9 do
write(a[i,j],' ');
writeln;
end;
writeln;
mm:=0;
x[s[k-1,2],s[k-1,3]]:=true;
y[s[k-1,1],s[k-1,3]]:=true;
xy[pa(s[k-1,2],s[k-1,1]),s[k-1,3]]:=true;
dec(k);
t:=false;
end;
end;
writeln(opo);
end.
求解数独的简单C语言程序(适合仅有唯一解的数独)*数独求解*
#include
void print(int a[9][9]) *格式化输出数独*
{int i,j;
for(i=0;i<9;i++)
{for(j=0;j<9;j++)
printf(
printf(
}
}
void ini_logo(int
logo[10][9][9],int arr[9][9]) *初始化标志数
组*
{int i,j,k,p,r,s,t;
for(i=0;i<9;++i)
for(j=0;j<9;++j)
if(arr[i][j]!=0)
for(k=1;k<=9;++k)logo[k][i][j]=1;
for(i=0;i<9;++i)
for(j=0;j<9;++j)
if(arr[i][j]!=0)
{p=arr[i][j];
for(r=0;r<9;++r)
{logo[p][i][r]=1;logo[p][r][j]=1;}
for(s=(i3)*3;s<(i3)*3+3;++s)
for(t=(j3)*3;t<(j3)*3+3;++t)
logo[p][s][t]=1;
}
}
int
add(int arr[9][9],int logo[10][9][9],int m,int
n,int k)
*arr[m][n]插入数字,修改arr,logo数组*
{int i,s,p,t;
arr[m][n]=k;
for(p=1;p<=9;++p)
logo[p][m][n]=1;
for(i=0;i<9;++i)
{logo[k][m][i]=1;
logo[k][i][n]=1;
}
for(s=(m3)*3;s<(m3)*3+3;++s)
for(t=(n3)*3;t<(n3)*3+3;++t)
logo[k][s][t]=1;
}
int check(int
logo[10][9][9],int arr[9][9]) *检测行列和小九宫
格*
{int i,j,k,p,q,r,s,t,m,n,tag=0;
*tag标志本轮是否修改*
for(k=1;k<=9;++k)
{for(i=0;i<9;++i)
{p=0;q=0;
for(j=0;j<9;++j)
{if(logo[k][i][j]==0){r=j;p++;} *检测行*
if(logo[k][j][i]==0){s=j;q++;} *检测列*
}
if(p==1){tag=1;add(arr,logo,i,r,k);}
if(q==1){tag=1;add(arr,logo,s,i,k);}
*满足一个添加的条件,修改
arr,logo数组和标志tag*
}
for(i=0;i<9;i=i+3) *检测小九宫格*
for(j=0;j<9;j=j+3)
{t=0;
for(m=i;m for(n=j;n
if(t==1){tag=1;add(arr,logo,q,s,k);}
}
}
return(tag);
}
main()
{
int arr[9][9]={
0,0,0,0,0,0,0,0,0, *数独初始化,其中0表示数字未给出*
0,2,3,0,0,0,7,8,0,
1,0,0,4,0,6,0,0,9,
4,0,0,0,5,0,0,0,1,
9,0,0,0,0,0,0,0,6,
0,6,0,0,0,0,0,9,0,
0,0,5,0,0,0,8,0,0,
0,0,0,3,0,1,0,0,0,
0,0,0,0,9,0,0,0,0
},
logo[10][9][9]={0},i,j;
ini_logo(logo,arr);
while(check(logo,arr)==1) *当一轮没有检测出,即结束*
{}
print(arr);
}
==
==================================================
==============
===============
Java解法(循环递归法):
private boolean counting(int
row, int col){
Fill the number as 1 to 9
for (int num = 1; num < 10; num++){
if (isLegal(row, col, num)){ Check whether the
number is legal
matrix[row][col] = num;
int nextRow = (row + 1 > 8) ? 0 : (row + 1);
int nextCol = (col + 1 > 8) ? 0 : (col + 1);
if (nextCol != 0) { Not last column
if (counting(row, nextCol))
return true;
} else if (nextRow != 0) { Last column
if (counting(nextRow, nextCol))
return
true;
} else { Last cell
return
true;
}
Get false with the current
selection, clear it and go on
matrix[row][col] = 0;
}
}
From 1 to 9, no number is legal, return false
return false;
}
上面只列出了主函数,如果要调用,还需要初始化matrix二维数组,然后
写以下语句:
if (counting(0, 0) == true)
有解
else
无解
数独的段位以及评选方法
一段掌握数
独概念及其分类、数独元素和规则、数独符号;掌握单区唯
一解法、简单排除法;45分钟内正确完成1
星九字标准题3道。二段:掌
握数独概念及其分类、数独元素和规则、数独符号;掌握单元排除法;了解
对角线数独和不规则数独的解题规则;45分钟内正确完成2星九字标准题
2道、对角线数独或
不规则数独1道。三段:掌握数独概念及其分类、数独
元素和规则、数独符号;掌握多区唯一解法、区块
排除法、数组占位法;掌
握杀手数独的解题规则;45分钟内正确完成3星九字标准题2道、杀手数独题1道。四段: 掌握候选数概念及候选数列表、链的概念及分类;掌握初
级候选数删减法;熟练
掌握对角线数独、不规则数独、杀手数独的解题技巧;
45分钟内正确完成4星九字标准题1道、杀手数
独1道、不规则数独或对
角线数独1道。五段: 掌握候选数概念及候选数列表、链的概念及分类;熟<
br>练掌握初级候选数删减法;熟练掌握各类题型的解题技巧;对于新题型的反
应能力比较快速,45
分钟内正确完成4星九字标准题2道、新变形数独题
2道。六段: 掌握候选数概念及候选数列表、链的
概念及分类;熟练掌握高
级候选数删减法;对于新题型的反应能力非常快速,45分钟内正确完成5星九字标准题2道、新变形数独2道。七段:
45分钟内正确完成5星九字
标准题2道、新变形数独题3道。或是中国数独锦标赛冠军。八段:
世界数
独锦标赛前八名。九段: 世界数独锦标赛前三名,同时提交一篇论文,经中
国数独联盟
理事会审核通过。(证书2年内有效,2年后须复核,如不过即降
段)。
数独单元格的叫法
从第1行到第9行分别叫A、B、C、D、E、F、G、H、I行,从第1列到
第9列分别
叫1、2、3、4、5、6、7、8、9列。读单元格的名称时,字母放
前,数字放后。比如说第3行第
5列就叫C5,第9行第6列叫I6,以此类推。