百度百科—数独 - 推理及计算 我爱数学网-数学爱好者的家园-中国专业化的数学论坛之一

我爱数学网-数学爱好者的家园-中国专业化的数学论坛之一

查看: 3111|回复: 21

[标准数独] 百度百科—数独

[复制链接]

264

主题

506

帖子

1万

积分

版主

Rank: 7Rank: 7Rank: 7

积分
15511

精华达人

QQ
发表于 2014-9-15 21:39:45 | 显示全部楼层 |阅读模式
本帖最后由 东方老师 于 2014-9-25 16:12 编辑

百度百科—数独
数独(すうどく,Sūdoku)是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复
独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。
1起源

既然“数独”有一个字是“数”,人们也往往会联想到数学,那就不妨从大家都知道的数学家欧拉说起,但凡想了解数独历史的玩家在网络、书籍中搜索时,共同会提到的就是欧拉的“拉丁方块(Latin square)”,如下图:
拉丁方块的规则:每一行(Row)、每一列(Column)均含1-N(N即盘面的规格),不重复。这与前面提到的标准数独非常相似,但少了一个宫的规则。
2组成元素
九宫格(Grid)
水平方向有九横行,垂直方向有九纵列的矩形,画分八十一个小正方形,称为九宫格(Grid),如图一所示,是数独(Sudoku)的作用范围。
数独元素 - 九宫格[1]

单元(Unit)画分
2.1 水平方向的每一横行有九格,每一横行称为行(Row),编号如图二所示。
数独元素 - 单元[1]

2.2 垂直方向的每一纵列有九格,每一纵列称为列(Column),编号如图三所示。
数独元素 - 列[1]

2.3 三行与三列相交之处有九格,每一单元称为小九宫(Box、Block),简称宫,如图四用粗线标示者。(在killer数独中,宫往往用单词Nonet表示)
数独元素 - 宫[1]

2.4 上述行、列、宫统称为单元(Unit)
2.5 由三个连续宫组成大区块(Chute),分大行区块(Floor)及大列区块(Tower)。
第一大行区块:由第一宫、第二宫、第三宫组成。
第二大行区块:由第四宫、第五宫、第六宫组成。
第三大行区块:由第七宫、第八宫、第九宫组成。
第一大列区块:由第一宫、第四宫、第七宫组成。
第二大列区块:由第二宫、第五宫、第八宫组成。
第三大列区块:由第三宫、第六宫、第九宫组成。
格位(Cell)编号
格位按所处的行列单元赋予坐标值,如图五所示。
数独元素 - 格位[1]

坐标有多种标示法,有横行A..I,纵列1..9(如中国),也有横行1..9,纵列A..I(如日本),这两种标示容易混淆,故最被广泛使用的是横行R1..R9,纵列C1..C9的标示法。
提示数(Clue)
在九宫格的格位填上一些数字,做为填数判断的线索(Hint),称为提示数(Clue),如图六所示。
数独元素 - 提示数[1]

3近代发展
20世纪70年代,人们在美国纽约的一本益智杂志《MathPuzzles and Logic Problems》上发现了这个游戏,当时被称为填数字(Number Place),这也是目前公认的数独最早的见报版本。1984年一位日本学者将其介绍到了日本,发表在Nikoli公司的一本游戏杂志《パズル通信ニコリ》上,当时起名为“Suuji wa dokushin ni kagiru”,后来觉得这个名字太长,就改名为“sudoku”,其中“su”是数字的意思,“doku”是单一的意思。这个名字也是国际上对数独的比较通用的叫法。后来一位前任香港高等法院的新西兰籍法官高乐德(WayneGould)在1997年3月到日本东京旅游时,无意中发现了。他首先在英国的《***》上发表,不久其他报纸也发表,很快便风靡全英国,之后他用了6年时间编写了电脑程式,并将它放在网站上(这个网站也就是著名的数独玩家论坛),后来因一些原因,网站被关闭,幸好数独大师GlennFowler恢复了数据,玩家论坛有了新处所。在90年代国内就有部分的益智类书籍开始刊登,南海出版社在2005年出版了《数独1-2》,随后日本著名数独制题人西尾彻也的《数独挑战》也由辽宁教育出版社出版。《北京晚报》、《扬子晚报》、《羊城晚报》、《新民晚报》、《成都商报》等等报纸媒体也先后刊登了数独游戏。
4解题方法
解题的本质有二:隐性唯一解(HiddenSingle)及显性唯一(NakedSingle),他们的名称是在候选数法的基础上命名的。
根据解题本质发展出来的解题方法有二种:
摒除法
摒除法:用数字去找单元内唯一可填空格,称为摒除法,数字可填唯一空格称为摒余解(隐性唯一解)。
根据不同的作用范围,摒余解可分为下述三种:
1.1 数字可填唯一空格在「宫」单元称为宫摒余解(Hidden Single in Box),这种解法称宫摒除法。
1.2 数字可填唯一空格在「行」单元称为行摒余解(Hidden Single in Row),这种解法称行摒除法。
1.3 数字可填唯一空格在「列」单元称为列摒余解(Hidden Single in Column),这种解法称列摒除法。
1.4 行摒余解和列摒余解合称行列摒余解(Hidden Single in Line)。
1.5 得到行列摒余解的方法称为行列摒除法。
余数法
Peer等位群格位[1]

余数法:用格位去找唯一可填数字,称为余数法,格位唯一可填数字称为唯余解(Naked Single)。
余数法是删减等位群格位(Peer)已出现的数字的方法,每一格位的等位群格位有 20 个,如右图所示。
相对概率
相对概率不是真实的概率,而是用于同一格中的几个数字之间相互比较出现的可能。
相对概率 = 九宫格出现的概率 × 行出现的概率 × 列出现的概率
九宫格出现的概率:如果九宫格中有2个格可能出现1,目标格可能的数字为1、2、3,另一个格可能出现的数字为1、4,那么:目标格中的1在九宫格出现的概率 = 目标格中出现1的概率 ×(1 - 另一个格中出现1的概率),得1/3× (1-1/2) = 1/6。
注意:1-1/2表示另一个格不出现1的概率,1/3× (1-1/2) 的意思就是在另一个格不出现1的情况下,目标格出现1的概率。
如果九宫格中有三个格可能出现1,目标格可能的数字为1、5、6,另一个格可能出现的数字为1、7,还有一个格可能出现的数字为1、8、9,得1/3 ×(1-1/2) × (1-1/3) = 1/9。依此类推。
行出现的概率和列出现的概率与九宫格出现的概率的算法原理相同。最后,把三个概率相乘,得到相对概率,把目标格中3个数字的相对概率进行对比,相对概率越大,出现的可能性越大。
辅助解法
上述方法称为基础解法(BasicTechniques),其他所有的解法称为进阶解法(Advanced Techniques),是在补基本解法之不足,所以又称辅助解法。
进阶解法包括:区块摒除法(LockedCandidates)、数组法(Subset)、四角对角线(X-Wing)、唯一矩形(Unique Rectangle)、全双值坟墓(BivalueUniversal Grave)、单数链(X-Chain)、异数链(XY-Chain)及其他数链的高级技巧等等。已发展出来的方法有近百种之多。
其中前两种加上基础解法为一般数独书中介绍并使用的方法,同时也是大部分人可以理解并掌握的数独解题技法。
4.通过基础解法出数只需一种解法,摒除法或唯余法,超出此范围而需要施加进阶解法时,解题点需要进阶解法协助基础解法来满足隐性唯一或显性唯一才能出数,该解题点的解法需要多个步骤协力完成,因此称做组合解法。
5.解题必须以逻辑为依归,猜测的方法被称为“暴力型”解法(Brute Force),这不是提倡数独的本意。
依解题填制的过程可区分为直观法与候选数法。
1.直观法就是不做任何记号,直接从数独的盘势观察线索,推论答案的方法。
2.候选数法就是删减等位群格位已出现的数字,将剩余可填数字填入空格做为解题线索的参考,可填数字称为候选数(Candidates,或称备选数)。
直观法和候选数法只是填制时候是否有注记的区别,依照个人习惯而定,并非鉴定题目难度或技巧难度的标准,无论是难题或是简单题都可上述方法填制,一般程序解题以候选数法较多。
5难度划分
影响数独难度的因素很多,就题目本身而言,包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。对于玩家而言,了解的技巧数量、熟练程度、观察力自然也影响对一道题的难度判断。市面上数独刊物良莠不齐,在书籍、报纸、杂志中所列的难度或者大众解题时间纯属参考,常有难度错置的情况出现,所以不必特别在意。网络上有很多数独难度的分析软件,比较著名的是 Nicolas Juillerat 开发的 Sudoku Explainer 和 BernhardHobiger 开发的 Hodoku,它们都是免费的软件。因为每种软件的都有不同的解题策略,所以也只能作为难度的大致界定,无法真正的解析出难度的内涵。
如果一道题目的提示数少,那么题目就会相对难,提示数多则会简单,这是一般人判断难易的思维模式,但数独谜题提示数的多寡与难易并无绝对关系,多提示数比少提示数难的情况屡见不鲜,同时也存在增加提示数之后题目反而变难的情形,即使是相同提示数(甚或相同谜题图形)也可以变化出各式各样的难度。提示数少对于出题的困难度则有比较直接的关系,以20-35提示数而言,每少一个提示数,其出题难度会增加数倍,在制作谜题时,提示数在22以下就非常困难,所以常见的数独题其提示数在23~30之间,其原因在于制作比较不困难,可以设计出比较漂亮的图形(Pattern),另外这个提示数范围的谜题变化多端是一个重要因素。
6终盘数量
数独中的数字排列千变万化,那么究竟有多少种终盘的数字组合呢?
6,670,903,752,021,072,936,960(约为6.67×10的21次方)种组合,2005年由BertramFelgenhauer和Frazer Jarvis计算出该数字,并将计算方法发布在他们网站上,如果将等价终盘(如旋转、翻转、行行对换,数字对换等变形)不计算,则有5,472,730,538个组合。数独终盘的组合数量都如此惊人,那么数独题目数量就更加不计其数了,因为每个数独终盘又可以制作出无数道合格的数独题目。
7标准数独
目前(截止2011年)发现的最少提示数9×9标准数独为17个提示,截止编辑此词条时间(2011.11.2416:14),共发现了非等价17提示数谜题49151题,此数量仍在缓慢上升中,如果你先发现了17提示数的题目,可以上传至“17格数独验证”网站,当然你也可以在这里下载这49151题。
关于是否有16提示数的合格题目,网络上也争论很久,有发现16提示数双解的,但是仍未发现唯一解。国外有网友给出了关于为什么至少需要17提示的证明,受到了大家的质疑,比如9×9对角线数独(在标准数独规则基础上,两条大对角线的数字不重复)的最小提示数为12,按照他的理论则需要更多的提示数。
另外在2006年GaryMcGuire[2] 撰写了程式,试图通过暴力法来证明16提示数的数独是否存在,方法很简单,既然Bertram Felgenhauer和FrazerJarvis已经计算出不等价的终盘总数为5,472,730,538个,那么将每个终盘是16提示的情况都跑一遍,如果没有找到16提示的数独,那么就可以证明最少提示数为17个。但因为是暴力方法,对于一台单核的电脑来说需要跑30万年才能跑出结果。***的吴毅成教授和他的团队将Gary McGuire的程式加以改进,使得效率大幅提升,大约2417年即可完成演算。并放在BOINC(伯克利开放式网络计算平台)上让世界加入BOINC的电脑一同演算,令人欣喜的是,截至编辑本词条的时间(2012年4月18日)已经完成了51.73%[3] 。
Gary McGuire的团队在2009年设计了新的算法,利用Deadly Pattern的思路,花费710万小时CPU时间后,于2012年1月1日提出了9×9标准数独不存在16提示唯一解的证明,继而说明最少需要17个提示数。并将他们的论文以及源代码更新在2009年的页面上。
8变形数独
数独到如今发展,出现了越来越多的变形(Variants),按照规则划分则成百上千,各国的数独爱好者也不断制作出新的变形。下面列出最常见的三种变形:
对角线数独
1.对角线数独(DiagonalSudoku、Sudoku-X):
在标准数独规则基础上,两条大对角线的数字不重复。
对角线数独[1]

锯齿数独
2.锯齿数独(Jigsaw Sudoku):
相对标准数独而言,宫变成了不规则的。玩家需在对应的锯齿方框内填入不重复的九个数,并保证横纵也不重复。
Killer数独
在标准数独规则的基础上,每个虚线框左上角的数字表示虚线框内所有数字之和,每个虚线框内数字无重复。
杀手数独[1]

同时这3种基本变型也作为其他变形数独的雏形慢慢延伸开来,比如对角线数独引发了额外区域等,锯齿数独打破了宫是方方正正的定式,killer数独更是引发了更多计算类的数独。[4]
9出题方法
挖洞法
从有到无的出题方法。先生成一个终盘,然后挖去部分数字形成一道题目。
填数法
从有到无的出题方法。在一个空盘面上填上部分数字形成一道题目。值得一提的是,2007年日本NPGenerator软件的网站提出了一种边推理边出题的出题法,可以手工打造出漂亮图案的数独题目,有兴趣出题的可以试试。[5]
10纸笔谜题
谜题(Puzzle):排除文化差异对做题者的影响,只用数字和图形表示的逻辑推理游戏。数独是谜题中的一个成员,由于其规则简单、种类众多从而从众多谜题脱颖而出,成为大众熟知的数字谜题。
不过除了数独以外,还有不少谜题也非常出色,也有众多的拥护者,而且与数独有千丝万缕的关系。数独爱好者同样不能错过这些优秀的逻辑推理游戏。下面简单介绍几类谜题:
数和(Kakuro):与杀手数独很像的一类谜题,规则要求同行、同列(同一段)数字不能重复,且每段数字之和等于左边和上边的提示数字。
数图[6] (Nonograms/Griddlers):根据盘面周围的数字提示,把盘中涂成符合条件的图案,很像“十字绣”。
数回(SlitherLink):游戏由0,1,2,3四个数字组成。每一个数字,代表四周划线的数目,并在最后成为一个不间断、不分岔的回路。
数墙(Nurikabe):数墙的世界,是一个非黑即白的二元世界;在游戏中,你要决定的是,哪些格子需要涂黑,哪一些应该留白。
数连(NumberLink):与数独一样,数连是一个简单明快的游戏。你只需要把属于相同数字的同伴,以线连接起来。不过,这个游戏看起来非常简单,实际上是很有深度的。
算独(Kenken)游戏的目的是将数字1到N(N为网格的行列数)填满空格,使得每一行,每一列的数字不重复,并且每一个粗线框左上角代表了该粗线框内数字的运算法则以及计算结果。算数数独的粗线框内,相同数字可能使用不止一次。[7]
11数独计算器
数独计算器是一个特殊的数独解答工具,它试图提供人性化的数独解题方法,完全模拟人脑的思维过程解题,并且能一步一步的讲解每步的理由。
在你对数独难题一筹莫展的时候,该数独软件将为了提供帮助, 数独计算器是一个特殊的数独工具。我们希望数独计算器成为很好的使用逻辑方法解数独的工具,大家可以从数独助手的运行过程掌握更好的解数独题技巧,作为数独技巧教学的工具。
数独计算器可以进行一步一步计算、指定步数计算、一次性计算,对于每一步计算给出详细的说明。对于有多个解的数独题目,会给出提示,并可人工干预。对每一步计算生成步骤列表,可以回到任意步骤进行研究。[8]
12赛事
世界数独锦标赛:由世界智力谜题联合会组织的国际性最高水准数独赛事,该赛事每年举办一次,由不同的会员国轮流申请举办。首届于2006年在意大利的卢卡举办,[2] 第八届于2013年在北京举办[1] 。每年由世智联在各国的唯一授权组织选拔国家队参加。
北京国际数独大奖赛:由北京广播电视台主办的一项国际数独赛事,该赛事奖金较高,也吸引了国际上众多高手踊跃参与,给国内高手提供了一个可以与国外高手同场竞技的平台。首届于2011年举办,第二届于2012年5月举办,目前国内参赛的选手均为以往进入过数独国家队或在国内选拔赛中名列前茅者。
中国数独锦标赛:由国内的世智联授权组织每年举办一次,目的是选拔出当年的数独高手组队参加一年一度的世界数独锦标赛。该比赛不设置门槛,无论新人还是老手均可参加。具体的时间和地点请关注官方的数独选拔赛通知。
经过两天紧张激烈的比赛,各项桂冠终有归属。中国队获得团体赛冠军,捷克、日本分获亚军、季军;中国队的三位中学生选手金策、孙彻然、邱言哲获18岁及18岁以下年龄组前三名;中国队梁跃获得50岁及50岁以上年龄组亚军,丹麦队和意大利队选手分获冠军和季军;金策还夺得个人赛冠军,日本的森西亨泰、捷克的雅库布分获亚军、季军。
据了解,随着数独这项智力运动在中国的不断普及,越来越多的青少年成为数独爱好者。此次中国数独代表队不仅是比赛中最年轻的国家队之一,年仅15岁的邱言哲也成为年龄最小的A队队长。别看他还是一名在校初中生,却有着丰富的比赛经验,2011、2012年他曾是世界数独锦标赛中国队选手,2013获得中国数独锦标赛第四名。
获得18岁及18岁以下年龄组、个人赛及团体赛三项冠军的中学生金策,可谓本届数独世锦赛的一匹黑马。来自浙江的他已与数独结缘4年,当一些同龄人沉溺于网络游戏时,他却利用网络寻找与他志同道合的数独伙伴。瘦高的个子,不善言语的他,虽然在陌生人面前有些羞涩,但却通过一个个小小的九宫格展现自信与智慧。
本届数独世锦赛决赛以电视直播的方式,在北京电视台新闻频道同步播出,这在世界上尚属首次。在没有任何经验可循的情况下,为保证不影响赛事进行,同时又能实时展现选手比赛进程,组委会设计了多套直播方案,多次推敲并到场演练,以演播室讲解加决赛现场的方式,清晰简练地为电视观众讲解数独题目。

百度百科—数独.pdf

1.26 MB, 下载次数: 33

回复

使用道具 举报

2

主题

36

帖子

215

积分

小学二年级

Rank: 2Rank: 2

积分
215
发表于 2014-10-6 21:55:07 | 显示全部楼层
数独在上海的教育体系里,几年级开始比较好?谢谢
回复

使用道具 举报

264

主题

506

帖子

1万

积分

版主

Rank: 7Rank: 7Rank: 7

积分
15511

精华达人

QQ
 楼主| 发表于 2014-10-7 13:39:04 | 显示全部楼层
芬达 发表于 2014-10-6 21:55
数独在上海的教育体系里,几年级开始比较好?谢谢

从低年级到高年级都可以,不同的年级都有想对应的数独课程体系。
回复

使用道具 举报

2

主题

36

帖子

215

积分

小学二年级

Rank: 2Rank: 2

积分
215
发表于 2014-10-10 23:52:36 | 显示全部楼层
东方老师 发表于 2014-10-7 13:39
从低年级到高年级都可以,不同的年级都有想对应的数独课程体系。

谢谢
回复

使用道具 举报

0

主题

180

帖子

674

积分

小学四年级

Rank: 3

积分
674
发表于 2014-11-20 19:44:42 | 显示全部楼层
学习了。谢谢!
回复

使用道具 举报

0

主题

180

帖子

674

积分

小学四年级

Rank: 3

积分
674
发表于 2015-2-27 20:19:26 | 显示全部楼层
好贴,顶!
回复

使用道具 举报

50

主题

1955

帖子

3568

积分

高中二年级

Rank: 5Rank: 5Rank: 5

积分
3568

活跃会员灌水之王最佳新人

发表于 2015-3-6 18:09:17 | 显示全部楼层
学习学习
回复

使用道具 举报

0

主题

11

帖子

50

积分

幼儿园

Rank: 1

积分
50
发表于 2015-3-31 14:20:47 | 显示全部楼层
学习学习
回复

使用道具 举报

0

主题

22

帖子

148

积分

小学一年级

Rank: 2Rank: 2

积分
148
发表于 2015-4-15 12:03:25 | 显示全部楼层
老师,请问有没有关于两年级孩子的数独练习题可以参考?
回复

使用道具 举报

0

主题

22

帖子

148

积分

小学一年级

Rank: 2Rank: 2

积分
148
发表于 2015-4-15 12:07:57 | 显示全部楼层
老师,请问有没有数独题目的相关书籍?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 会员注册

本版积分规则

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc

关于我们 | 网站地图 | 我爱数学网 ( 沪ICP备16005585号-3  

GMT+8, 2019-11-14 16:41 征信网

快速回复 返回顶部 返回列表