九宫格数独

九宫格数独 【摘要】 九宫格数独，是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数字谜题。这种游戏全面考验做题者观察能力和推理能力，是训练头脑的绝佳方式。于是，笔者想探究解决这种数字谜题的方法。

数独的历史 数独前身为“九宫格”，最早起源于中国。数千年前，我们的祖先就发明了洛书，其特点较之现在的数独更为复杂，要求纵向、横向、斜向上的三个数字之和等于15，而非简单的九个数字不能重复。中国古籍《易经》中的“九宫图”也源于此，故称“洛书九宫图”。而“九宫”之名也因《易经》在中华文化发展史上的重要地位而保存、沿用至今。 1783年，瑞士数学家莱昂哈德·欧拉发明了一种当时称作“拉丁方块”（Latin Square）的游戏，这个游戏是一个n×n的数字方阵，每一行和每一列都是由不重复的n个数字或者字母组成的。 19世纪70年代，美国的一家数学逻辑游戏杂志《戴尔铅笔字谜和词语游戏》（Dell Puzzle Mαgαzines）开始刊登现在称为“数独”的这种游戏，当时人们称之为“数字拼图”（Number Place），在这个时候，9×9的81格数字游戏才开始成型。 1984年4月，在日本游戏杂志《字谜通讯Nikoil》（《パズル通信ニコリ》）上出现了“数独”游戏，提出了“独立的数字”的概念，意思就是“这个数字只能出现一次”或者“这个数字必须是惟一的”，并将这个游戏命名为“数独”（sudoku）。 一位前任香港高等法院的新西兰籍法官高乐德（Wayne Gould）在1997年3月到日本东京旅游时，无意中发现了。他首先在英国的《泰晤士报》上发表，不久其他报纸也发表，很快便风靡全英国，之后他用了6年时间编写了电脑程式，并将它放在网站上，使这个游戏很快在全世界流行。从此，这个游戏开始风靡全球。后来更因数独的流行衍生了许多类似的数学智力拼图游戏，例如：数和、杀手数独。 中国大陆是在2007年2月28日正式引入数独. 2007年2月28日，北京晚报智力休闲数独俱乐部(数独联盟sudokufederation前身)在新闻大厦举行加入世界谜题联合会的颁证仪式，会上谜题联合会秘书长皮特-里米斯特和俱乐部会长在证书上签字，这标志着北京晚报智力休闲俱乐部成为世界谜题联合会的39个成员之一，这也标志着俱乐部走向国际舞台，它将给数独爱好者带来更多与世界数独爱好者们交流的机会。 数独的基本结构与规则 元素构成： 单元格：数独中最小的单元，标准数独中共有81个； 行：横向9个单元格的集合； 列：纵向9个单元格的集合； 宫：粗黑线划分的区域，标准数独中为3×3的9个单元格的集合； 已知数：数独初始盘面给出的数字； 候选数：每个空单元格中可以填入的数字。 规则：

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

基本解法举例 数独解法全是由规则衍生出来的，基本解法分为两类思路，一类为排除法，一类为唯一法。更复杂的解法，最终也会归结到这两大类中。 以下为查找到的一些基本解法：

基础摒除法 基础摒除法就是利用1 ～ 9 的数字在每一行、每一列、每一宫都只能出现一次的规则进行解题的方法。基础摒除法可以分为行摒除、列摒除、九宫格摒除。 实际寻找解的过程为： 寻找九宫格摒除解：找到了某数在某一个九宫格可填入的位置只余一个的情形；意即找到了 该数在该九宫格中的填入位置。 寻找列摒除解：找到了某数在某列可填入的位置只余一个的情形；意即找到了该数在该列中的填入位置。 寻找行摒除解：找到了某数在某行可填入的位置只余一个的情形；意即找到了该数在该行中的填入位置。 基础摒除法的提升方法是区块摒除法,是直观法中使用频率最高的方法之一.

唯一解法 当某行已填数字的宫格达到8个,那么该行剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为行唯一解. 当某列已填数字的宫格达到8个,那么该列剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为列唯一解. 当某九宫格已填数字的宫格达到8个,那么该九宫格剩余宫格能填的数字就只剩下那个还没出现过的数字了。成为九宫格唯一解.

唯余解法 唯余解法就是某宫格可以添入的数已经排除了8个,那么这个宫格的数字就只能添入那个没有出现的数字.

区块摒除法 区块摒除法是基础摒除法的提升方法,是直观法中使用频率最高的方法之一. 余数测试法 所谓余数测试法就是在某行或列,九宫格所填数字比较多,剩余2个或3个时,在剩余宫格添入值进行测试的解题方法.

隐性唯一候选数法 当某个数字在某一列各宫格的候选数中只出现一次时，那么这个数字就是这一列的唯一候选数了．这个宫格的值就可以确定为该数字． 这是因为，按照数独游戏的规则要求每一列都应该包含数字1～9，而其它宫格的候选数都不含有该数，则该数不可能出现在其它的宫格，那么就只能出现在这个宫格了． 对于唯一候选数出现行,九宫格的情况，处理方法完全相同。

三链数删减法 找出某一列、某一行或某一个九宫格中的某三个宫格候选数中，相异的数字不超过3个的情形， 进而将这3个数字自其它宫格的候选数中删减掉的方法就叫做三链数删减法。

矩形顶点删减法 矩形顶点删减法和直观法讲到的矩形摒除法分析方法是一样的。矩形顶点删减法在识别时比较不容易找到，所以最好先使用其它的方法。

三链列删减法 三链列删减法是矩形顶点删减法的扩展，如果不清楚矩形顶点删减法，可以参考矩形顶点删减法，以便于更容易理解本节内容。 利用“找出某个数字在某三列仅出现在相同三行的情形，进而将该数字自这三行其他宫格候选数中删减掉”； 或“找出某个数字在某三行仅出现在相同三列的情形，进而将该数字自这三列其他宫格候选数中删减掉”的方法 就叫做三链列删减法。 关键数删减法 在进入到解题后期，利用前面讲到的唯一候选数法、隐性唯一候选数法、 区块删减法、数对删减法、隐性数对删减法、 三链数删减法、隐性三链数删减法、矩形顶点删减法、 三链列删减法都无法有进展的时候，可以考虑使用关键数删减法。关键数删减法就是在后期找到一个数，这个数在行（或列，九宫格）仅出现两次的数字。我们假定这个数在其中一个宫格类，继续求解，如果发生错误，则确定我们的假设错误。如果继续求解仍然出现困难，不妨假设这个数在另外一个宫格，看能不能得到错误。这就是关键数删减法. 排除法 当某一列，某一行或某一宫里已填7个数字时，可采用排除法，排除不可能出现在这个格子的数，从而确定格子里应该填什么数。比如某一行已填1，3，4，5，7，8，9，还剩2，6，而其中一个空格所在的列上已有了2，可知这个空格里不可能是2，那么另外一个空格里一定是2，那么这个空格里一定是6。 当某一列，某一行或某一宫里已填6个数字时，也可采用排除法。

由于以上步骤过于繁琐，笔者想到利用计算机高速处理数据的能力来解决这个难题。笔者利用计算机 PASCAL 程序尝试解决问题，并最终能在1秒左右解决有唯一解的数独谜题。 以下是笔者编写的程序： type int=0..9; var a,b:array[0..9,1..9]of boolean; c:array[0..2,0..2,1..9]of boolean; s:array[0..9,0..9]of int;

procedure init; var i,j,t:-1..9; ch:char; begin fillchar(a,sizeof(a),true); fillchar(b,sizeof(b),true); fillchar(c,sizeof(c),true); i:=0; j:=-1; while i*9+j+1<81 do begin read(ch); if (ch>='0') and (ch<='9') then begin inc(j); if j>8 then begin j:=0; inc(i); end; s[i,j]:=ord(ch)-48; t:=s[i,j]; if t>0 then begin a[i,t]:=false; b[j,t]:=false; c[i div 3,j div 3,t]:=false; end; end; end; end;

procedure print; var i,j:int; begin for i:=0 to 8 do begin for j:=0 to 8 do begin write(s[i,j]); if (j=2) or (j=5) then write(' '); end; writeln; if (i=2) or (i=5) then writeln; end; halt; end;

procedure save(x,y,u,v,i:int); begin a[x,i]:=false; b[y,i]:=false; c[u,v,i]:=false; s[x,y]:=i; end;

procedure set_free(x,y,u,v,i:int); begin a[x,i]:=true; b[y,i]:=true; c[u,v,i]:=true; s[x,y]:=0; end;

procedure dfs(x,y:int); var u,v,i:int; begin if x>8 then print; if y>8 then begin dfs(x+1,0); exit; end; if s[x,y]=0 then begin u:=x div 3; v:=y div 3; for i:=1 to 9 do if a[x,i] and b[y,i] and c[u,v,i] then begin save(x,y,u,v,i); dfs(x,y+1); set_free(x,y,u,v,i); end; end else dfs(x,y+1); end;

begin init; dfs(0,0); write('No answer'); end.