标准数独.doc
《标准数独.doc》由会员分享,可在线阅读,更多相关《标准数独.doc(184页珍藏版)》请在三一办公上搜索。
1、标 准 数 独目 录第一篇一、 什么是数独二、元素构成三、数独规则四、解题方法五、解题手法1、摒除法2、余数法六、谜题的难易度第二篇一、数字的强链接和弱链接二、候选数的排除三、候选数的确定第三篇一、Single(唯一数)1、唯一显式候选数数(Naked Single)2、唯一隐式候选数数(Hidden Single)二、完全约束候选数(Locked Candidates)三、显式子集(Naked SubSets)1、显式数对(Naked Pair)2、显式三链数(Naked Triple)3、显式四链数(Naked Quadruple)四、隐式子集(Hidden SubSets)1、隐式数对(
2、Hidden Pair)2、欠一数对(Almost Locked Pair)3、隐式三链数(Hidden Triple)4、隐式四链数(Hidden Quadruple)五、 基础鱼形(Basic Fish)1、矩形对角线法(X-Wing)2、剑鱼(Swordfish)3、水母(Jellyfish)六、 单一数字图形(Single Digit Patterns)1、摩天楼(Skyscraper)2、双线风筝(2-String Kite)3、多宝鱼(Turbot Fish)4、空矩形(Empty Rectangle)第四篇一、 链和环(Chains and Loops)1、单数链(X-Chain
3、)2、XY链(XY-Chain)3、遥控数对(Remote Pair)二、翼(Wings)1、W-Wing(Y-Wing)2、M-Wing3、XY-Wing4、XYZ-Wing5、WXYZ-Wing6、XY Chain7、唯一矩形(Uniqueness Rectangle) UR1 UR2 UR3 UR4 UR5 UR6 隐式矩形(Hidden Rectangle) 全双值坟墓(Bivalue Universal Grave + 1) 可避免的矩形(Avoidable Rectangle)三、带鳍的/刺身(Finned/Sashimi)1、带鳍的X-Wing(Finned X-Wing)2、刺
4、身X-Wing(Sashimi X-Wing)3、带鳍的剑鱼(Finned Swordfish)4、刺身剑鱼(Sashimi Swordfish)5、带鳍的水母(Finned Jellyfish)6、 刺身水母(Sashimi Jellyfish)第五篇一、Sue de Coq二、Almost Locked Set(简称ALS)1、Almost Locked Set XZ-Rule2、Almost Locked XY-Wing3、Almost Locked Set Chain三、Nice Loop/AIC1、Continuous Nice Loop2、Discontinuous Nice Lo
5、op3、Grouped Discontinuous Nice Loop4、AIC5、Grouped AIC四、强制链(Forcing Chain)1、Forcing Chain Verity2、Forcing Chain Contradiction3、Forcing Net五、暴力解题(Brute Force)第六篇直观法解题一、宫摒除数对二、列摒除数对三、宫摒除对隐藏行列摒余解四、行列摒除对隐藏宫摒余解五、数对的聚焦六、一些例子另一、多重数对解题第一篇一、什么是数独?数独(Sudoku)又叫做九宫格数独,是一种源自于18世纪末的瑞士,后在美国发展,并在日本得以发扬光大的数字谜题。数独盘面是个
6、九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格中填入1-9的数字,且使数字1-9在每一行、每一列和每一宫中都只出现一次。这种游戏全面考验做题者的观察能力和推理能力,虽然玩法简单,但是数字的排列方式却千变万化,所以不少教育者认为数独是训练头脑的绝佳方式。二、元素构成宫格(Cell):又称单元格、格位,是数独中最小的单元,标准数独中共有81格;行(Row):横向9个单元格的集合,标准数独共有9行,可用R1、R2、R3.R8、R9来表示,也可用A、B、C.H、I来表示;列(Column):纵向9个单元格的集合,标准数独共有9列,可用C1、C2、C
7、3.C8、C9来表示,也可用1、2、3.8、9来表示; 宫(Box):三行与三列相交之处共有九单元,每个单元称为宫,可用第一宫、第二宫、第三宫.第八宫、第九宫来表示。单元(Unit):行、列、宫都称为单元。三、数独规则标准数独的规则为:数独每行、每列及每宫填入的数字必须为1-9,且不能重复。数独谜题按规则填写数字,最终必须只能有一个结果,也就是唯一解(Unique Solution),如果存在无解或两个及以上的解,则不被承认是数独谜题。先举个例子看看:上图中给定了一些已知数字(黑色),你能把空格中的数字填写完整么?答案:蓝色数字为自己填写的数字。是不是很简单呢!四、解题方法数独解题方法分为两种
8、:直观法和候选数法。直观法又称纸笔模式,就是不做任何记号,直接从数独的盘势观察线索,推论答案的方法。直观法一般只能解一些相对容易的谜题,一般在报刊杂志或是手机等出现的数独谜题用直观法就能解出谜题。上面例题用直观法就能解出答案了。候选数法就是删减等位群格位已出现的数字,将剩余可填入数字填入空格,作为解题线索的参考。可填数字成为候选数(Candidates)。一般直观法不能解出的谜题,用候选数法就能解出。但候选数法往往要用计算机软件作为辅助工具,因为人工填写候选数一是工作量大,二是容易填错或是漏填候选数,导致谜题不能被正确解出。候选数法举例:黑色大些的数字是题目给定的数字,宫格中小些的数字群就是候
9、选数。如果把候选数去掉,谜题形状为:你能用直观法把它解出来么?估计很困难,除非你有十分出众的记忆力和推理能力。谜题答案:五、解题手法解题手法本质上有两种:1、摒除法:用数字去找单元内唯一可填空格,称为摒除法。数字可填唯一空格称为摒余解(Hidden Single)。数字可填唯一空格在“宫”单元称为宫摒余解(Hidden Single in Box),这种解法称为宫摒除法;数字可填唯一空格在“行”单元称为行摒余解(Hidden Single in Row),这种解法称为行摒除法;数字可填唯一空格在“列”单元称为列摒余解(Hidden Single in Column),这种解法称为列摒除法。行摒
10、余解和列摒余解合称为行列摒余解(Hidden Single in Line).得到行列摒余解的方法称为行列摒除法。2、余数法:用格位去找唯一可填数字,称为余数法。格位唯一可填数字称为唯余解(Naked Single)。余数法是删减等位群格位已出现的数字的方法,每一格位的等位群格位有20个,如图所示:上述两种方法(摒除法、余数法)称为基础解法(Basic Techniques),其他所有的解法称为进阶解法(Advanced Techniques)。解数独谜题必须以逻辑依归,猜测的方法被称为暴力型解法(Brute Force),尽管有人认为暴力解法也算是一种逻辑解法,但这不是数独的本意,一般只用在
11、比赛中,平时练习尽量不用或少用。六、谜题的难易度谜题当然有难有易,目前已知的有唯一解的最少给定数字是17个。一般往往是给定的数字越多越容易,但不绝对,还要看给定数字的排列情况。有些情况下给定28个数很可能会比给定25个数字更难。不同的软件会用不同的方法衡量谜题的难易度,有的是用分值的方法,有的是用难度等级方法等等,在此不做进一步讨论。对个人解题而言也就是难者不会,会者不难。下面出几题难易不同的谜题供大家练习(直观法)。1、Easy(初级)2、Medium(中级)3、Hard(高级)第二篇上篇的一些题目你都能通过直观法做出来了么?如果完成了,那么你肯定对数独已经有了一个初步的概念。为什么是初步呢
12、?因为那些题目还是相对简单的。本章开始我们重点讨论一下相对比较难解的谜题,主要采用的解题方法是候选数法,并介绍一些概念和使用技巧。一、数字的强链接和弱链接链接是数独中最重要也是最根本的概念。链接有两种形式存在:强链接和弱链接。先看以下图形:观察数字3的情况,我们得到了数字3的所有强链接(蓝线表示);可以看到,每条蓝线的两个顶点数字3只在一行、一列或一宫中出现。我们用以下方法表示强链接:强链接的基本属性:若A为真,则B为假;反之若A为假,则B为真。简单地说,就是在一个单元(行、列、宫)中某候选数字只出现两次,那么这两数就形成强链接。另一种情况就是当某个宫格(也称单元格)中只有两个候选数时,这两个
13、候选数之间也是强链接。如宫格A4中的候选数3和9,宫格C3中的2和7,均组成它们之间的强链接。同一单元中还存在着未划线的多于两个候选数3的情况,它们形成了弱链接。如A行中宫格A4、A7、A9中的候选数3组成了3的弱链接。弱链接的基本属性:若A为真,则B为假;若A为假,则B不确定(可能为真也可能为假)。简单地说,在一个单元中某候选数字出现大于两次,那么该数字间存在着弱链接;在某个宫格中存在三个及以上候选数时,它们也形成了弱链接。如A9中的候选数2、3、9,G3中的3、6、8均组成了它们之间的弱链接。一个重要的说明:在解题时有时候我们可以把强链接当做弱链接看待,因为强链接的属性包含于弱链接的属性。
14、但是弱链接是不能当做强链接看待的。候选数法解题的原则就是去找出数字之间强弱链接的关系,从而排除或确定某个候选数为假(删除)或为真(填入)。二、候选数的排除为了书写方便,我们用一些符号来表示:等于(=);不等于();强链接(=);弱链接(-),推导过程(-)上图中红色圈中的候选数3可以排除。蓝色粗线为强链接,绿色细线为弱链接。其中也要理解有时强链接也能看做是弱链接的情况(第8宫为强链接,这里可以看成是弱链接)。R1C9(3) - R1C4(3) = R8C4(3) - R9C6(3) = R9C9(3) - R1C9(3)从上面表达式可以看出这些候选数3形成了一个封闭的环(Loop),且在该封闭
15、环中除了一个节点(R1C9)的相邻链接为弱链接外,其他均为强弱交替链接,则相邻链接为弱链接的候选数必须被删除。可以验证一下:若R1C4=3 - R1C93;若R1C43 - R8C4=3 - R9C63 - R9C9=3 - R1C93也就是说不管R1C4是否等于3,都能推导出R1C9不等于3,所以R1C9宫格中候选数3在逻辑上是不存在的,应该被删除。逐个删除逻辑不存在的候选数是候选数法解题的最主要技术方法 。三、候选数的确定看下图:若R6C77 = R4C7=7 - R4C67 = R4C6=4 - R4C34 = R6C3=4 - R6C32 = R6C1=2 - R6C17 = R6C7
16、=7上面的表达式假定R6C77,但是通过推导得出结论R6C7=7,从而证明假设R6C77是错误的,结果应该是R6C7=7从这条链接(环)中我们可以看出也是一条强弱交替出现的链接,其中只有一个节点(F7)的相邻链接为强链接,那么这个节点的数值就是该宫格值。第三篇本篇着重介绍一些解题时的常用技巧一、Single(唯一数)唯一数分为唯一显式候选数(Naked Single)和唯一隐式候选数(Hidden Single)1、唯一显式候选数(Naked Single)当某个宫格中候选数只存在唯一一个候选数时,该宫格值就是该候选数。如下图黄色标记所示的D1(R4C1)中候选数9、E3(R5C3)中候选数6
17、、H2(R8C2)中候选数1书写时可用D1=9(或R4C1=9)、E3=6(或R5C3=6)、H2=1(或R8C2=1)来表示。2、唯一隐式候选数数(Hidden Single)当某单元(行、列、宫)中某候选数只出现一次时,该候选数所在宫格值就是该候选数。I7的候选数9是第I行唯一出现的候选数,I7=9;E9的候选数2是第9列唯一出现的候选数,E9=2;G5的候选数5是第8宫(也称下中宫)唯一出现的候选数,G5=5。二、完全约束候选数(Locked Candidates)1、当某宫中某候选数只存在于某行(列)时,可删除在其他宫中此行(列)的候选数。第8宫中候选数1(绿色)只存在于G行,可删除G
18、行其他宫(第7宫、第9宫)中候选数1(黄色)。第2宫中候选数7(绿色)只存在于第3列,可删除第3列其他宫(第7宫)中候选数7(黄色)。2、当某行(列)中某候选数只存在于某宫中,可删除此宫中其他行(列)的该候选数第B行中候选数7(绿色)只在第1宫中,删除C2候选数7(黄色)。第6列候选数4(绿色)只存在于第2宫,删除A4、A5、B4、B5、C4、C5候选数4(黄色)。三、显式子集(Naked SubSets)1、显式数对(Naked Pair)在一个单元中,如果有两个宫格都包含且只包含相同的两个候选数,则这两个候选数不能再出现在该单元其他的宫格中。显示数对的形式为XY,XY。看上图I行中I1和I
19、8的候选数只有4和5(绿色),它们就组成了显式数对4 5,意味着在I行中4和5只能存在于I1和I8中,故能删除第I行中其他宫格的候选数4和5,如I2、I5、I6、I7中黄色候选数4和5。上图第9宫中G9和I8组成了显式数对2 5,可删除第9宫其他宫格中的候选数2和5。2、显式三链数(Naked Triple)在一个单元中,如果有三个宫格都包含且只包含相同的三个候选数,则这三个候选数不能再出现在该单元其他的宫格中。显式三链数的形式有很多种,如XYZ,XYZ,XYZ、XY,XYZ,XYZ、XY,YZ,XYZ、XY,YZ,XZ等等。上图中绿色数字宫格组成了显式三链数,可删除相应单元中的其他候选数(红
20、色)。3、显式四链数(Naked Quadruple)在一个单元中,如果有四个宫格都包含且只包含相同的四个候选数,则这四个候选数不能再出现在该单元其他的宫格中。上图中绿色数字宫格组成了显式四链数,可删除相应单元中的其他候选数(红色)。四、隐式子集(Hidden SubSets)1、隐式数对(Hidden Pair)在一个单元中,如果有两个宫格的候选数中包含有相同的两个候选数,且在该单元的其他宫格中不再含有这两个候选数,则这两个候选数所在宫格的除该两个候选数之外的其他候选数将被删除。第2宫(或第5行)中绿色候选数4和6只出现在A5和C5宫格中,红色候选数将被删除。2、欠一数对(Almost Lo
21、cked Pair)数对、三链数、四链数被统称为完全约束候选数(Locked Candidates),如果还差一点,就成为了非完全约束候选数(Almost Locked Candidates)。我们取其中的数对部分(Almost Locked Pair)来讲解。下面的讲解图中“/”表示不含有X和Y,“XY”表示可删除XY。R1C4和R2C1为双值格X Y,绿色方框中表示宫格中含有X和Y候选数。这样的盘面简单地说就是:如果宫中不含有X Y,则删除行(列)中其他X Y;如果行(列)中不含有X Y,则删除宫中其他X Y。举例:第4宫中除了双值格6,8,其余的6和8均在第5行,那么就可以把第5行的6和
22、8与第5行的双值格6,8结合起来看成是数对6,8可以删除棕色候选数6。欠一数对还能倒推应用:还是上图的例子绿色候选数要组成欠一数对的形式,必须把棕色候选数6删除。欠一数对这种技巧在直观法中应用的也比较多,如:通过摒除法得知画“X”的宫格中已不包含有7和8,而在第9宫的蓝色宫格中含有7和8的候选数,那么根据欠一数对技巧可以倒推出R8C6为双值格7,8。再用1对第8宫摒除得R8C5=1。欠一数对还可以稍微变换一下结构:同样可删除第1宫中其他宫格候选数X和Y。再加以演化一下:第一行可以看成是数对W,X而删除第1行其他宫格的W和X ;第一宫可以看成是数对Y,Z而删除第1宫其他宫格候选数Y和Z。这种技巧
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 标准
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-3882406.html