注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

我的博客

只要心情是晴朗的,人生就没有雨天~~

 
 
 

日志

 
 

【转载】数独(转自豆扣网)  

2014-11-24 23:18:22|  分类: 快乐练习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自我的“江山”《数独(转自豆扣网)》
 

数独的起源

数独(日语:数独、 s ū doku )是一种源自 18 世纪末的瑞士,后在美国发展、并在日本发扬光大的数学智力拼图游戏。拼图是九宫格(即 3 格宽× 3 格高)的正方形状,每一格又细分为一个九宫格。在每一个小九宫格中,分别填上 1 至 9 的数字,让整个大九宫格每一列、每一行的数字都不重复。

数独的玩法逻辑简单,数字排列方式千变万化。不少教育者认为数独是锻炼脑筋的好方法。

如今数独的雏型首先于 1970 年代由美国的一家数学逻辑游戏杂志发表,当时名为 Number Place 。现今流行的数独于 1984 年由日本游戏杂志Nikoli 《パズル通信ニコリ》发表并得了现时的名称。数独本是「独立的数字」的省略,因为每一个方格都填上一个个位数。                                                                

 1

3

 4

 5

 6

 7

 8

 9

 1

 2

 3

 7

 8

 9

 1

 2

 3

 4

 5

 6

 2

 3

 1

 5

 6

 4

 8

 9

 7

 5

 6

 4

 8

 9

 7

 2

 3

 1

 8

 9

 7

 2

 3

 1

 5

 6

 4

 3

 1

 2

 6

 4

 5

 9

 7

 8

 6

 4

 5

 9

 7

 8

 3

 1

 2

 9

 7

 8

 3

 1

 2

 6

 4

 5

中国玩家可以访问数独游戏网:http://www.sudokus.cn

  数独联盟官网(中国)http://www.sudokuchina.com/                                                 

数独联盟,2007年2月正式加入世界谜题联合会(World Puzzle Federation),是中国独家代表世界谜题联合会在中国举办各种数独活动和赛事,独家选拔中国数独选手参加世界数独锦标赛,世界谜题联合会中国唯一会员机构。 我们致力于为中外数独游戏爱好者提供国际最前沿的数独游戏

世界谜题联合会http://www.worldpuzzle.org/

《纽约时报》数独(英文):http://www.nytimes.com/ref/crosswords/sudoku/easy.html?scp=1-spot&sq=sudoku&st=cse

免费数独在线(英文):http://www.free-soduko.com/

数独的历史

  数独前身为“九宫格”,最早起源于中国。数千年前,我们的祖先就发明了洛书,其特点较之现在的数独更为复杂,要求纵向、横向、斜向上的三个数字之和等于15,而非简单的九个数字不能重复。儒家典籍《易经》中的“九宫图”也源于此,故称“洛书九宫图”。而“九宫”之名也因《易经》在中华文化发展史上的重要地位而保存、沿用至今。

数独

■你知道是最先发明数独的吗?
       1783年,瑞士数学家莱昂哈德·欧拉发明了一种当时称作“拉丁方块”的游戏,这个游戏是一个n×n的数字方阵,每一行和每一列都是由不重复的n个数字或者字母组成的。
■你知道是哪一本杂志最先推广数独的吗?
       19世纪70年代,美国的一家数学逻辑游戏杂志《戴尔铅笔字谜和词语游戏》(Dell Puzzle Mαgαzines)开始刊登现在称为“数独”的这种游戏,当时人们称之为“数字拼图”,在这个时候,9×9的81格数字游戏才开始成型。
■你知道“数独”这个游戏名称是怎么来的吗?
       1984年4月,在日本游戏杂志《字谜通讯Nikoil》上出现了“数独”游戏,提出了“独立的数字”的概念,意思就是“这个数字只能出现一次”或者“这个数字必须是惟一的”,并将这个游戏命名为“数独”(SO DOKU),从此,这个游戏开始风靡全球。

解法举例

先注意其中一个方格,限定该方格内可以填写的数字。
注意其中一列(或者其中一个小九宫格),寻找填写某数字的方格。
学过“资料结构”的人,可以尝试用Backtrack试试。
数独的通解方法及步骤:
根据以下方法可以确保最终得到数独的解,而且通过手工运算的时间基本可以控制在1.5个小时,不论难易程度,所以此方法可以作为取得数独答案的一般解法。
1、根据横列、竖列和方格的限制条件排除各个点不可能的数字,并从1-9将各个可能的数字用小字体逐个写进每个空白的格子。(该步骤大约需要15-20分钟,这是求解的初始,务必确保没有遗漏)。
2、审视第一步骤的结果,如果发现某个空格只有一个数字,即确定该空格为这个数字。并根据该数字审视其相关的横列、竖列和方格,并划除相同的数字。(该情况出现的可能往往不多,除了较简单的数独题,但这是一个必要的过程,而且在随后的过程中要反复使用此方法。)
3、审视各个横列、竖列和方格中罗列出的可能的数字结果,若发现某一个数字在各个横列、竖列或方格中出现的次数仅一次,则可以确定该空格的解为此数字。并根据第二条的方法排除与此空格相关列或方格中相同的数字。
4、审视各个横列、竖列和方格中罗列的各个可能的结果,找出相对称的两个数组合的空格(或3个、4个组合),并确定这两个空格(或3个、4个)的数字只可能为这两个数字,即两个数字在这两个空格的位置可以交换,但不可能到该行、该列或该方格的其他位置。根据此结果可以排除相关列或方格罗列出相关数字的可能,并缩小范围。(该步骤处理的难度相对复杂,需要在积累一定经验的基础上进行,也是最终求解的关键)
5、反复使用2、3、4提到的步骤,逐步得到一个一个空格的解,并将先前罗列的各种可能的结果一个一个排除,使可能的范围越来越小,直至得到最后结果。

另外一种方法解初级的题目比较简单,就是:

数独
1、把每一个横行里缺少的数字写到这一行的最右边。
2、把每一个竖列里缺少的数字写到这一列的最下边。
3、在刚才写的备选数字中,肯定有一个是行和列都缺的,这个数就可以填到里面去了。
4、如此反复第3步即可。

在线玩数独游戏地址:http://www.yx007.com/sdir/slist793c24.htm

数独游戏在全球如此风靡,以致很多数学爱好者想要对数独游戏的难易及解法给出定量的刻画。2008年美国数学建模大赛中有一道题目就是关于数独问题难度刻画的。


 

数独终盘的排列组合

       数独中的数字排列千变万化,那么究竟有多少种终盘的数字组合呢?
  6,670,903,752,021,072,936,960(约有6.67×10的21次方)种组合,2005年由Bertram Felgenhauer和Frazer Jarvis计算出该数字,如果将重复(如数字交换、对称等)不计算,那么有5,472,730,538个组合。数独终盘的组合数量都如此惊人,那么数独题目数量就更加不计其数了,因为每个数独终盘都可以用挖数的方法出很多个不同的数独题目。

数独的基本元素

数独基本元素示意图数独(转自豆扣网) - 我的“江山” - 徐良雷

      单元格:数独中最小的单元,标准数独中共有81个;
      行:横向9个单元格的集合;
  列:纵向9个单元格的集合;
  宫:粗黑线划分的区域,标准数独中为3×3的9个单元格的集合;
  已知数:数独初始盘面给出的数字;
  候选数:每个空单元格中可以填入的数字。 
  

 

 

数独的基本规则

  标准数独的规则为:数独每行、每列及每宫填入数字1-9且不能重复。
基本解法举例
  数独解法全是由规则衍生出来的,基本解法分为两类思路,一类为排除法,一类为唯一法。更复杂的解法,最终也会归结到这两大类中。 下边以图示简单介绍几种解法,只要你花几分钟看一遍,马上就可以开始做数独了。

基础摒除法

       基础摒除法就是利用1 ~ 9 的数字在每一行、每一列、每一宫都只能出现一次的规则进行解题的方法。基础摒除法可以分为行摒除、列摒除、九宫格摒除。
  实际寻找解的过程为:
  寻找九宫格摒除解:找到了某数在某一个九宫格可填入的位置只余一个的情形;意即找到了 该数在该九宫格中的填入位置。
  寻找列摒除解:找到了某数在某列可填入的位置只余一个的情形;意即找到了该数在该列中的填入位置。
  寻找行摒除解:找到了某数在某行可填入的位置只余一个的情形;意即找到了该数在该行中的填入位置。
  基础摒除法的提升方法是区块摒除法,是直观法中使用频率最高的方法之一.

唯一解法

       当某行已填数字的宫格达到8个,那么该行剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为行唯一解.
  当某列已填数字的宫格达到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种分类并非全部变化条件,只是常见的大类,还有不少变形数独未举例,其实变形的条件不会有极限的,只要你有想象力,可以创造出属于你自己的新型变形数独。虽然数独条件变换多端,但有一条始终不变的绝对条件——同一限制区域内不能出现重复数字。只要符合这个条件,就没有脱离“数独”的范畴。

数独的近亲

       谜题(Pazzle):排除文化差异对做题者的影响,只用数字和图形表示的逻辑推理游戏。
  数独是谜题(Pazzle)中的一个分支,由于其规则简单、种类众多从而从众多谜题脱颖而出,成为大众熟知的数字谜题。
  不过除了数独以外,还有不少谜题也非常出色,也有众多的拥护者,而且与数独有千丝万缕的关系。数独爱好者同样不能错过这些优秀的逻辑推理游戏。下面简单介绍几类谜题:
  数和(Kakuro):与杀手数独很像的一类谜题,规则要求同行、同列(同一段)数字不能重复,且每段数字之和等于左边和上边的提示数字。
  数图(NonogramsGriddlers):根据盘面周围的数字提示,把盘中涂成符合条件的图案,很像“十字绣”。
  数回(Slither Link):游戏由0,1,2,3四个数字组成。每一个数字,代表四周划线的数目,并在最后成为一个不间断、不分岔的回路。
  数墙(Nurikabe):数墙的世界,是一个非黑即白的二元世界;在游戏中,你要决定的是,那些格子需要涂黑,那一些应该留白。
  数连(Number Link):与数独一样,数连是一个简单明快的游戏。你只需要把属于相同数字的同伴,以线连接起来。不过,这个游戏看起来非常简单,实际上是很有深度的。
  图独(tudoku):数独的一种扩展,将数字换成有趣的图形,看似一样,但换成图形后大大增强了数独趣味性,使游戏不会那么枯燥,很合适小孩子玩,即动脑又锻炼记忆力。

数独的难度

  数独的难度不好评价,因为它的各种局面互不相关,你别想用一种方法解决所有数独,这也是它的魅力所在,有人爱玩数独,因为他上瘾了,真的欲罢不能。
  数独的推理性强,像一些数学思想,推理,假设,反证(找矛盾)都有影子,换成计算机,它也做类似的事情,推理和假设变成搜索,反证变成回溯,做一件数学工作,难度就体现在这些基本的工作重复了多少,越多越难,如果推两下就出结果,那就容易,所以……
  就一般性的数独难度,拿两个指标来衡量,搜索次数S和回溯次数T,T越大越难,但和S也有关系,应该描述成回溯率,比如同样是回溯了10次,一个是20次的搜索,另一个是80次的搜索,那难度应该不同。换个思路,T可以看成是无效搜索,它一定是 S的一子集,即T<=S,如果T=S就表示无解,回退到了一开始的情况,而难度应该和有效搜索有关系,有效搜索比率就定义为难度系数,即H=(S- T)/S,它是[0,1]内的小数,它越小越难,那对一个难度的评价,可以取它的倒数,或者负对数,怎么表示好,看实验情况。
  其它因素。科学的评价,应该要考虑其它因素,像空格数,做为初学者就会觉得很重要,还有各个空格的不确定度,但是这些因素都会或多或少的影响到S和T。这里评价的前提是按照同样的搜索算法,那个算法和不确定度有关系,所以也可以反映出来。
  总结出来,评价的具体方法是,运用偶的搜索算法试解一个数独,在调用dfs时S计数加一,在dfs退出时T计数加一,在搜索到第一个解时停止统计,计算H,给出S,T和H。

给出数字最少的有唯一解的数独 数独(转自豆扣网) - 我的“江山” - 徐良雷

17个数(的确是唯一解,硫酸锌01做出来了)。

 

 


目前还没有发现16数的,这个就是最少的吧,但没人证明:

 

 

数独计算器

        在你对数独难题一筹莫展的时候,该数独软件将为了提供帮助, 数独计算器(数独助手)是一个特殊的数独工具,它试图提供人性化的数独解题方法,完全模拟人脑的思维过程解题,并且能一步一步的讲解每步的理由。我们希望数独计算器成为很好的使用逻辑方法解数独的工具,大家可以从数独助手的运行过程掌握更好的解数独题技巧,作为数独技巧教学的工具。
  数独计算器可以进行一步一步计算、指定步数计算、一次性计算,对于每一步计算给出详细的说明。对于有多个解的数独题目,会给出提示,并可人工干预。
  对每一步计算生成步骤列表,可以回到任意步骤进行研究。
  目前数独计算器采用的解题方法为典型的候选数法解题,新的解题方法会不断集成到这里,敬请持续关注。您有好的点子,也可以参与进来(数独论坛)。
  数独计算器支持数独题目的导入,使用数独论坛上的数独题目的通用格式,你可以很轻松的把数独BBS上数独难题导入到本软件中。

 

  评论这张
 
阅读(87)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017