数独作为一款益智游戏,深受部分同(da)学(shen)的喜爱。今天小编就带你们走进数独的世界。来一起感受一下数独的魅力!
基本信息
图中每个小格称为方格。
竖着的9个称为列。
横着的9个称为行。
每个加粗线包围的3x3大方格称为宫。
所谓数独,其实规则很简单,在这些方格里分别填上1-9,使得每一行每一列每一宫中间都要有1-9,不重复不遗漏。
但是,你以为这就是数独??
那你可就太Naive了。
上面的,只是最基本的数独。
数独包括,但远远不止于这些。
下面本小编将给你展示
各种你想都没想到过的花式数独
比如增加了额(jie)外(ti)区(nan)域(du)的……
对角线数独
这算是最简单的一种变体了,仅需在标准数独规则的基础上,再保证对角线上元素不重复即可。
比如改变了棋盘大小的……
迷你数独
棋盘缩小为4x4或6x6,对应基本规则没有变化。还是每一行、列、宫均出现1-4(1-6),不重复不遗漏。
比如改变了宫是方方正正的定式的……
锯齿数独
锯齿数独里,宫的形状变得不规则。你需在每个“宫”中填入1-9,并保证行、列、“宫”均不重复。
前方高能警告!!!
高能系列之:谁说数独只能单身Σ(°△°|||)︴
连体数独(MultiSudoku)
连体数独由多个数独重叠组成,每个小的数独单元可能是标准数独也可能是其他的花式数独,且它们都有一个或多个宫重叠。你需要根据提示将每个数独均解出。而且,重叠的区域必须同时满足其所在的所有数独单元的要求。
高能系列之:解数独还要做计算题д)b
杀手数独(KillerSudoku)
杀手数独看似规则简单,只需要你在标准数独规则的基础上,让部分特定的数字满足某种运算的规则即可(例图是所有虚线内的数字满足加法等于左上角标注的数字)。但问题在,他不会给提示数!
例图里的还算是简单的,毕竟只有加法。小编曾经见到过加减乘除都用上的杀手数独!当时小编的内心是崩溃的"(oДo*)
高能系列之:………………
算了不吓唬大家了,怕你们被吓倒系列
其实,花式数独肯定不止这些。
毕竟经过计算,数独的终盘可能多达
6,670,903,752,021,072,936,960种!!
即便去掉通过初等变换可以实现等价的情况
(对换行列,翻转旋转,数字对调等)
终盘数量也有5,472,730,538种!
这么多的可能情况,还有什么花式数独
是不可能的呢!!
前世今生
诞生与发展
数独起源于18世纪初欧拉等人研究的拉丁方阵。不同于现有的数独,拉丁方阵并不限定是9*9的方阵,且对宫内的数字并没有做要求,仅要求每一行每一列内出现1-N(N代表行数)所有数并且不重复即可。
19世纪80年代,一位美国的退休建筑师格昂斯(HowardGarns)根据这种拉丁方阵发明了一种填数趣味游戏,这就是数独的雏形。20世纪70年代,人们在美国纽约的一本益智杂志《MathPuzzlesandLogicProblems》上发现了这个游戏,当时被称为NumberPlace(填数字),这也是目前公认的数独最早的见报版本。
1984年,这个游戏经过学者介绍,进入日本。当时发表在游戏杂志上,并最早确立了游戏名叫“数独”(すうどく,罗马音SUDOKU)数代表数字,独代表唯一。这也是数独的英文名Sudoku的由来了。
1997年,新西兰人高乐德(WayneGould)把这个游戏带到了英国,在泰晤士报上发表之后,很快风靡全英国。他后来花了六年写了一个程序并放到网站上,这也是最早的数独玩家论坛,可惜这个网站现在不在了,但是从此,数独就开始走向全世界。
研究与讨论
【有关最小提示数的讨论】
数独作为从数学中脱胎而来的游戏,自然少不了对它的数学研究。最为经典的讨论之一就是最小提示数。也就是在标准数独上,至少先填入多少个数字作为提示数,才可以使得解唯一。很早就有人找到17提示数的谜题使得解唯一存在。但是人们却找不到满足要求的16提示数数独,它们最少也有两解。
2006年,GaryMcGuire撰写了程序,试图证明16提示数是否真的存在。这位老哥的想法,就是遍历上述提到的近55亿的终盘可能。作为最暴力但可能最有效的手法,他的程序编写下来,需要一台单核计算机跑30万年。后来,在台湾吴毅成教授进行程序优化之后,加上现在的计算能力,这个想法在2013年9月5日最终演算完成。也就是说,通过暴力法成功证明了最小提示数就是17。当然美中不足的是,目前似乎还没有对最大提示数的研究。
【提示数和数独难度真的有联系吗?】
既然提到了17提示数独,那就多插几句话。目前发现的17提示数的数独是49157题。他们的难度分布是这样的:
(上述数据统计至2013.12.1)根据贴吧某大神解释,真正骨灰级难度题目不超过4%,这意味着难度和提示数其实并没有直接联系。提示数越少并不代表数独难度越高。
不过,这个问题没有严格的数学证明,甚至连数独难度的准确定义都没有。所以上面所说的这些,也都只是直观的感受啦。
解题手法
数独解题手法最常用最基本的是排除法。
下面介绍小编常用的几个操作,
其实都离不开排除法思维的影子。
唯一余数法
如图所示,和点位A处于同一行or列or宫的格子叫做A的等位群格位。每个点位的等位群格位一共有20个。
其实根据规则不难发现,如果一个数字出现在了A的等位群格位上,就一定不可能出现在A上,所以就可以通过数等位群格位上的数字,对A进行排除。如果排除得到A只有唯一一个可能数字,那你就放心填上它好了。
纵横排除法
原数独题
方法示意
从数字本身的角度考虑,填进数独的9个一样的数字必须不在同一行或同一列。借此也可以做纵横排除法。
上面是“纵横排除法”方法示意。观察到9数字足够多,就针对9实行纵横排除法。如右图所示,划掉所有数字是9的点位的等位群格位(蓝)。发现就只剩下3个点位,一个宫里1个,所以这三个点位一定就是9了。
行列排除法
当你发现一行or列or宫里已出现较多的数字(一般是5个以上)的时候,可以数这一行还剩下什么数字没填进去。再看有没有其他的提示能够帮助你排除这些空位的一些可能。其本质上和唯一余数法相近,但可以额外解决一些唯一余数法所不能解决的情况。
上面是“行列排除法”方法示意,对第三行检测,发现第三行只有5.6.9三个数字没填。再继续审视其他地方。由于圈出的数字的存在,第一个空位不能填6,第二个空位不能填5.9,第三个空位不能填6.9。这样我们也锁定了三个空位分别填9.6.5。
当然,还有最暴力但风险最高的方法!
那就是传说中的:
假设法!
假设
当你不能确定到底该填哪个的时候
可以列出一切合理的可能,然后
随便选择一个看着顺眼的数填进去。
我管你是不是真的对,反正我就当你对。
因为你不确定它是否真的正确,
所以它叫假(du)设(bo)法.
而且,因为它真的不一定正确,
所以你可能会发现
等位群格位中出现了1-9所有数
也可能会发现
纵横排除法消去了一个宫内的所有可能
行列排除法中缺失的数字
填不进任何一个空位
这个时候不要慌
你只需要倒退回前一个假设的位置
更换一个假设
然后继续做数独……
Ofcourse,这意味着如果需要的假设越多
这个数独难度就越高
因为你真的不知道是哪一个假设出了错
所以,假设法虽然好,但请慎重使用!
assumption
小试牛刀
前面说了这么多,就先拿一个40提示数的简单数独练练手吧,小编的水平不算很高,但对付它只用了不到4分钟。相信你可以的!后台回复“数独1”即可查看本题答案!
这个34提示数独小编觉得虽然有点难度,但是不需要用到假设。本题小编花了10分钟解决,供大家参考。相信不少大佬都比小编厉害!后台回复“数独2”即可查看本题答案!
这个29提示数独就是需要用到假设的了。因此也直接吓退了一个帮我测试难度的同学。但相信我,假设是一个痛并快乐着的过程。这个小编我花了20分钟解决,大家有兴趣可以来挑战一下自我哟~后台回复“数独3”即可查看本题答案!