忘忧草家园

 找回密码
 注册
查看: 57|回复: 5

数独

[复制链接]
发表于 2018-9-14 12:00 | 显示全部楼层 |阅读模式
本帖最后由 山色空蒙 于 2018-9-14 15:39 编辑

数独


数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。

数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格


 楼主| 发表于 2018-9-14 12:00 | 显示全部楼层
本帖最后由 山色空蒙 于 2018-9-14 15:42 编辑

历史发展
起源

既然“数独”有一个字是“数”,人们也往往会联想到数学,那就不妨从大家都知道的数学家欧拉说起,但凡想了解数独历史的玩家在网络、书籍中搜索时,共同会提到的就是欧拉的“拉丁方块(Latin square)”。

拉丁方块的规则:每一行(Row)、每一列(Column)均含1-N(N即盘面的规格),不重复。这与前面提到的标准数独非常相似,但少了一个宫的规则。


近代发展

数独起源于18世纪初瑞士数学家欧拉等人研究的拉丁方阵(Latin Square)。19世纪80年代,一位美国的退休建筑师格昂斯(Howard Garns)根据这种拉丁方阵发明了一种填数趣味游戏,这就是数独的雏形。20世纪70年代,人们在美国纽约的一本益智杂志《Math Puzzles and Logic Problems》上发现了这个游戏,当时被称为填数字(Number Place),这也是目前公认的数独最早的见报版本。1984年一位日本学者将其介绍到了日本,发表在Nikoli公司的一本游戏杂志上,当时起名为“数字は独身に限る”(すうじはどくしんにかぎる),就改名为“数独”(すうどく),其中“数”(すう)是数字的意思,“独”(どく)是唯一的意思。后来一位前任香港高等法院的新西兰籍法官高乐德(Wayne Gould)在1997年3月到日本东京旅游时,无意中发现了。他首先在英国的《泰晤士报》上发表,不久其他报纸也发表,很快便风靡全英国,之后他用了6年时间编写了电脑程序,并将它放在网站上(这个网站也就是著名的数独玩家论坛),后来因一些原因,网站被关闭,幸好数独大师Glenn Fowler恢复了数据,玩家论坛有了新处所。在90年代国内就有部分的益智类书籍开始刊登,南海出版社在2005年出版了《数独1-2》,随后日本著名数独制题人西尾彻也的《数独挑战》也由辽宁教育出版社出版。《北京晚报》、《扬子晚报》、《羊城晚报》、《新民晚报》、《成都商报》等等报纸媒体也先后刊登了数独游戏


2、组成元素
方格

水平方向有九横行,垂直方向有九纵列的矩形,画分八十一个小正方形,称为九宫格(Grid),如图一所示,是数独(Sudoku)的作用范围。

数独元素 - 九宫格




水平方向的每一横行有九格,每一横行称为行(Row),如图二所示。

数独元素 - 单元


垂直方向的每一纵列有九格,每一纵列称为列(Column),如图三所示。

数独元素 - 列


三行与三列相交之处有九格,每一单元称为小九宫(Box、Block),简称宫,如图四所示(在杀手数独中,宫往往用单词Nonet表示)。

数独元素 - 宫


单元、区域

上述行、列、宫、单元格统称为单元(Unit);而行、列、宫统称为区域(Region)。


区块

由三个连续宫组成大行列(Chute),分大行(Floor)及大列(Tower)。

第一大行:由第一宫、第二宫、第三宫组成。

第二大行:由第四宫第五宫、第六宫组成。

第三大行:由第七宫、第八宫、第九宫组成。

第一大列:由第一宫、第四宫、第七宫组成。

第二大列:由第二宫、第五宫、第八宫组成。

第三大列:由第三宫、第六宫、第九宫组成。




 楼主| 发表于 2018-9-14 15:35 | 显示全部楼层
本帖最后由 山色空蒙 于 2018-9-14 15:58 编辑

格位编号

格位按所处的行列单元赋予坐标值,如图五所示。

数独元素 - 格位

坐标有多种标示法,有横行 A~I,纵列 1~9(如中国),也有横行 1~9,纵列 A~I(如日本),这两种标示容易混淆,故最被广泛使用的是横行R1~R9,纵列C1~C9的标示法。


提示数

九宫格的格位填上一些数字,做为填数判断的线索(Hint),称为提示数(Clue),如图六所示。

数独元素 - 提示数


3、解题手法


数独依解题填制的过程可区分为直观法与候选数法。

直观法就是不做任何记号,直接从数独的盘势观察线索,推论答案的方法。

候选数法就是删减等位群格位已出现的数字,将剩余可填数字填入空格做为解题线索的参考,可填数字称为候选数(Candidates,或称备选数)。

直观法和候选数法只是填制时候是否有注记的区别,依照个人习惯而定,并非鉴定题目难度或技巧难度的标准,无论是难题或是简单题都可上述方法填制,一般程序解题以候选数法较多。


4、基础解法
排除法(摒除法)

摒除法:用数字去找单元内唯一可填空格,称为摒除法,数字可填唯一空格称为排除法 (Hidden Single)。

根据不同的作用范围,摒余解可分为下述三种:

数字可填唯一空格在「宫」单元称为宫排除(Hidden Single in Box),也称宫摒除法。

数字可填唯一空格在「行」单元称为行排除法(Hidden Single in Row),也称行摒除法。

数字可填唯一空格在「列」单元称为列排除法(Hidden Single in Column),也称列摒除法。


唯一余数法

Peer等位群格位唯一余数法:用格位去找唯一可填数字,称为余数法,格位唯一可填数字称为唯余解(Naked Single)。

余数法是删减等位群格位(Peer)已出现的数字的方法,每一格位的等位群格位有 20 个,如图七所示。


5、进阶解法


数独上述方法称为基础解法(Basic Techniques),其他所有的解法称为进阶解法(Advanced Techniques),是在补基本解法之不足,所以又称辅助解法。

进阶解法包括:区块摒除法(Locked Candidates)、数组(Subset/Tuple)、二链列(X-Wing)、唯一矩形(Unique Rectangle)、全双值格致死解法(Bivalue Universal Grave)、同数链(X-Chain)、异数链(Multidigit Chain)及其他数链的高级技巧等等。已发展出来的方法有近百种之多。

其中前三种加上基础解法为一般数独书中介绍并使用的方法,同时也是大部分人可以理解并掌握的数独解题技法。

通过基础解法出数只需一种解法,摒除法或唯余法,超出此范围而需要施加进阶解法时,解题点需要进阶解法协助基础解法来满足隐性唯一或显性唯一才能出数,该解题点的解法需要多个步骤协力完成,因此称做组合解法。

解题必须以逻辑为依归,提倡数独的本意。


区块摒除法

区块摒除法包括宫区块摒除法(Pointing)与行列区块摒除法(Claiming)。

在基础题里,利用区块摒除可以替代一些基础解法的观察,或辅助基础解法寻找焦点。

在非基础题里,区块可以隐藏任何其他结构,简单的可以把基础解法隐藏起来,难的可以隐藏数对等等其他进阶技巧。

例如:

区块摒除法

首先数字6对第五宫摒除,得到第五宫的6在R4C5或者R6C5。

不论是在R4C5或者R6C5,C5的其他格都不能再有数字6。(R4C5与R6C5就是数字6的区块,这也是区块摒除作用的观点)

数字6对第二宫摒除,得解R1C4=6。




 楼主| 发表于 2018-9-14 15:36 | 显示全部楼层
本帖最后由 山色空蒙 于 2018-9-14 15:50 编辑

数对法

当一个单元(行、列、宫)的某两个数字仅可能在某两格时,我们称这两个格为这两个数的数对(Pairs)。

数对出现在宫称为宫数对;数对出现在行列成为行列数对。

用候选数法的观点去看,数对有两种,一种是在同单元内其中两格有相同的双候选数,一看就明白,因此称为显性数对(Naked Pair),另一种是,同单元内有两个候选数占用了相同的两格,该两格因为还有其它候选数很难辨认,因此称为隐性数对(Hidden Pair)。

合并图册(2)


例子:

左图:数字2与7同时对第一宫摒除,得到这两个数字均只可能在r2c2与r3c2这两个位置,我们称r2c2与r3c2是27数对。

右图:数字8对第一宫摒除,得到摒余解r1c3=8。


6、难度划分

数独影响数独难度的因素很多,就题目本身而言,包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。对于玩家而言,了解的技巧数量、熟练程度、观察力自然也影响对一道题的难度判断。市面上数独刊物良莠不齐,在书籍、报纸、杂志中所列的难度或者大众解题时间纯属参考,常有难度错置的情况出现,所以不必特别在意。网络上有很多数独难度的分析软件,比较著名的是 Nicolas Juillerat 开发的Sudoku Explainer和 Bernhard Hobiger 开发的Hodoku,它们都是免费的软件。因为每种软件的都有不同的解题策略,所以也只能作为难度的大致界定,无法真正的解析出难度的内涵。

如果一道题目的提示数少,那么题目就会相对难,提示数多则会简单,这是一般人判断难易的思维模式,但数独谜题提示数的多寡与难易并无绝对关系,多提示数比少提示数难的情况屡见不鲜,同时也存在增加提示数之后题目反而变难的情形,即使是相同提示数(甚或相同谜题图形)也可以变化出各式各样的难度。提示数少对于出题的困难度则有比较直接的关系,以20-35提示数而言,每少一个提示数,其出题难度会增加数倍,在制作谜题时,提示数在22以下就非常困难,所以常见的数独题其提示数在23~30之间,其原因在于制作比较不困难,可以设计出比较漂亮的图形(Pattern),另外这个提示数范围的谜题变化多端是一个重要因素。


7、终盘数量编辑

数独数独中的数字排列千变万化,那么究竟有多少种终盘的数字组合呢?

6,670,903,752,021,072,936,960(约为6.67×10的21次方)种组合,2005年由Bertram Felgenhauer和Frazer Jarvis计算出该数字,并将计算方法发布在他们网站上,如果将等价终盘(如旋转、翻转、行行对换,数字对换等变形)不计算,则有5,472,730,538个组合。数独终盘的组合数量都如此惊人,那么数独题目数量就更加不计其数了,因为每个数独终盘又可以制作出无数道合格的数独题目。


8、标准数独编辑

数独目前(截止2011年)发现的最少提示数9×9标准数独为17个提示,截止2011年11月24日16:14,共发现了非等价17提示数谜题49151题,此数量仍在缓慢上升中,如果你先发现了17提示数的题目,可以上传至“17格数独验证”网站,当然你也可以在这里下载这49151题。

关于是否有16提示数的合格题目,网络上也争论很久,有发现16提示数双解的,但是仍未发现唯一解。国外有网友给出了关于为什么至少需要17提示的证明,受到了大家的质疑,比如9×9对角线数独(在标准数独规则基础上,两条大对角线的数字不重复)的最小提示数为12,按照他的理论则需要更多的提示数。

另外在2006年Gary McGuire撰写了程式,试图通过暴力法来证明16提示数的数独是否存在,方法很简单,既然Bertram Felgenhauer和Frazer Jarvis已经计算出不等价的终盘总数为5,472,730,538个,那么将每个终盘是16提示的情况都跑一遍,如果没有找到16提示的数独,那么就可以证明最少提示数为17个。但因为是暴力方法,对于一台单核的电脑来说需要跑30万年才能跑出结果。台湾的吴毅成教授和他的团队将Gary McGuire的程式加以改进,使得效率大幅提升,大约2417年即可完成演算。并放在BOINC(伯克利开放式网络计算平台)上让世界加入BOINC的电脑一同演算,令人欣喜的是,截至编辑2012年4月18日已经完成了51.73%。

Gary McGuire的团队在2009年设计了新的算法,利用致命结构的思路,花费710万小时CPU时间后,于2012年1月1日提出了9×9标准数独不存在16提示唯一解的证明,继而说明最少需要17个提示数。并将他们的论文以及源代码更新在2009年的页面上。


9、变形数独

数独数独到如今发展,出现了越来越多的变形(Variants),按照规则划分则成百上千,各国的数独爱好者也不断制作出新的变形。

一般意义上,按照最为基础的数独规则,一般称为标准数独(Standard Sudoku)。而产生的解题思路和技巧,也称为标准数独技巧。

下面列出最常见的几种变形:


对角线数独

对角线数独(Diagonal Sudoku、Sudoku-X):

在标准数独规则基础上,两条大对角线的数字不重复。

对角线数独




 楼主| 发表于 2018-9-14 15:37 | 显示全部楼层
本帖最后由 山色空蒙 于 2018-9-14 15:54 编辑

迷你数独

迷你数独(Mini Sudoku):

每个谜题都由一个在不同位置给与提示数字的4x4或6x6网格组成。游戏的目的是将空方格填上数字1到4(对于4x4大小的谜题)或者1到6(对于6x6的谜题),使得每一行,每一列以及每一个宫都没有重复的数字出现。


锯齿数独

锯齿数独(Jigsaw Sudoku):

相对标准数独而言,宫变成了不规则的。玩家需在对应的锯齿方框内填入不重复的九个数或N个数,并保证横纵也不重复。


连体数独

连体数独(Multi Sudoku):

每个谜题都由俩个或者更多的数独网格重叠组成,该网格可能是标准数独谜题也可能是混合类型的数独谜题,这些网格都有一个或多个宫重叠。游戏的目的是通过其规则将每个网格均解出。温馨提示,重叠的区域必须同时满足其所在网格的规则。


Killer数独

杀手数独(Killer Sudoku、Sum Sudoku):

在标准数独规则的基础上,每个虚线框左上角的数字表示虚线框内所有数字之和,每个虚线框内数字无重复。

杀手数独

对角线数独引发了额外区域等,锯齿数独打破了宫是方方正正的定式,杀手数独更是引发了更多计算类的数独。


10、出题方法编辑
挖洞法

从有到无的出题方法。先生成一个终盘,然后挖去部分数字形成一道题目。


填数法

从有到无的出题方法。在一个空盘面上填上部分数字形成一道题目。值得一提的是,2007年日本NPGenerator软件的网站提出了一种边推理边出题的出题法,可以手工打造出漂亮图案的数独题目,有兴趣出题的可以试试。


11、类似谜题

数独谜题(Puzzle):排除文化差异对做题者的影响,只用数字和图形表示的逻辑推理游戏。数独是谜题中的一个成员,由于其规则简单、种类众多从而从众多谜题脱颖而出,成为大众熟知的数字谜题

不过除了数独以外,还有不少谜题也非常出色,也有众多的拥护者,而且与数独有千丝万缕的关系。数独爱好者同样不能错过这些优秀的逻辑推理游戏。下面简单介绍几类谜题:

数和(Kakuro):与杀手数独很像的一类谜题,规则要求同行、同列(同一段)数字不能重复,且每段数字之和等于左边和上边的提示数字。

数图(Nonograms/Griddlers):根据盘面周围的数字提示,把盘中涂成符合条件的图案,很像“十字绣”。

数回(Slither Link):游戏由0,1,2,3四个数字组成。每一个数字,代表四周划线的数目,并在最后成为一个不间断、不分岔的回路。

数墙(Nurikabe):数墙的世界,是一个非黑即白的二元世界;在游戏中,你要决定的是,哪些格子需要涂黑,哪一些应该留白。

数连(Number Link):与数独一样,数连是一个简单明快的游戏。你只需要把属于相同数字的同伴,以线连接起来。不过,这个游戏看起来非常简单,实际上是很有深度的。

算独(Kenken)游戏的目的是将数字1到N(N为网格的行列数)填满空格,使得每一行,每一列的数字不重复,并且每一个粗线框左上角代表了该粗线框内数字的运算法则以及计算结果。算数数独的粗线框内,相同数字可能使用不止一次。


12、数独软件

数独数独软件现在比较多,影响比较大,功能比较全的有以下软件:

hodoku,Sudoku Explainer,SudoCue,Simple Sudoku,Color Sudoku,无限数独等。

一个好的数独软件应当可以进行一步一步计算、指定步数计算、一次性计算,对于每一步计算给出详细的说明。对于有多个解的数独题目,会给出提示,并可人工干预。对每一步计算生成步骤列表,可以回到任意步骤进行研究。

【hodoku】,用于分析标准数独难度及产生标准数独题目。功能相当强大。免费下载,提供了超详细的解题过程分析。

HoDoKu is a sudoku helper written in Java and available in English and German. Generate sudokus in five different and fully configurable difficulty levels. Solve them yourself (with help from HoDoKu's hint system) or let HoDoKu do it for you.

HoDoKu supports many more human style solving techniques than most other programs available (singles, subsets, LCs, fish, wings, uniqueness, coloring, chains, ALS; for details see "solving techniques"). All steps can be highlighted on the grid which makes HoDoKu a great tool for learning as well.

【Sudoku Explainer】,用于分析标准数独难度及产生标准数独题目。本软件的难度分析评分极具权威性。

【SudoCue】,功能强大,免费。还可以生成多种变形数独。

SudoCue is a program that generates sudoku puzzles in various difficulties and helps you solve them by providing a suite of tools to inspect the grid and give you useful hints. The program can solve any valid sudoku puzzle, or report the invalidity when no unique solution can be found. This makes the program a generator, helper and solver. That’s 3 programs for the price of none. Some of the functions are not found anywhere else, like the optimizer and the scrambler. The program accepts input is many formats, from file and from the clipboard. Save and copy functions are also included. It is an excellent tool to communicate sudoku problems with other players on the popular sudoku forums.

【Simple Sudoku】,功能强大,免费。

A Sudoku puzzle maker and solverfor Win9x, Win2000 & WinXP

Simple Sudoku makes high quality puzzles that are symmetrical, have a single solution, and do not require trial & error to solve. The user can also choose between five levels of complexity - from Easy to Extreme. Each puzzle is generated randomly so there is an almost limitless selection.

Not only does Simple Sudoku make challenging puzzles, it also provides tools to help solve them - removing the drudgery but not the fun. Keeping track of possible values for blank cells (candidates), providing filters and color markers are just some of the tools available to make solving even those really tricky puzzles possible. Also, if you ever get really stuck, Simple Sudoku can get you started again with a discreet hint (without giving everything away).

【Color Sudoku】,用于生成标准数独、对角线数独、killer数独、GT数独(跨宫标)、连续数独、连体数独及上述任意几种规则的组合题型,可选择提示数是否180度对称,可批量打印上述题目。功能强大,免费。

无限数独,是国人开发,免费,简单易用。可惜作者源代码丢失后不在继续开发了。




 楼主| 发表于 2018-9-14 15:38 | 显示全部楼层
本帖最后由 山色空蒙 于 2018-9-14 15:56 编辑

数独赛事

数独世界数独锦标赛:由世界智力谜题联合会组织的国际性最高水准数独赛事,该赛事每年举办一次,由不同的会员国轮流申请举办。首届于2006年在意大利的卢卡举办,第八届于2013年在北京举办。每年由世智联在各国的唯一授权组织选拔国家队参加。

北京国际数独大奖赛:由北京广播电视台主办的一项国际数独赛事,该赛事奖金较高,也吸引了国际上众多高手踊跃参与,给国内高手提供了一个可以与国外高手同场竞技的平台。首届于2011年举办,第二届于2012年5月举办,目前国内参赛的选手均为以往进入过数独国家队或在国内选拔赛中名列前茅者。

中国数独锦标赛:由国内的世智联授权组织每年举办一次,目的是选拔出当年的数独高手组队参加一年一度的世界数独锦标赛。该比赛不设置门槛,无论新人还是老手均可参加。具体的时间和地点请关注官方的数独选拔赛通知。

经过两天紧张激烈的比赛,各项桂冠终有归属。中国队获得团体赛冠军,捷克、日本分获亚军、季军;中国队的三位中学生选手金策孙彻然、邱言哲获18岁及18岁以下年龄组前三名;中国队梁跃获得50岁及50岁以上年龄组亚军,丹麦队和意大利队选手分获冠军和季军;金策还夺得个人赛冠军,日本的森西亨泰、捷克的雅库布分获亚军、季军。

据了解,随着数独这项智力运动在中国的不断普及,越来越多的青少年成为数独爱好者。此次中国数独代表队不仅是比赛中最年轻的国家队之一,年仅15岁的邱言哲也成为年龄最小的A队队长。别看他还是一名在校初中生,却有着丰富的比赛经验,2011、2012年他曾是世界数独锦标赛中国队选手,2013获得中国数独锦标赛第四名。

获得18岁及18岁以下年龄组、个人赛及团体赛三项冠军的中学生金策,可谓本届数独世锦赛的一匹黑马。来自浙江的他已与数独结缘4年,当一些同龄人沉溺于网络游戏时,他却利用网络寻找与他志同道合的数独伙伴。瘦高的个子,不善言语的他,虽然在陌生人面前有些羞涩,但却通过一个个小小的九宫格展现自信与智慧。

本届数独世锦赛决赛以电视直播的方式,在北京电视台新闻频道同步播出,这在世界上尚属首次。在没有任何经验可循的情况下,为保证不影响赛事进行,同时又能实时展现选手比赛进程,组委会设计了多套直播方案,多次推敲并到场演练,以演播室讲解加决赛现场的方式,清晰简练地为电视观众讲解数独题目。


14、词条图册




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

本版积分规则

辽公网安备 21010502000089号|手机版|Archiver|忘忧草家园 ( ICP14007463

GMT+8, 2018-11-17 02:58 , Processed in 0.160147 second(s), 17 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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