顾氏不动点解法--数独题通用解法Abstract:Sudoku is that one number shows only one time,it is Chinese Jiugongge by origin. Gushi fixedpoint method finds the point of intersection fortwo or over two different logic roads by logic andmethod, it is the key point of Sudokureasoningso that it finds a general method toquestion,Sudoku question.calculate摘要：“数独”意为“每个数字只能出现一次”，起源于 中国的古代的九宫格通过运用严格逻辑推理方法， 顾氏不动点解法找到两条或两条以上不同的逻辑路径 的交点，即数独题目的关键点，找到一种解决数独问 题的通用方法关键词： 数独 九宫格顾氏不动点I:II I£Keywords： Sudoku Jiugongge Gushi fixed point引言“数独” 一词源于日语，是“SUDOKU” 的音译，意为“每个数字只能出现一次”。
数独起源于中国的古代的九宫格到了 18 世纪，瑞士盲人数学家欧拉在九宫格的基础上发明了“拉丁方块”，即今天的“数独”的雏形标准数独 是一个9 x 9格的正方形，解题过程需要不断运用逻辑 推理，通过已知数字得出未知数字并填入相应的空白 单元格内，使得每一个数字在每一行、每一列、每一 宫中不重复目前常见的数独解法有直观法和候选数 法在解决相对简单的数独题时，直观法可以快速解 题但是在解决比较复杂的数独题，直观法就很难解 出现有的候选数法可以解决一些复杂的数独题，但 是遇到某些难题还是无法精确解出，这时就需要用猜 的办法来得到数独题的结果顾氏不动点解法是一种 数独题目的通用解题方法，用顾氏不动点解法可以找 到关键点，即顾氏不动点，从而化解了题目难度本 文主要对顾氏不动点解法做详尽的描述，并加以简要 地证明tIt:e:tt（三）顾氏不动点的定义在数独题中选择几种完全互补的可能，分别进行逻 辑推理，得出几条逻辑路径，当这几条逻辑路径的交一.什么是数独标准数独是一个9 x 9格的正方形，在这个正 方形中又按照3x3格划分为9个宫，每1个小方格成 为一个宫格，如图1所示其规则是给定9个数字， 每个宫格只能填一个数字，每个宫格可填的数是唯一 的，即数独题有唯一解。
每一个数字在每一行、每一 列、每一宫中不重复通过已知数字得出未知数字并 填入相应的空白宫格内二•顾氏不动点解法（一） 建立九宫坐标系对每一行，每一列按照顺序分别标以1, 2, 3, 4, 5, 6, 7, 8, 9;每一宫格对应的行与列即为该宫格的 坐标行坐标在前，列坐标在后，对位于x行y列的 宫格标记为（x, y）o（二） 给宫排序按照从左到右，从上到下的顺序，对9个宫排序，分别记为 1、2、3、4、5、6、7、8、9 宫988665837859783992533628a(T点为相同数字时，此数字即该宫格的解，则该宫格为 顾氏不动点这里完全互补是指，位于同一行或者同一列或者同 一宫的几个宫格中，几种可能之和即为该事件的全部 可能，即对该事件而言，这几种概率之和为1，这是 解出顾氏不动点的充要条件四）顾氏不动点相容性一般而言，在用直观法解出部分宫格之后，经常能 找到两种完全互补可能的宫格在寻找顾氏不动点时， 当已经选择两种完全互补的可能之后，发现其中一条 逻辑路径出现两个矛盾的分支时，选择与另一条逻辑 路径相容的分支继续进行即可，此时与另一条逻辑路 径的交点出现相同数字时，都是顾氏不动点。
此即 顾氏不动点理论定理A，准确表述如下：在寻找顾氏 不动点时，从两条完全互补的逻辑路径出发，当其中 一条路径出现矛盾的两个分支之后，应当选择与另外 条逻辑路径相容的分支继 n续进行，此时与另外一条逻辑 路径的交点宫格出现相同的 数字时，这些交点宫格及其上 的相同数字就都是顾氏不动 点 II tf£:JtfatJ（五）应用范围说明t ::叟1. 使用顾氏不动点解法解数独题之前，应尽可 能的用其他方法解题，直到其他方法无法继续 时，再用顾氏不动点解法，这样可以提高解题效 率2. 如果找到一个顾氏不动点后仍不能用其它 方法解开此题，应继续寻找更多的顾氏不动点， 直到解开此题为止3. 随意选择某一完全互补的两种可能，并不一 定得到顾氏不动点，得不到顾氏不动点时为无效 选择，此时应再考虑别的完全互补的的可能，持 续这种选择就一定能找到至少一个顾氏不动点， 能找到顾氏不动点的选择称为有效选择4. 对于任一数独题来说，选择不同的起点，可 能找到不同的顾氏不动点，可能只需要部分不动 点即可完全解开该题5. 广义的顾氏不动点解法同样有效，选择两种 完全互补的可能，分别进行逻辑推理，得出两条 逻辑路径A和B当这两条逻辑路径在某几个宫 格出现同样的数组时，则出现相同数字的那几个 宫格称为顾氏不动点区域。
2826g583889639653=eq&359J1)选择逻辑路径起点，令（4, 2）=2,可得（5,=1四•顾氏不动点解法例题例1：如图2所示，解：本题用直观法解不出任何宫格如图3所示标出每个空白宫格的候选数，开始找顾氏 不动点，解法如下：1.⑥ 由(2, 4)=3,可 得(6, 5)=3;⑦ 由(6, 5 ) =3, (6, 7 ) = 7,可得(6, 2 ) = 2;⑧ 由(6, 2)=2,可 得(5, 1)=1（T67图总寻找颐氏不渤点的逻辑路牲II:I①由(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;选择另一逻辑路径起点，令（4, 2）=7;-2591 i:f44■17 9■ 28a61 35574 589234 568 95280 4 b—Jrr1/■ ■ —JT ■ 1/^ ■ IJF * I ■ I r —Jr ― —/T ■ —Jp. r- —Jf— r —Jf 护 —Jr r- r —Jr ■ irfrF—Jr r —dr -r —Jf 存 I ■ I ■ Ir'Ir3. 到目前为止，按照顾氏不动 点解法得到了顾氏不动点（5, 1） =14. 下面可用直观法来解出本 题了，结果如图4所示。
① 由（5, 1）=1,可得（1, 3）975284436796疥:庄3942548633 5 67518 21 9 7, ■ , ■2 8 9窗"满验的禅=1；② 由（5, 1）=1,第6宫中1只能在第8列，可③由(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•5⑩得(6,8)=1,得(4, 8)=5;?由(4,3)=9,得,(5, 3)=3•5得(9, 7)=1;54 9 3 5 8 2 6[1] 同济大学数学教研室主编，《概率论》，出版社，1982年第1版[2] 康小虎，“论九宫图与古代计算法的关系”，《延 安教育学院报》，2001年第4期，第52 - 55页。
[3] 李林森，“奥妙无穷的古题”,《科技潮》，1998 年第5期，第86 - 87页£JfaJ?由(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,2)=5,(7,9)=2,(9,9)=5参考文献高等教育5l:叟。