|
颠覆传统思维，破解数独密码 新理念、新观点、新角度，破解数独新方法 这是以数独规则为依据，将集合论和拓扑学的理论为数学基础，采用深度优先搜索算法，以新的视角、用新的思维，融合新的策略，以创新的手段开发出来的一种数独新解法。 数独进入中国以来，解题方法和解题技巧一直是国外经验一统天下。破解高难数独的“高级技巧”更是被国内数独爱好者奉为“宝典“。 破解数独果真就没有别的方法了吗？ 首先，我们要从数独的规则来研究：标准九宫数独的每个小方格内只能填上数字1至9，主要规则是：（1）每行、每列和每个小九宫都并且只包含数字1至9（2）每个单元格只包含一个元素（数字1—9），这个数字且与所在的行、列和宫都不重复。（3）标准数独题只有唯一解。 高难度数独是要通过“候选数法”才能快速顺利解题的，“候选数法”就是在待填单元格中将可能填入的数字列示出来，以供寻找破解的线索。 使用“高级技巧”需要通过搜索与“高级技巧”相符合的题面（数字排列），再进行推算、回溯、删除候选数或找出正确的答案。 那么候选数的性质又是什么呢？我们不妨先看一道难度系数为8.0的数独：  我们将数独作为一个集合，有81个单元格，九个元素（123456789）。他的子集分别是：行、列和小九宫，每个子集的元素也是九个，只是它们排列与组合有所不同。每个单元格只包含一个元素，这个元素在所处的行、列和宫都不重复。待填格的候选数也是一个集合，这个集合的元素≤9个。 我们用集合运算的方法将候选数填列出来。 数独是以行、列、宫作为基本单元的，因为每个单元格元素的变动，与之发生直接关联的是它所在的行、列和宫，这是数独规则所决定的。如果把行、列和宫的待填数作为一个集合，我们以上图的第五宫为例： 第四行待填数集合R4{1、2、3、5、6、7、8、9} 第五行待填数集合R5{、2、3、7、8、9} 第六行待填数集合R6{2、3、4、5、6、8、9} 第四列待填数集合C4{1、5、6、8} 第五列待填数集合C5{1、2、3、4、5、7、8} 第六列待填数集合C5{1、2、3、4、6、7、8} 五宫待填数集合B5{1、2、3、5、8、9}。见下图;  各待填格的候选数集合就是通过下列运算得到的 R4C5的候选数集合= R4∩C5∩B5{1、2、3、5、8}。 R4C6的候选数集合= R4∩C6∩B5{1、2、3、8、9}。 R5C4的候选数集合= R5∩C4∩B5{8}。 ……。 可见，单元格的待填候选数就是该单元格所在行、列、宫待填数集合的交集。当这个交集只有一个元素时，那么它就是该单元格的解。和我们通常用的余数法所计算出来的结果是一致的，见R5C4。 如果某个单元格候选数集合中的一个元素，是所在宫或行或列的其它所有单元格候选数集合的绝对补集，那么这个元素也是该单元格的解。换种说法就是：一个单元格候选数集合中的一个元素，与所在宫或行或列的其它所有单元格候选数集合都没有交集，那么这个元素也是该单元格的解。用排除法也会得出同样的结果。见图：  看到这里，我们还明白一个道理，单元格里的候选数其实就是一个解的集合，如果没有规则，就是一道多解题。 可见，破解数独题，我们是用规则在识别答案：找出符合规则的答案。也用逻辑推理的方法取破解数独，就是用一个又一个的判断去识别答案。所谓“高级技巧”的缺陷是，着眼于一数、一链非此即彼，非真及假的推演，过多的且繁琐判断过程和只能适用固定数据结构而掌握困难，运用于实践更加困难，而且大多数时候只能删除几个候选数，要想得到结果你可能需要几次的推演。正因为如此，在实战中得大多数情况下往往推不出一个确定的结果，忙了半天无果而终。九宫数独约有6.67×10的21次方种组合，就是剔除重复（如数字交换、对称等）后，也有54亿多种。每个组合又可以设计出n道数独题，即使高级技巧不断被发现，也无法适用千变万化的数独题。 从集合论的角度来看，数独就是一个集合，虽有81个单元格，但只有九个元素（1、2、3、4、5、6、7、8、9）。如果我们把一个数独题作为一个全集U，子集S则是：行、列和小九宫，每个子集的元素也是9个元素，只是它们排列与组合有所不同。  我们把数独的待填数看成一个集合，它的元素总是≤9个。每个单元格的待填候选数的个数却远远大于集合的元素的个数，这是因为每个待填单元格的候选数总是≥2，真正的答案隐藏其中，其它“候选数”组成了一个假候选数集合。 通过对“世界最难数独”的逆项工程，得到以下候选数表。红色数字是该单元格的解，仔细观察就会发现：四宫E3、D3和F2都存在数组{2、6}。在确认F3的解是9以后可继续确认D3的解是4，再确认F2的解是8。 在解题过程中经常会利用数对锁定待填数和待填格来精简候选数和确认解。当一个单元只剩两个待填格时，它们一定是一个双值数对，双值数对是最典型的数对，此外还有三值数对，四值数对。这些数对，对解题不利的方面是循环、结构牢固，给解题带来困惑。 既然数独就是一个数的集合，每个待填的候选数是一个子集，这个子集中只有一个元素是符合数独规则的元素，这是数独题探求的结果。这也是分析数学—拓扑学研究的对象。 创新解法的核心就是要找出候选数集合中隐藏的数对，如果一个候选数集合有n个元素，我们就得找到n+1个同样的选数集合，因为n个元素只能占用n个待填格。在删除多出的那个候选数集合后要保证能得到有效解，否则毫无意义。这也是创新解法得独特之处。所以，了解数对在解题中的意义很有必要。 我们在解题过程中所遇到的数对都是显性数对，它的表现形式有两种：一、n个待填格中只有数对中的数（数对中有n个数），别无其它候选数。待填格中只有数对中的全部或其中的几个数，可删除的是所在宫或行或列其它待填格数对中的候选数；二、只有n个待填格中有数对中的n个数，可删除的是所在待填格中其它候选数。 显性数对通过肉眼观察即能获得，创新解法所要寻找的是隐性数对。隐形数对也有两种表现形式：半隐性数对和全隐性数对。 既然我们运用分析数学—拓扑学作为破解数独的理论，那么，我们就要寻找到一个适合的算法来求出答案。 我们知道，很多问题在无法根据某种确定的计算法则，同时也不能找出适用的数学模型来求解时，可以用搜索与回溯的技术求解。那么，深度优先搜索（DFS）算法为我们提供了一个可用的工具，这种算法也是计算机常用的算法。专业的表述就是：搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。 我们可以运用深度优先搜索（DFS）算法寻求破解数独。 深度优先搜索（DFS）算法的特点就是利用计算机高性能计算速度和能同时多点发起搜索的优势，采用穷举遍历的方法找出答案。可是人脑和手工在短时间内是很难完成的。 如果我们能够利用化整为零的方法缩小数据规模，科学的筛选出高效可靠的搜索发起点，正确定义解题空间，在搜索过程中再利用剪枝函数避免回溯减少无效搜索。那么，人脑和手工运用深度优先搜索算法破解数独还是有可能的。当然，用计算机软件来实现这个方案将会更快。 第一、如果以九宫数独的小九宫、行和列作为研究对象，他们组合便只有362，880种。再以小九宫、行和列的待填格作为研究对象，数据的规模将会更小。 整个九宫数独的81个单元格是相互联系的，如果只是以小九宫、行和列为研究对象，把它们与整个九宫割裂开来，这样得出的解岂不是令人担心？大可不必，因为数独题的每个待填单元格的元素（数）是唯一的，早就确定的。我们看不到它，它只是隐藏在了其它候选数之中，它不会因我们的解题方法和解题线路而改变。根据数独规则“（2）每个单元格只包含一个元素（数字1—9），这个数字且与所在的行、列和宫都不重复“的定义，它们只与所在的九宫、行列有关联，仅此而已。 第二、根据数独的规则定义解题空间。每个单元格只有一个有效元素，且与所在的小九宫、行和列其它单元格的元素不重复，这是数独规则的要求。我们定义的有效解是：当一个单元格只有一个元素不包含在该单元格的所出现的子集中，那么，这个元素就是该单元格的解。 为什么这样说？每个单元格的元素是唯一的，而那有三个或更多的候选数待填格中，除了那个解外，其它的候选数正是一个假候选数的集合。我们只要根据一定的规则筛选出这些假候选数的集合，那么，这个单元格中孤独的元素自然就是该单元格的解。 从这个理论出发，当一个候选数集合在单元（行、列、宫）中的个数多于这个集合元素的个数时（集合的数量多于该集合的元素），才能进行删除，而且在待填格中删除该候选数集合后能得到有效解。 如果一个待填格中有两个子集的并集且没交集，这两个子集符合删除的数量要求时，也可作为确认有效解的删除依据。 一个单元中，某个候选数出现在所有的待填格中，我们称它为“公共候选数”。它将会与那些有三个及以上的其它候选数组成可确认有效解的候选数集合，而它将是那些子集的共同交集，确认解时要仔细分析。  如图1：候选数6在每个待填格中都有出现，它就是公共候选数待填数1、2、9每个都出现3次，它们都能与6组成有效的可定义解的（三个）数组集合A{1、6}、B{6、9}、C{2、6}，此时不能随意删除和任意确认其中的一个候选数是解（例：删除A1中的{1、2}、{1、6}或{2、6}，去定义另一个数是解）。定义没有交集的待填格B1的解是4（4只出现两次）。 下图也是这种情况，候选数1在每个待填格中都有出现，候选数3、7、8每个都出现3次及以上，它们都能与1组成有效的可定义解的（3-4个）数组集合A{1、3}、B{1、7}、C{1、8}，此时不能随意删除一个去任意定义这几个候选数的一个为解（例：删除C2中的{1、3}、定义8是C2的解）。定义没有交集的待填格A1的解是4（4只出现两次）  在解题过程中，公共候选数不仅能帮助我们确认只出现两次的待填数的有效解，也能帮组我们在复杂的数据中确认有效解。如上例中的待填数4. 见图1：一宫有7个待填数，待填数5出现在每个单元格中；1和9出现三次；3和7出现四次，2出现5次。它们和5都能组成能确认有效解的集合。只有6出现两次，它分别出现在A1和C1。C1中的{2、3、5}多于{2、2、3、5}，确认C1的解是6。  在四个待填格中不能同时定义两个有效解。如果一个单元中只有两个待填格，它们必定是一个数对。如果只有三个待填格，它们共有7种组合，分别是1.{ABC、ABC、ABC}；2.{ABC、ABC、AB}；3.{ABC、ABC、AC}；4.{ABC、ABC、BC}；5.{ABC、AB、AC}；6.{ABC、AB、BC}；7.{ABC、AC、BC}。如果根据规则，每个组合都是循环，不能确认正确的解。在四个待填格中同时定义两个解是有问题的。  如上左图：五宫有四个待填格，每个待填格都有数组{2、3}。有效搜索发起点是F5{2、3}，按规则可删除两个{2、3}，似乎可以得到两个有效解D5是1、E6是9。可是，这其中有一个解是在只有三个待填格的情况下确认的解，是不合乎逻辑的。如果我们确认任何一个解，剩下的三个待填格候选数组合是{23n、23n、23}，无法确认解。最终正确答案是E6=9；D5=2。 第三、利用剪枝函数避免无效搜索。如一个数组有两个元数（比如A、B），那么在另外一个单元格也应有一个一样的数组，不然一个单元格无法安放两个元素。我们在确定子集的数组时，要保证它与其它子集∪时，至少要有一组∪中不存在∩。确定子集元素时要保证子集中的元素在上一层集合中它们是连接最紧密（最多）的。 第四、确定集合研究的范围也很重要，它可以避免我们在解题过程陷入混乱和迷茫。数独不研究有0个元素的集合，因为数独的每个单元格必须且只有一个元素，不存在空单元格。也不研究只有一个元素的集合，因为一个单元格只有1个元素，他就是这个单元格的解，再去研究毫无意义。 我们将数独题的待填数定义为全集U，研究单元（小九宫、行和列）定义为子集S，每个单元的候选数以数组为子集A、B、C、……，子集A的子集是A1、A2、An……。数组子集的并集为T，T是S的子集。当数组子集A、B、C的元素是n(n≥2)个时，它应当同时在≥n个单元中出现。这是数独规则所要求的，如一个数组有两个元数（比如A、B），那么在另外一个单元个也应有一个一样的数组，不然一个单元格无法安放两个元素。 当一个单元（宫、行和列）的某个候选数只出现两次，这个候选数可以不用把它编入子集中。因为，我们定义：在一个单元中，如果一个子集仅出现两次，不能作为确认解的依据。否则，很有可能让我们在解题时进入死循环。 如果某个单元有多个候选数只出现两次，而其他候选数数组又组成了与之数量相同的集合，那么，这些集合不能删除，也不能作为确认解的依据。 第五、在对一个小九宫、行和列进行深度搜索（DFS）算法得出解之后，应立即用排除法和余数法整理题面。一是可以验证解的正确性，二是如果发现运用排除法和余数法即能顺利解题，就可终止使用深度搜索（DFS）和回溯算法，毕竟用排除法和余数法解题要快速和容易很多，避免不必要的回溯。深度搜索（DFS）也可在多点（小九宫、行和列）同时发起。 第六、关于数对。创新解法的核心就是要找出非正解候选数的数对，如果一个非正解候选数集合有n个元素，我们就得找到n+1个同样的非正解候选数集合，因为n个元素只能占用n个待填格。在删除多出的1个非正解候选数集合后要保证能得到有效的解，否则毫无意义，这也是创新解法得独特之处。所以，了解数对在解题中的意义很有必要。 我们在解题过程中所运用的大都是显性数对和隐形数对。 显性数对：n个待填格中只有数对中的数（数对中有n个数），别无其它候选数。待填格中只有数对中的全部或其中的几个数，可删除的是所在宫或行或列其它待填格候选数中的数对数。如图：数组{2、7}就是典型的显性数对，本宫和相关列的其它待填格候选数中的2和7都要删去。  隐形数对：只有n个待填格中有数对中的n个数，可删除的是所在待填格中其它候选数。由于它们被其它候选数包裹着往往难以发现。如图：  图中数组{1、2}就是典型的隐形数对，它们分别被其他候选数{4、6、8}和{4、5、6}包裹着，不认真观察不易发现。 隐形数对还有多种非典型表现方式： 所谓非典型隐形数对：就是在一个单元中，有两个及以上的待填数总是同时出现在相同的待填格中。见非典型隐形数对-1：这是所谓“世界最难数独”第五宫开局全标候选数图，我们发现，五宫的每个待填格中都有数组{2、8}，按规则可以删除三个{2、8}数组，但只有删除C2的{2、8}可确认有效解是6。  典型隐形数对-2，在实践中也会经常遇到，从图可以看出，在该宫，待填数3和5都是同时出现在相同的待填格中，组成不可分割的数组{3、5}。 这种形式在实战解题中有什么意义呢？按照常规搜索法，该宫无法发起有效搜索，任一个三值格或四值格都不能找到3个或4个相同的数组，也就是不能发起有效搜索，也就无法得到有效解。如果发现了这个隐形数对，就可以从D3{1、6}、E3{6、7}、F2{8、9}、F3{2、7}发起有效搜索，从而可确认E2的有效解是9。 隐性数对也有两种表现形式：半隐性数对和全隐性数对。创新解法解题时九是通过搜索半隐性数对来确认有效解。通常的做法是通过显性数组来寻找（搜索）隐性数对（非正解候选数的集合），搜索到的非正解候选数集合的个数超过数对元素的数量时，对确认有效解才有实际意义。如果是一个双值数对，需要找出三个或以上相同的数组，才能删除多余的数组。 选择搜索发起点的目的时寻找隐性数对的另一半，我们知道在一个单元中出现数对，这个单元其他待填格就不能再出现数对中的数，解题实践中帮组我们简化题面的候选数，又是也能直接得出有效解。 如上图：从A1{1、2、4、7}或B2{2、4、6、7}发起搜索，都不能得到4个相同数组，因为这个数组有四个元素，我们把它称之为无效搜素。我们如果从B1{2、4、7}发起搜索，发现共得到5个相同数组，因为这个数组只有三个元素，根据数对的定义，我们可以删除两个待填格中的数组{2、4、7}。但是，有三个待填格在删除数组{2、4、7}后可得到解。A1和C3可得到的解是1，B2可得到的解是6。根据数独规则，只能删除两个，取两个解，显然A1和C3的解是不符合数独规则的，只得舍弃。没有争议的而能确认的有效解是B2，它的解是6。 全隐性数对就是无法通过搜索半隐性数对的方法得到，它只能通过因素分析法得到，在遇到数据结构复杂，用搜索半隐性数对的方法无法获得任何有效解的情况下而使用的一种方法。 在所有单元都无法发起有效搜索，或搜索不到有效的候选数集合，或无法确认有效解，这时需要运用因素分析法来获得全隐性数对。 因素分析就是对一个单元所有待填格的候选数进行分析，找出隐性的有效候选数集合，这些候选数集合必须是明确的没有交集的有效的并且能确认有效解的候选数集合。 见上图：A1{2、7、8、9}；A2{5、6、7、8、9}；B1{1、2、7、8、9}；B2{1、6、7、8、9}；C2{1、5、7、8、9}。与其他子集{1、2}和{5、6}没有交集。并且能确认A1的有效解是2。 再看第二例，存在全隐性数对{4、5、6}和{2、3、8}。数对{4、5、6}共6个，（包含两个子集{4、5}）；数对{2、3、8}共有5个（包含1个子集{2、8}）。搜索过程中避开了发生交集的情况。因此得到两个有效解1和9。 这是有一个运用全隐性数对解题的例子，宫中只有一个提示数，无论从哪个待填格都不能发起有效搜索，但是该宫有非典型隐形数对{5、9}，这个数对不能帮我们直接确认有效解。在所有出现数对的待填格中还存在2个及以上的其它候选数。特别是有3个及以上候选数但又无法发起有效搜索时，就很难得到有效解，如果仅凭主观臆断对候选数进行组合划分，出错的概率会很大。这时我们可以利用非典型的隐形数对来搜索全隐形数对。这一例中，发现有四个{5、6、9}数组，还有一个子集{5、9}数组，继续搜索过程中避开出现交集的情况，得到D1的有效解是2。 显性数对、隐形数对、非典型隐形数对、隐性数对的特点。 显性数对和隐形数对是一组确定的数对，它们的存在可直接删除与它们相关的其他待填格中的（数对）候选数，起到精简题面的作用，有时也能得到有效解。 非典型隐形数对：可以确认一定存在一组数对，但是到底是由哪几个单元格来组成数对并不确定。有时可以直接确认有效解，有时可帮助我们发起有效搜索找到有效解。 隐性数对不一定存在真正的数对，他只是帮助我们找出解的媒介。 第七、策略 一、搜索的策略 1、搜索单元以宫优先。根据几何学的定义，行和列属于线是一维图形，宫属于面是二维图形，宫的作用面要大于行和列，得到解的可能性大。 2、从候选数少的待填格优先发起搜索。这是因为元素少更容易组成本解法意义上的有效集合，也更容易得到有效解。从实践来看，在三值格中搜到有效解的概率很高。 3、元素多的集合优先于元素少的集合。如：4元素集合→3元素集合→2元素集合……。例：从{A、B}发起搜索，搜索到了{A、B、C}数组集合且满足定义有效候选数集合的条件（三个），这是{A、B}只能作为{A、B、C}的子集出现，而不能利用{A、B}去确认{A、B、C}中的解。 4、在一个单元中（行、列、宫）的两个待填格中同时搜索到相同解（两个单元格得到同一个数字的解）的情况时：独立子集优先于并集；并集优先于有交集的；出现次数多的优先于出现次数少的。注意：有交集的待填格不可确认有效解。 5、开局搜索从提示数最多的行列宫开始。 二、规避风险的策略 1、利用优先搜索策略减少无效搜索。 2、优先规避回溯风险。在一个单元（行、列、宫）的两个待填格中同时搜索到相同解（两个单元格得到同一个数字的解）的情况，只要存在疑义，就果断舍弃。 3、开局慎用残局定义解的规则。 第七、因素分析法。 在所有单元都无法发起有效搜索，或搜索不到有效的候选数集合，或无法确认有效解，这时需要进行纵深分析。 因素分析就是对一个单元所有待填格的候选数进行分析，找出隐性的有效候选数集合，这些候选数集合必须是明确的没有交集的有效得并且能确认有效解得候选数集合。 我们用下面这题难度系数为10.4的数独题为例，全标候选数见下图： 这道题用常规搜索法，一时很难发现有效解。下面运用因素分析法来解题，先从五宫入手： 首先在五宫发现了非典型隐形数对{1、4}用橙色标记，它出现在每个待填格中。其他待填数3和7都出现五次、2出现三次，都用绿色标记。5和9都只出现两次不做标记。先看D4的候选数5，除了数组{1、4}还有数组{3、7}，数组{3、7}共有三个，可以删除一个。E4也有候选数5，但七数组{2、3、7}只有两个，不符合确认有效解的条件。再看待填数9，分别出现在D5{1、4、7、9}和F6{1、3、4、9}，除了隐形数对{1、4}外，待填数3和7都出现在5个待填格中，所以不能确认哪个是有效解。 这例中的数组{1、4}既是非典型隐形数对也是公共候选数。 再来看四宫，四宫也存在非典型隐形数对{2、8}。以数对{2、8}为起点，E2除了数对{2、8}外还有数组{4、5、6}，共搜索到四个{4、5、6}数组，可组成一个有效的候选数集合，并能确认D2的解是9。但同时，又可以组成有效的{4、5、8}、{4、5、9}和{2、3、4}候选数集合。他们的交集是∩{4、5}。这种情况应慎重行事。 我们看三宫，从C8{4、6、9}发起搜索，引出数组{4、8}。数组{4、8}共有三个，根据数对理论，可以删除一个，在删除C9的{4、8}后可确认C9的有效解是3。我们见终盘图：C9的解确实是9。但A7和A9的4、8并不是真正以数对形式存在的，C7的解是6，C9的解是8。 见上图：A1{2、7、8、9}；A2{5、6、7、8、9}；B1{1、2、7、8、9}；B2{1、6、7、8、9}；C2{1、5、7、8、9}。可以看出，数组{8、9}是一组非典型隐形数对。{7、8、9}、{5、6}和{1、2}都属于全隐形数对。这些数对的集合相互之间不存在交集。并且能确认A1的有效解是2。 最后，这些理论的经过实战的演练才发现它的瑕疵和新的规律，亦不断完善走向成熟。以后将会以更多的实例来验证这种创新解法格可行性和可靠性。欢迎数独爱好者提供难题。 |
|
|
