数独简介及解题举例.docx

《数独简介及解题举例.docx》由会员分享，可在线阅读，更多相关《数独简介及解题举例.docx（18页珍藏版）》请在第一文库网上搜索。

1、数独简介及解题举例数独(日语：数独/寸5占SUdOkU)是一种逻辑性的数字填充游戏，玩家须以数字填进每一格，而每行、每列和每个宫(即3x3的大格)有齐1至9所有数字。游戏设计者会提供一部分的数字，使谜题只有一个答案。一个已解答的数独其实是一种多了宫的限制的拉丁方阵，因为同一个数字不可能在同一行、列或宫中出现多于一次。一、历史发展Is起源既然“数独”有一个字是“数”，人们也往往会联想到数学，那就不妨从大家都知道的数学家欧拉说起，但凡想了解数独历史的玩家在网络、书籍中搜索时，共同会提到的就是欧拉的“拉丁方块(1atinSqUare)”，如下图：拉丁方块的规则：每一行(Row)、每一列(Co1Umn

2、)均含I-N(N即盘面的规格)，不重复。这与前面提到的标准数独非常相似，但少了一个宫的规则。2、近代发展数独起源于18世纪初瑞士数学家欧拉等人研究的拉丁方阵(1atinSquare)019世纪80年代，一位美国的退休建筑师格昂斯(HOWardGarns)根据这种拉丁方阵发明了一种填数趣味游戏，这就是数独的雏形。20世纪70年代，人们在美国纽约的一本益智杂志MathPuzz1esand1ogicProb1ems上发现了这个游戏，当时被称为填数字(NumberP1ace),这也是目前公认的数独最早的见报版本。1984年一位日本学者将其介绍到了日本，发表在NikoIi公司的一本游戏杂志八;XrnZ通

3、信二口公上，当时起名为Suujiwadokushinnikagiru,后来觉得这个名字太长，就改名为“sudoku”，其中“su”是数字的意思，“doku”是单一的意思。这个名字也是国际上对数独的比较通用的叫法。后来一位前任香港高等法院的新西兰籍法官高乐德(WayneGOUId)在1997年3月到日本东京旅游时，无意中发现了。他首先在英国的泰晤士报上发表，不久其他报纸也发表，很快便风靡全英国，之后他用了6年时间编写了电脑程式，并将它放在网站上(这个网站也就是著名的数独玩家论坛)，后来因一些原因，网站被关闭，幸好数独大师G1ennFoW1er恢复了数据，玩家论坛有了新处所。在90年代国内就有部分

4、的益智类书籍开始刊登，南海出版社在2005年出版了数独12,随后日本著名数独制题人西尾彻也的数独挑战也由辽宁教育出版社出版。北京晚报、扬子晚报、羊城晚报、新民晚报、成都商报等等报纸媒体也先后刊登了数独游戏。二、组成元素1、方格水平方向有九横行，垂直方向有九纵列的矩形，画分八十一个小正方形，称为九宫格(Grid),如图一所示，是数独(Sudoku)的作用范围。3、列垂直方向的每一纵列有九格，每一纵列称为列（CoIUmn）,如图三所示。三行与三列相交之处有九格，每一单元称为小九宫（Box、B1ock）,简称宫，如图四所示（在杀手数独中，宫往往用单词Nonet表示）。第一宫B1第二宫B2第三宫B3第

5、四宫笫五宫第六宫BqB5B6第七宫第八宫第九宫B7B8B95、单元上述行、歹k宫统称为单元（Unit）06、区块由三个连续宫组成大区块（ChUte）,分大行区块（F1oor）及大列区块（TOWer）,第一大行区块:由第一宫、第二宫、第三宫组成。第二大行区块:由第四宫、第五宫、第六宫组成。第三大行区块:由第七宫、第八宫、第九宫组成。第一大列区块:由第一宫、第四宫、第七宫组成。第二大列区块:由第二宫、第五宫、第八宫组成。第三大列区块:7、格位编号由第三宫、第六宫、第九宫组成。格位按所处的行列单元赋予坐标值,如图五所示。OC4C5R1IUIUIUIU坐标有多种标示法，有横行A-I,纵列19（如中国）

6、，也有横行19,纵列A1（如日本），这两种标示容易混沼，故最被广泛使用的是横行R1R9,纵列C1C9的标示法。8、提示数在九宫格的格位填上一些数字，做为填数判断的线索（Hint）,称为提示数（CIUe）,如图六所示。三、基本解题解题的本质有二：隐性唯一解（HiddenSing1e）及显性唯一解（NakedSingIe）,他们的名称是在候选数法的基础上命名的。解题必须以逻辑为依归，猜测的方法被称为“暴力型”解法(BruteForce),这不是提倡数独的本意。根据解题本质发展出来的基本解题方法有二种：1、摒除法摒除法：用数字去找单元内唯一可填空格，称为摒除法，数字可填唯一空格称为摒余解(隐性唯一解

7、)。根据不同的作用范围，摒余解可分为下述三种：数字可填唯一空格在宫单元称为宫摒余解(HiddenSingieinBox)，这种解法称宫摒除法。数字可填唯一空格在行单元称为行摒余解(HiddenSingIeinRoW),这种解法称行摒除法。数字可填唯一空格在歹打单元称为列摒余解(HiddenSingIeinCoIUmn),这种解法称列摒除法。行摒余解和列摒余解合称行列摒余解(HiddenSingIein1ine)。得到行列摒余解的方法称为行列摒除法。2、直观法直观法就是不做任何记号，直接从数独的盘势观察线索，推论答案的方法。3、候选数法候选数法就是删减等位群格位已出现的数字，将剩余可填数字填入空

8、格做为解题线索的参考，可填数字称为候选数(Candidates,或称备选数)。直观法和候选数法只是填制时候是否有注记的区别，依照个人习惯而定，并非鉴定题目难度或技巧难度的标准，无论是难题或是简单题都可上述方法填制，一般程序解题以候选数法较多。四、进阶解题上述方法称为基础解法(BaSiCTechniques),其他所有的解法称为进阶解法(AdVanCedTechniques),是在补基本解法之不足，所以又称辅助解法。进阶解法包括：区块摒除法(1ockedCandidates)数组法(Subset)四角对角线(X-Wing)唯一矩形(UniqueRectangIe)全双值坟墓(Biva1ueUni

9、versa1Grave)单数链(X-Chain)异数链(XY-Chain)及其他数链的高级技巧等等。己发展出来的方法有近百种之多。其中前两种加上基础解法为一般数独书中介绍并使用的方法，同时也是大部分人可以理解并掌握的数独解题技法。通过基础解法出数只需一种解法，摒除法或唯余法，超出此范围而需要施加进阶解法时，解题点需要进阶解法协助基础解法来满足隐性唯一或显性唯一才能出数,该解题点的解法需要多个步骤协力完成，因此称做组合解法。1、相对概率相对概率不是真实的概率，而是用于同一格中的几个数字之间相互比较出现的可能。相对概率=九宫格出现的概率行出现的概率列出现的概率九宫格出现的概率：如果九宫格中有2个格

10、可能出现1,目标格可能的数字为1、2、3,另一个格可能出现的数字为1、4,那么：目标格中的1在九宫格出现的概率=目标格中出现1的概率X(1-另一个格中出现1的概率)，得3X(1-1/2)=注意：1-1/2表示另一个格不出现1的概率，电(1-1/2)的意思就是在另一个格不出现1的情况下，目标格出现1的概率。如果九宫格中有三个格可能出现1,目标格可能的数字为1、5、6,另一个格可能出现的数字为1、7,还有一个格可能出现的数字为1、8、9,得VBX(1-1/2)X(1-1/3)=1/9。依此类推。行出现的概率和列出现的概率与九宫格出现的概率的算法原理相同。最后,把三个概率相乘,得到相对概率，把目标格

11、中3个数字的相对概率进行对比，相对概率越大，出现的可能性越大。2、区块摒除法区块摒除法包括宫区块摒除法(POiming)与行列区块摒除法(C1aiming)在基础题里，利用区块摒除可以替代一些基础解法的观察，或辅助基础解法寻找焦点。在非基础题里，区块可以隐藏任何其他结构，简单的可以把基础解法隐藏起来，难的可以隐藏数对等等其他进阶技巧。五、难度划分影响数独难度的因素很多，就题目本身而言，包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。对于玩家而言，了解的技巧数量、熟练程度、观察力自然也影响对一道题的难度判断。市面上数独刊物良莠不齐

12、，在书籍、报纸、杂志中所列的难度或者大众解题时间纯属参考，常有难度错置的情况出现，所以不必特别在意。网络上有很多数独难度的分析软件，比较著名的是Nico1asJui11erat开发的SudokuExp1ainer和BernhardHobiger开发的Hodoku,它们都是免费的软件。因为每种软件的都有不同的解题策略，所以也只能作为难度的大致界定，无法真正的解析出难度的内涵。如果一道题目的提示数少，那么题目就会相对难，提示数多则会简单，这是一般人判断难易的思维模式，但数独谜题提示数的多寡与难易并无绝对关系，多提示数比少提示数难的情况屡见不鲜，同时也存在增加提示数之后题目反而变难的情形，即使是相同

13、提示数（甚或相同谜题图形）也可以变化出各式各样的难度。提示数少对于出题的困难度则有比较直接的关系，以2035提示数而言，每少一个提示数，其出题难度会增加数倍，在制作谜题时，提示数在22以下就非常困难，所以常见的数独题其提示数在2330之间，其原因在于制作比较不困难，可以设计出比较漂亮的图形（Pattern）,另外这个提示数范围的谜题变化多端是一个重要因素。六、终盘数量数独中的数字排列千变万化，那么究竟有多少种终盘的数字组合呢？6,670,903,752,021,072,936,960（约为6.67X1O的21次方）种组合，2005年由BertramFeIgenhaUer和FraZerJarVi

14、S计算出该数字，并将计算方法发布在他们网站上，如果将等价终盘（如旋转、翻转、行行对换，数字对换等变形）不计算，则有5,472,730,538个组合。数独终盘的组合数量都如此惊人，那么数独题目数量就更加不计其数了，因为每个数独终盘又可以制作出无数道合格的数独题目。七、标准数独目前（截止2011年）发现的最少提示数9X9标准数独为17个提示，截止2011年11月24日16:14,共发现了非等价17提示数谜题49151题，此数量仍在缓慢上升中，如果你先发现了17提示数的题目，可以上传至“17格数独验证”网站，当然你也可以在这里下载这49151题。关于是否有16提示数的合格题目，网络上也争论很久，有发

15、现16提示数双解的，但是仍未发现唯一解。国外有网友给出了关于为什么至少需要17提示的证明，受到了大家的质疑，比如9X9对角线数独（在标准数独规则基础上，两条大对角线的数字不重复）的最小提示数为12,按照他的理论则需要更多的提示数。另外在2006年GaryMcGuire撰写了程式，试图通过暴力法来证明16提示数的数独是否存在，方法很简单，既然BertramFe1genhauer和FrazerJarvis己经计算出不等价的终盘总数为5,472,730,538个,那么将每个终盘是16提示的情况都跑一遍，如果没有找到16提示的数独,那么就可以证明最少提示数为17个。但因为是暴力方法，对于一台单核的电脑来说需要跑30万年才能跑出结果。台湾的吴毅成教授和他的团队将GaryMCGUire的程式加以改进，使得效率大幅提升，大约2417年即可完成演算。并放在Bo1NC（伯克利开放式网络计算平台）上让世界加入Bo1NC的电脑一同演算，令人欣喜的是，截至编辑2012年4月18日已经完成了51.73%oGaryMcGuire的团队在2009年设计了新的算法，利用DeadIyPattern的思路，花费710万小时CPU时间后，于2012年1月1日提出了9X9标