当前位置:文档之家› 标准数独(1)讲解

标准数独(1)讲解

标准数独目录第一篇一、什么是数独二、元素构成第六篇直观法解题一、宫摒除数对二、列摒除数对三、宫摒除对隐藏行列摒余解四、行列摒除对隐藏宫摒余解五、数对的聚焦六、一些例子另一、多重数对解题第一篇一、什么是数独?数独(Sudoku)又叫做九宫格数独,是一种源自于18世纪末的瑞士,后在美国发展,并在日本得以发扬光大的数字谜题。

数独盘面是个九宫,每一宫又分为九个小格。

在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格中填入1-9的数字,且使数字1-9在每一行、每一列和每一宫中都只出现一次。

这种游戏全面考验做题者的观察能力和推理能力,虽然玩法简单,但是数字的排列方式却千变万化,所以不少教育者认为数独是训练头脑的绝佳方式。

二、元素构成宫格(Cell):又称单元格、格位,是数独中最小的单元,标准数独中共有81格;行(Row):横向9个单元格的集合,标准数独共有9行,可用R1、R2、R3......R8、R9来表示,也可用A、B、C......H、I来表示;列(Column):纵向9个单元格的集合,标准数独共有9列,可用C1、C2、C3......C8、C9来表示,也可用1、2、3......8、9来表示;宫(Box):三行与三列相交之处共有九单元,每个单元称为宫,可用第一宫、第二宫、第三宫......第八宫、第九宫来表示。

单元(Unit):行、列、宫都称为单元。

三、数独规则标准数独的规则为:数独每行、每列及每宫填入的数字必须为1-9,且不能重复。

数独谜题按规则填写数字,最终必须只能有一个结果,也就是唯一解(Unique Solution),如果存在无解或两个及以上的解,则不被承认是数独谜题。

先举个例子看看:上图中给定了一些已知数字(黑色),你能把空格中的数字填写完整么?答案:蓝色数字为自己填写的数字。

是不是很简单呢!四、解题方法数独解题方法分为两种:直观法和候选数法。

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

直观法一般只能解一些相对容易的谜题,一般在报刊杂志或是手机等出现的数独谜题用直观法就能解出谜题。

上面例题用直观法就能解出答案了。

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

可填数字成为候选数(Candidates)。

一般直观法不能解出的谜题,用候选数法就能解出。

但候选数法往往要用计算机软件作为辅助工具,因为人工填写候选数一是工作量大,二是容易填错或是漏填候选数,导致谜题不能被正确解出。

候选数法举例:黑色大些的数字是题目给定的数字,宫格中小些的数字群就是候选数。

如果把候选数去掉,谜题形状为:你能用直观法把它解出来么?估计很困难,除非你有十分出众的记忆力和推理能力。

谜题答案:五、解题手法解题手法本质上有两种:1、摒除法:用数字去找单元内唯一可填空格,称为摒除法。

数字可填唯一空格称为摒余解(Hidden Single)。

数字可填唯一空格在“宫”单元称为宫摒余解(Hidden Single in Box),这种解法称为宫摒除法;数字可填唯一空格在“行”单元称为行摒余解(Hidden Single in Row),这种解法称为行摒除法;数字可填唯一空格在“列”单元称为列摒余解(Hidden Single in Column),这种解法称为列摒除法。

行摒余解和列摒余解合称为行列摒余解(Hidden Single in Line).得到行列摒余解的方法称为行列摒除法。

2、余数法:用格位去找唯一可填数字,称为余数法。

格位唯一可填数字称为唯余解(Naked Single)。

余数法是删减等位群格位已出现的数字的方法,每一格位的等位群格位有20个,如图所示:上述两种方法(摒除法、余数法)称为基础解法(Basic Techniques),其他所有的解法称为进阶解法(Advanced Techniques)。

解数独谜题必须以逻辑依归,猜测的方法被称为暴力型解法(Brute Force),尽管有人认为暴力解法也算是一种逻辑解法,但这不是数独的本意,一般只用在比赛中,平时练习尽量不用或少用。

六、谜题的难易度谜题当然有难有易,目前已知的有唯一解的最少给定数字是17个。

一般往往是给定的数字越多越容易,但不绝对,还要看给定数字的排列情况。

有些情况下给定28个数很可能会比给定25个数字更难。

不同的软件会用不同的方法衡量谜题的难易度,有的是用分值的方法,有的是用难度等级方法等等,在此不做进一步讨论。

对个人解题而言也就是难者不会,会者不难。

下面出几题难易不同的谜题供大家练习(直观法)。

1、Easy(初级)2、Medium(中级)3、Hard(高级)第二篇上篇的一些题目你都能通过直观法做出来了么?如果完成了,那么你肯定对数独已经有了一个初步的概念。

为什么是初步呢?因为那些题目还是相对简单的。

本章开始我们重点讨论一下相对比较难解的谜题,主要采用的解题方法是候选数法,并介绍一些概念和使用技巧。

一、数字的强链接和弱链接链接是数独中最重要也是最根本的概念。

链接有两种形式存在:强链接和弱链接。

先看以下图形:观察数字3的情况,我们得到了数字3的所有强链接(蓝线表示);可以看到,每条蓝线的两个顶点数字3只在一行、一列或一宫中出现。

我们用以下方法表示强链接:强链接的基本属性:若A为真,则B为假;反之若A为假,则B 为真。

简单地说,就是在一个单元(行、列、宫)中某候选数字只出现两次,那么这两数就形成强链接。

另一种情况就是当某个宫格(也称单元格)中只有两个候选数时,这两个候选数之间也是强链接。

如宫格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均组成了它们之间的弱链接。

一个重要的说明:在解题时有时候我们可以把强链接当做弱链接看待,因为强链接的属性包含于弱链接的属性。

但是弱链接是不能当做强链接看待的。

候选数法解题的原则就是去找出数字之间强弱链接的关系,从而排除或确定某个候选数为假(删除)或为真(填入)。

二、候选数的排除为了书写方便,我们用一些符号来表示:等于(=);不等于(<>);强链接(==>);弱链接(-->),推导过程(->)上图中红色圈中的候选数3可以排除。

蓝色粗线为强链接,绿色细线为弱链接。

其中也要理解有时强链接也能看做是弱链接的情况(第8宫为强链接,这里可以看成是弱链接)。

R1C9(3) --> R1C4(3) ==> R8C4(3) --> R9C6(3) ==> R9C9(3) -->R1C9(3)从上面表达式可以看出这些候选数3形成了一个封闭的环(Loop),且在该封闭环中除了一个节点(R1C9)的相邻链接为弱链接外,其他均为强弱交替链接,则相邻链接为弱链接的候选数必须被删除。

可以验证一下:若R1C4=3 -> R1C9<>3;若R1C4<>3 -> R8C4=3 -> R9C6<>3 -> R9C9=3 -> R1C9<>3也就是说不管R1C4是否等于3,都能推导出R1C9不等于3,所以R1C9宫格中候选数3在逻辑上是不存在的,应该被删除。

逐个删除逻辑不存在的候选数是候选数法解题的最主要技术方法。

三、候选数的确定看下图:若R6C7<>7 ==> R4C7=7 --> R4C6<>7 ==> R4C6=4 --> R4C3<>4 ==> R6C3=4 --> R6C3<>2 ==> R6C1=2 --> R6C1<>7 ==> R6C7=7上面的表达式假定R6C7<>7,但是通过推导得出结论R6C7=7,从而证明假设R6C7<>7是错误的,结果应该是R6C7=7从这条链接(环)中我们可以看出也是一条强弱交替出现的链接,其中只有一个节点(F7)的相邻链接为强链接,那么这个节点的数值就是该宫格值。

第三篇本篇着重介绍一些解题时的常用技巧一、Single(唯一数)唯一数分为唯一显式候选数(Naked Single)和唯一隐式候选数(Hidden Single)1、唯一显式候选数(Naked Single)当某个宫格中候选数只存在唯一一个候选数时,该宫格值就是该候选数。

如下图黄色标记所示的D1(R4C1)中候选数9、E3(R5C3)中候选数6、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行其他宫(第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和I8的候选数只有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。

相关主题