思维训练游戏-数独

1、思维训练游戏-数独数独数独，是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数字谜题。数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次。这种游戏全面考验做题者观察能力和推理能力，虽然玩法简单，但数字排列方式却千变万化，所以不少教育者认为数独是训练头脑的绝佳方式。数独数独的历史数独是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格（即3格宽3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格

2、中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。数独的基础是数字魔方，它的解也一定是数字魔方。制作一个数独，便是使用一个一般的数字魔方，盖住部分数字，成为一个拥有唯一解的数独。数独前身为“九宫格”，最早起源于中国。数千年前，我们的祖先就发明了洛书，其特点较之现在的数独更为复杂，要求纵向、横向、斜向上的三个数字之和等于15，而非简单的九个数字不能重复。中国古籍易经中的“九宫图”也源于此，故称“洛书九宫图”。而“九宫”之名也因易经在中华文化发展史上的重要地位而保存、沿用至今。1783年，瑞士数学家莱昂哈德欧拉发明了一种当时称作“拉丁方块”（Latin Square）的游戏，这

3、个游戏是一个nn的数字方阵，每一行和每一列都是由不重复的n个数字或者字母组成的。19世纪70年代，美国的一家数学逻辑游戏杂志戴尔铅笔字谜和词语游戏（Dell Puzzle Mgzines）开始刊登现在称为“数独”的这种游戏，当时人们称之为“数字拼图”（Number Place），在这个时候，99的81格数字游戏才开始成型。填充完整后1984年4月，在日本游戏杂志字谜通讯Nikoil（通信）上出现了“数独”游戏，提出了“独立的数字”的概念，意思就是“这个数字只能出现一次”或者“这个数字必须是唯一的”，并将这个游戏命名为“数独”（sudoku）。一位前任香港高等法院的新西兰籍法官高乐德（Wayne

4、 Gould）在1997年3月到日本东京旅游时，无意中发现了。他首先在英国的泰晤士报上发表，不久其他报纸也发表，很快便风靡全英国，之后他用了6年时间编写了电脑程式，并将它放在网站上，使这个游戏很快在全世界流行。从此，这个游戏开始风靡全球。后来更因数独的流行衍生了许多类似的数学智力拼图游戏，例如：数和、杀手数独。中国大陆是在2007年2月28日正式引入数独. 2007年2月28日，北京晚报智力休闲数独俱乐部(数独联盟sudokufederation前身)在新闻大厦举行加入世界谜题联合会的颁证仪式，会上谜题联合会秘书长皮特-里米斯特和俱乐部会长在证书上签字，这标志着北京晚报智力休闲俱乐部成为世界谜

5、题联合会的39个成员之一，这也标志着俱乐部走向国际舞台，它将给数独爱好者带来更多与世界数独爱好者们交流的机会。元素构成数独基本元素示意图单元格：数独中最小的单元，标准数独中共有81个；行：横向9个单元格的集合；列：纵向9个单元格的集合；宫：粗黑线划分的区域，标准数独中为33的9个单元格的集合；已知数：数独初始盘面给出的数字；候选数：每个空单元格中可以填入的数字。规则标准数独的规则为：数独每行、每列及每宫填入数字1-9且不能重复。基本解法举例数独解法全是由规则衍生出来的，基本解法分为两类思路，一类为排除法，一类为唯一法。更复杂的解法，最终也会归结到这两大类中。下边以图示简单介绍几种解法，只要你花

6、几分钟看一遍，马上就可以开始做数独了。基础摒除法基础摒除法就是利用1 9 的数字在每一行、每一列、每一宫都只能出现一次的规则进行解题的方法。基础摒除法可以分为行摒除、列摒除、九宫格摒除。实际寻找解的过程为：寻找九宫格摒除解：找到了某数在某一个九宫格可填入的位置只余一个的情形；意即找到了该数在该九宫格中的填入位置。寻找列摒除解：找到了某数在某列可填入的位置只余一个的情形；意即找到了该数在该列中的填入位置。寻找行摒除解：找到了某数在某行可填入的位置只余一个的情形；意即找到了该数在该行中的填入位置。基础摒除法的提升方法是区块摒除法,是直观法中使用频率最高的方法之一. 唯一解法当某列已填数字的宫格达到

7、8个,那么该列剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为列唯一解. 当某九宫格已填数字的宫格达到8个,那么该九宫格剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为九宫格唯一解. 唯余解法唯余解法就是某宫格可以添入的数已经排除了8个,那么这个宫格的数字就只能添入那个没有出现的数字. 区块摒除法区块摒除法是基础摒除法的提升方法,是直观法中使用频率最高的方法之一. 余数测试法所谓余数测试法就是在某行或列,九宫格所填数字比较多,剩余2个或3个时,在剩余宫格添入值进行测试的解题方法. 隐性唯一候选数法当某个数字在某一列各宫格的候选数中只出现一次时，那么这个数字就是这一列的唯一候选数了这

8、个宫格的值就可以确定为该数字这是因为，按照数独游戏的规则要求每一列都应该包含数字19，而其它宫格的候选数都不含有该数，则该数不可能出现在其它的宫格，那么就只能出现在这个宫格了对于唯一候选数出现行,九宫格的情况，处理方法完全相同。三链数删减法找出某一列、某一行或某一个九宫格中的某三个宫格候选数中，相异的数字不超过3个的情形，进而将这3个数字自其它宫格的候选数中删减掉的方法就叫做三链数删减法。隐性三链数删减法在某行，存在三个数字出现在相同的宫格内，在本行的其它宫格均不包含这三个数字，我们称这个数对是隐形三链数那么这三个宫格的候选数中的其它数字都可以排除当隐形三链数出现在列，九宫格，处理方法是完全相

9、同的修改为：在某行，存在三个候选数字分别出现在三个宫格内，在本行的其它宫格均不包含这三个数字，我们称这个数对是隐形三链数那么这三个宫格的其它候选数都可以排除当隐形三链数出现在列，九宫格，处理方法是完全相同的或者：利用“找出某3个数字仅出现在某行、某列或某一个九宫格的某三个宫格候选数中的情形，进而将这三个宫格的候选数删减成该3个数字”的方法就叫做隐性三链数删减法(Hidden Triples)。矩形顶点删减法矩形顶点删减法和直观法讲到的矩形摒除法分析方法是一样的。矩形顶点删减法在识别时比较不容易找到，所以最好先使用其它的方法。三链列删减法三链列删减法是矩形顶点删减法的扩展，如果不清楚矩形顶点删减

10、法，可以参考矩形顶点删减法，以便于更容易理解本节内容。利用“找出某个数字在某三列仅出现在相同三行的情形，进而将该数字自这三行其他宫格候选数中删减掉”；或“找出某个数字在某三行仅出现在相同三列的情形，进而将该数字自这三列其他宫格候选数中删减掉”的方法就叫做三链列删减法。关键数删减法在进入到解题后期，利用前面讲到的唯一候选数法、隐性唯一候选数法、区块删减法、数对删减法、隐性数对删减法、三链数删减法、隐性三链数删减法、矩形顶点删减法、三链列删减法都无法有进展的时候，可以考虑使用关键数删减法。关键数删减法就是在后期找到一个数，这个数在行（或列，九宫格）仅出现两次的数字。我们假定这个数在其中一个宫格类，

11、继续求解，如果发生错误，则确定我们的假设错误。如果继续求解仍然出现困难，不妨假设这个数在另外一个宫格，看能不能得到错误。这就是关键数删减法. 排除法当某一列，某一行或某一宫里已填7个数字时，可采用排除法，排除不可能出现在这个格子的数，从而确定格子里应该填什么数。比如某一行已填1，3，4，5，7，8，9，还剩2，6，而其中一个空格所在的列上已有了2，可知这个空格里不可能是2，那么另外一个空格里一定是2，那么这个空格里一定是6。当某一列，某一行或某一宫里已填6个数字时，也可采用排除法。变形数独概述数独发展到今天，类型已经多种多样，如果按不同条件细分绝不下百种，而且数量还在增加中。大家平时可以常见的

12、变形数独，如：对角线数独、锯齿数独、杀手数独等等。对角线数独锯齿数独杀手数独所谓变形数独，即改变一些标准数独的条件或规则，形成的新型数独题目，有的变形数独也会同时具备多种变形条件，变形条件如下：1、使用数字的数量不同可以有4字数独、6字数独、16字数独、25字数独等等；2、增加限制区域的类别可以有对角线数独、额外区域数独、彩虹数独等等；3、宫形发生变化有锯齿数独；多个数独叠加起来有连体数独、武士数独、超级数独等等4、用其它元素代替已知数字有字母数独、骰子数独、数码数独等等；5、利用单元格内数字之和或乘积等关系有杀手数独、边框数独、箭头数独、魔方数独、算式数独等等；6、利用相邻单元格内数字的关系

13、有连续数独、不等号数独、堡垒数独、XV数独、黑白点数独等等；7、单元格限制数字属性有奇偶数独、大中小数独等等；8、利用数独外提示数字有边缘观测数独、摩天楼数独等等；9、按禁止同一数字位置有无缘数独、无马数独等等；10、非方形数独有圆环数独、立方体数独、六角数独、蜂窝数独等等；11、需要多个数独条件配合才能解题的有三合一数独、双胞数独等等。以上11种分类并非全部变化条件，只是常见的大类，还有不少变形数独未举例，其实变形的条件不会有极限的，只要你有想象力，可以创造出属于你自己的新型变形数独。虽然数独条件变换多端，但有一条始终不变的绝对条件同一限制区域内不能出现重复数字。只要符合这个条件，就没有脱离

14、“数独”的范畴。靶形数独Noip2009赛题Noip2009提高组复赛最后一题：靶形数独。靶形数独考察搜索顺序优化，预处理出所有结点的决策，卡时搜索方法。问题描述小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。靶形数独的方格同普通数独一样，在 9 格宽9 格高的大九宫格中有 9 个 3 格宽3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 1到

15、9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红色区域）每个格子为 9 分，再外面一圈（蓝色区域）每个格子为 8分，蓝色区域外面一圈（棕色区域）每个格子为 7分，最外面一圈（白色区域）每个格子为 6 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字

16、的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 2829。游戏规定，将以总分数的高低决出胜负。由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。输入数据一共 9 行。每行 9 个整数（每个数都在 09 的范围内），表示一个尚未填满的数独方格，未填的空格用“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

17、 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:array0.9,0.9 of boolean; 我们每次就填入数字可以进行如下判断if (hengx,i=false) and (shuy,i=false) and (bo

18、x(x-1) div 3)*3+(y-1) div 3)+1,i=false) then 这次的数据我们倒的搜索要比正的搜索效率高对于完全不加优化的程序期望分值为70分如果加上卡时间的操作，期望得分95分如果随机化搜索顺序，期望得分100分如果加入启发函数信息，期望得分100分代码清单（pascal实现）program sudoku; const value:array1.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

19、,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:array0.9 of integer; square,lie,hang:integer; end; var way:array1.81 of node; temp:node; find:boolean; i,j,k,w,point,bestpoint:integer; square,lie,hang:array1.9,1.9 of boolean; map:a

20、rray1.9,1.9 of integer; function fs(i,j:integer):integer; begin if (i=3) and (j=3) then fs:=1; if (i=4) and (j=6) then fs:=2; if (i=7) then fs:=3; if (i=4) and (i=6) and (j=4) and (i=4) and (j=4) and (i=7) then fs:=6; if (i=7) and (j=7) and (j=4) and (j=7) and (j=7) then fs:=9; end; procedure search

21、(i:integer); var k:integer; begin if i=82 then begin if pointbestpoint then bestpoint:=point; find:=true; exit; end; if wayi.juece0=0 then search(i+1); for k:=1 to wayi.juece0 do if not hangwayi.hang,wayi.juecek and not liewayi.lie,wayi.juecek and not squarewayi.square,wayi.juecek then begin hangway

22、i.hang,wayi.juecek:=true; liewayi.lie,wayi.juecek:=true; squarewayi.square,wayi.juecek:=true; point:=point+wayi.juecek*valuewayi.hang,wayi.lie; search(i+1); hangwayi.hang,wayi.juecek:=false; liewayi.lie,wayi.juecek:=false; squarewayi.square,wayi.juecek:=false; point:=point-wayi.juecek*valuewayi.hang

23、,wayi.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(mapi,j); if mapi,j0 then begin point:=point+mapi,j*valuei,j; hangi,mapi,j:=true; liej,mapi,j:=true; squarefs(i,j),mapi,j:=true; end; en

24、d; 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.juece0:=w; if mapi,j=0 then begin for k:=1 to 9 do if not hangi,k and not liej,k and not squarefs(i,j),k then begin inc(w); way(i-1)*9+j.j

25、uece0:=w; way(i-1)*9+j.juecew:=k; end; end; end; for i:=1 to 80 do for j:=1 to 81-i do if wayj.juece0wayj+1.juece0 then begin temp:=wayj+1; wayj+1:=wayj; wayj:=temp; end; search(1); assign(output,dataoutsudoku.out); rewrite(output); if not find then writeln(-1) else writeln(bestpoint); close(output)

26、; end. 数独的近亲谜题（Pazzle）：排除文化差异对做题者的影响，只用数字和图形表示的逻辑推理游戏。数独是谜题（Pazzle）中的一个分支，由于其规则简单、种类众多从而从众多谜题脱颖而出，成为大众熟知的数字谜题。不过除了数独以外，还有不少谜题也非常出色，也有众多的拥护者，而且与数独有千丝万缕的关系。数独爱好者同样不能错过这些优秀的逻辑推理游戏。下面简单介绍几类谜题：数和（Kakuro）：与杀手数独很像的一类谜题，规则要求同行、同列（同一段）数字不能重复，且每段数字之和等于左边和上边的提示数字。数图（NonogramsGriddlers)：根据盘面周围的数字提示，把盘中涂成符合条件的图案

27、，很像“十字绣”。数回（Slither Link）：游戏由0,1,2,3四个数字组成。每一个数字，代表四周划线的数目，并在最后成为一个不间断、不分岔的回路。数墙（Nurikabe）：数墙的世界，是一个非黑即白的二元世界；在游戏中，你要决定的是，那些格子需要涂黑，那一些应该留白。数连（Number Link）：与数独一样，数连是一个简单明快的游戏。你只需要把属于相同数字的同伴，以线连接起来。不过，这个游戏看起来非常简单，实际上是很有深度的。图独（tudoku）：数独的一种扩展，将数字换成有趣的图形，看似一样，但换成图形后大大增强了数独趣味性，使游戏不会那么枯燥，很合适小孩子玩，即动脑又锻炼记忆力

28、。给出最少数字且有唯一解的数独数独初盘最少可以有17个数。与数独终盘相对应，一个数独游戏给出的初始条件称为初盘。由于规则所限，给出的初盘数字个数必须在32以下。一般常见的初盘数字个数在2228之间，而数独爱好者们常问的一个问题是：最少给出多少个数字，数独游戏才确保有唯一解？具体地说：最少需要在初盘中给出多少个数字，使得移除其中任何一个数字该数独游戏便没有唯一解。事实上，这个问题是数独中最有数学趣味的问题之一，并且至今仍未得到解决。但数学家们估计，这个数字很可能是17.17个数字的最小唯一解初盘是由一名日本数独爱好者发现的。澳大利亚数学家GordonRoyle已经收集了36628个17个数字的唯

29、一解初盘，而爱尔兰数学家Gary McGuire则致力于寻找16个数字的唯一解初盘，但至今仍无发现。部分数学家开始退而求其次，转而寻找只有两个解的16个数字初盘。统计学家根据一个统计学原理曾随机地构造了大量17个数字的初盘，发现其中有唯一解的初盘只有数个未被GordonRoyle教授发现，这意味着，最小唯一解初盘问题的最终答案可能正是17：因为从理论上说，如果16个数字的唯一解终盘存在，那么每一个必将引起65个17个数字唯一解终盘的增加，而在研究中至今没有观察到这一效应。17个数的数独求解数独的程序代码求解数独所有解（适合所有数独）的PASCAL程序var a:packed array1.9,

30、1.9 of longint; i,j,k,p,l,m,n,ii,ans,mm,oo:longint; s,s1:packed array0.100,1.4 of longint; x,y,xy:packed array0.9,-1.9 of boolean; /横向，纵向，九宫的检验t,tt,u:boolean; opo:longint; ll:packed array0.9,0.9,-1.11 of longint; /存储每个空格可能出现的数字提高程序效率function max(a,b:longint):longint; begin if ba then exit(b) else ex

31、it(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 (k1) 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); c

32、ase 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); ai,j:=ii; if ii=0 then begin inc(n); s1n,1:=j; s1n,2:=i; end else begin xi,ii:=false; yj,ii:=false;

33、 xypa(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 xi,ooand yj,oo and xypa(i,j),oo then begin inc(lli,j,-1); lli,j,lli,j,-1:=oo; end; end; for i:=1 to n do si:=s1n-i+1; k:=1; i:=0; t:=true;tt:=false; while iff do begin if t then begin for i:=llsk,2,sk,1,-1 d

34、ownto 0 do if (xsk,2,llsk,2,sk,1,iand ysk,1,llsk,2,sk,1,i) and xypa(sk,2,sk,1),llsk,2,sk,1,i then begin t:=true; break; end; end else begin i:=sk,4; tt:=false; repeat dec(i); until (xsk,2,llsk,2,sk,1,iand ysk,1,llsk,2,sk,1,i) and xypa(sk,2,sk,1),llsk,2,sk,1,i)or (i1); end; if in then begin inc(opo);

35、 writeln(opo); / 计数器for i:=1 to 9 do begin for j:=1 to 9 do write(ai,j, ); writeln; end; writeln; mm:=0; xsk-1,2,sk-1,3:=true; ysk-1,1,sk-1,3:=true; xypa(sk-1,2,sk-1,1),sk-1,3:=true; dec(k); t:=false; end; end; writeln(opo); end. 求解数独的简单C语言程序（适合仅有唯一解的数独）/*数独求解*/ #include void print(int a99) /*格式化输出数

36、独*/ int i,j; for(i=0;i9;i+) for(j=0;j9;j+) printf(%d ,aij); printf(n); void ini_logo(int logo1099,int arr99) /*初始化标志数组*/ int i,j,k,p,r,s,t; for(i=0;i9;+i) for(j=0;j9;+j) if(arrij!=0) for(k=1;k=9;+k)logokij=1; for(i=0;i9;+i) for(j=0;j9;+j) if(arrij!=0) p=arrij; for(r=0;r9;+r) logopir=1;logoprj=1; for

37、(s=(i/3)*3;s(i/3)*3+3;+s) for(t=(j/3)*3;t(j/3)*3+3;+t) logopst=1; int add(int arr99,int logo1099,int m,int n,int k) /*arrmn插入数字,修改arr,logo数组*/ int i,s,p,t; arrmn=k; for(p=1;p=9;+p) logopmn=1; for(i=0;i9;+i) logokmi=1; logokin=1; for(s=(m/3)*3;s(m/3)*3+3;+s) for(t=(n/3)*3;t(n/3)*3+3;+t) logokst=1; in

38、t check(int logo1099,int arr99) /*检测行列和小九宫格*/ int i,j,k,p,q,r,s,t,m,n,tag=0; /*tag标志本轮是否修改*/ for(k=1;k=9;+k) for(i=0;i9;+i) p=0;q=0; for(j=0;j9;+j) if(logokij=0)r=j;p+; /*检测行*/ if(logokji=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数组和标

39、志tag*/ for(i=0;i9;i=i+3) /*检测小九宫格*/ for(j=0;j9;j=j+3) t=0; for(m=i;mi+3;+m) for(n=j;nj+3;+n) if(logokmn=0)q=m;s=n;t+; if(t=1)tag=1;add(arr,logo,q,s,k); return(tag); main() int arr99= 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 , logo1099=0,i,j; ini_logo(logo,arr); while(check(logo,arr)=1) /*当一轮没有检测出，即结束