数独顾氏不动点解法

顾氏不动点解法数独题通用解法 摘要： “数独” 意为“ 每个数字只能出 现一次 ”，起源于中国 的古代的九宫格。通过运用严格逻辑推理方法，顾氏 不动点解法找到两条或两条以上不同的逻辑路径的交 点，即数独题目的关键点，找到一种解决数独问题的 通用方法。 关键词: 数独 九宫格 顾氏不动点 Abstract: Sudoku is that one number shows only one time, it is Chinese Jiugongge by origin. Gushi fixed point method finds the point of intersection for two or over two different logic roads by logic and reasoning method, it is the key point of Sudoku question, so that it finds a general method to calculate Sudoku question. Keywords： Sudoku Jiugongge Gushi fixed point 引言 “数独”一词源于日语，是“SUDOKU”的 音译，意为“每个数字只能出现一次 ”。数 独起源于中国的古代的九宫格。到了 18 世纪，瑞士盲 人数学家欧拉在九宫格的基础上发明了“拉丁方块” ， 即今天的“数独”的雏形。标准数独是一个 99 格的正 方形，解题过程需要不断运用逻辑推理，通过已知数 字得出未知数字并填入相应的空白单元格内，使得每 一个数字在每一行、每一列、每一宫中不重复。目前常 见的数独解法有直观法和候选数法。在解决相对简单 的数独题时， 直观法可以快速解题。但是在解决比较 复杂的数独题， 直观法就很难解出。现有的候选数法 可以解决一些复杂的数独题，但是遇到某些难题还是 无法精确解出，这时就需要用猜的办法来得到数独题 的结果。顾氏不动点解法是一种数独题目的通用解题 方法，用顾氏不动点解法可以找到关键点，即顾氏不 动点，从而化解了题目难度。本文主要对顾氏不动点 解法做详尽的描述，并加以简要地证明。 一. 什么是数独 标准数独是一个 99 格的正方形，在这个正方 形中又按照 33 格划分为 9 个宫，每 1 个小方格成为 一个宫格，如 图 1 所示。其规则是给定 9 个数字，每个 宫格只能填一个数字，每个宫格可填的数是唯一的， 即数独题有唯一解。每一个数字在每一行、每一列、每 一宫中不重复。通过已知数字得出未知数字并填入相 应的空白宫格内。 二顾氏不动点解法 (一) 建立九宫坐标系 对每一行，每一列按照顺序分别标以 1，2，3，4，5，6，7，8，9；每一宫格对应的行与列即为 该宫格的坐标。行坐标在前，列坐标在后，对位于 x 行 y 列的宫格标记为（x，y）。 (二) 给宫排序 按照从左到右，从上到下的顺序，对 9 个宫排序， 分别记为 1、2、3、4、5、6、7、8、9 宫。 (三) 顾氏不动点的定义 在数独题中选择几种完全互补的可能，分别进行逻 辑推理，得出几条逻辑路径，当这几条逻辑路径的交 点为相同数字时，此数字即该宫格的解，则该宫格为 顾氏不动点。 这里完全互补是指，位于同一行或者同一列或者同 一宫的几个宫格中，几种可能之和即为该事件的全部 可能，即对该事件而言，这几种概率之和为 1，这是解 出顾氏不动点的充要条件。 (四) 顾氏不动点相容性 一般而言，在用直观法解出部分宫格之后，经常能 找到两种完全互补可能的宫格。在寻找顾氏不动点时， 当已经选择两种完全互补的可能之后，发现其中一条 逻辑路径出现两个矛盾的分支时，选择与另一条逻辑 路径相容的分支继续进行即可，此时与另一条逻辑路 径的交点出现相同数字时，都是顾氏不动点。（此即顾 氏不动点理论定理 A，准确表述如下：在寻找顾氏不 动点时，从两条完全互补的逻辑路径出发，当其中一 条路径出现矛盾的两个分支 之后，应当选择与另外一条逻 辑路径相容的分支继续进行， 此时与另外一条逻辑路径的 交点宫格出现相同的数字时， 这些交点宫格及其上的相同 数字就都是顾氏不动点。） (五) 应用范围说明 1. 使用顾氏不动点解法解数独题之前，应尽可 能的用其他方法解题，直到其他方法无法继续时， 再用顾氏不动点解法，这样可以提高解题效率。 2. 如果找到一个顾氏不动点后仍不能用其它方 法解开此题，应继续寻找更多的顾氏不动点，直 到解开此题为止。 3. 随意选择某一完全互补的两种可能，并不一 定得到顾氏不动点，得不到顾氏不动点时为无效 选择，此时应再考虑别的完全互补的的可能，持 续这种选择就一定能找到至少一个顾氏不动点， 能找到顾氏不动点的选择称为有效选择。 4. 对于任一数独题来说，选择不同的起点，可 能找到不同的顾氏不动点，可能只需要部分不动 点即可完全解开该题。 5. 广义的顾氏不动点解法同样有效，选择两种 完全互补的可能，分别进行逻辑推理，得出两条 逻辑路径 A 和 B，当 这两条逻辑路径在某几个宫 格出现同样的数组时，则出现相同数字的那几个 宫格称为顾氏不动点区域。 四顾氏不动点解法例题 例 1：如图 2 所示， 解：本题用直观法解不出任何宫格。 如图 3 所示标出每个空白宫格的候选数，开始找顾氏 不动点，解法如下： 1. 选择逻辑路径起点，令（4，2）2，可得（5，1） 1 2. 选择另一逻辑路径起点，令（4，2）7； 由（4，2）7，可得（6， 7）7； 由（6，7）7，可得（4， 9）6； 由（4，9）6，可得（1， 9）7； 由（1，9）7，（4， 2）7，可得（ 2，3）7； 由（2，3）7，可得（2， 4）3； 由（2，4）3，可得 （6，5）3； 由（6，5）3，（6， 7） 7，可得（6， 2）2； 由（6，2）2，可得 （5，1）1 3. 到目前为止，按照顾氏不动 点解法得到了顾氏不动点（5，1） 1 4. 下面可用直观法来解出本 题了，结果如图 4 所示。 由（5，1）1，可得（1， 3） 1； 由（5，1）1，第 6 宫中 1 只能在第 8 列，可得 （9，7）1； 由（9，7）1，得（9， 6）9，（ 8，7）8；（7， 5） 1； 由（9，6）9，得（9， 5）8，（ 3，5）9； 由（9，5）8，得（4， 4）8，（ 5，4）9，（ 4，5） 2； 由（4，5）2，得（6， 2）2，（ 4，2）7； 由（4，2）7，得（4， 3）9，（ 4，9）6，（ 2，3） 7，（3， 2）3； 由（2，3）7，得（8， 4）7； 由（4，9）6，得（1， 7）6，（ 6，7）7，（ 1，9） 7，（6， 6）6，（ 6，7）7； 得（6，8）1，得（4， 8）5； ? 由（4，3）9，得，（ 5，3）3； ? 由（3，2）3，得（3，6）7，（ 3，8）2，（2，7） 4； ? 由（2，7）4，得（1，8）3，（ 1，5）4，（1，4） 5； ? 由（1，4）5，得（2，4）3，（ 2，6）2，（1，1） 2，（2， 1）5； ? 由（2，4）3，得（6，4）4，（ 6，5）3，（8，4） 7，（8， 6）4； ? 由（6，4）4，得（5，6）5，（ 4，6）1，（4，8） 5，（5， 9）4，（ 6，8）1； ? 由（5，9）4，得（7，8）4，（ 9，2）4； ? 由（9，2）4，得（7，