嗑时间·数独(Sudoku)

提到数独(Sudoku),其实已经不怎么陌生了。这个小游戏相传起源于拉丁方阵(Latin Square),由18世纪瑞士数学家发明。1970年代在美国发展,改名为数字拼图(Number Place),之后流传至日本并发扬光大。 “数独”虽然名字带“数”,而本质上是无关算数的推理与逻辑。将9×9的方格分为九个区块,每个区块由3×3个小块组成,姑且称之为九宫格。顾名思义,数独要做的就是用1~9的数字填入空缺的格子里,并保证其在所属的行/列及九宫格里是独一无二的。常常我们会把数独标识成下面这种样子,方便进行判断:





























































































85  2   7
6 97 3825
  358    
   6   3 
5 28 79 4
 3   1   
    425  
9251 84 3
3   7  12

对于简单的数独题,或许我们凭简单的看、猜、试就可以完成;但对于有难度的,就要费些周折,往往做的最到后两三个才发现走错路了,前功尽弃。所有就需要掌握一些技巧了。 任何一个数独最终只有唯一解,而复杂的数独往往会存在若干条分支,为了尽快排除干扰,就要在初期尽可能多的减少变数,绝不猜测。下面一些方法可以确定已知的唯一解:


1、当某行/列或者九宫格里已填入8个数字,那么结果一定是剩下的那个数字了;(列举的这个题目里显然目前没有这样好的条件,不过到最后是一定用得上的)


 2、当某一行/列的3个九宫格里,有2个都存在某个数字,那么可由此确定剩下九宫格里该数字的位置;(如第中间的一排九宫格里,两边红色九宫格都有3,分别占去第4、6行;那么可以确定中间白色九宫格5E处必为3


3、当上述情况中所空的格子多于1个时,可综合三项条件排除假设来确定唯一值;(如第2行缺少1和4,但显然2E处填4会与E7冲突,于是确定2B为4、2E为1;同样第8行的67,左侧三个九宫格的9都是通过排除确定下的)





















ABCDEFGHI





















1
2
3
4
5
6
7
8
9




























































































85  2 3 7
649713825
  358    
 9 6   3 
5 28379 4
 3   1 5 
    425  
925168473
3   75 12

当然事事不会继续一帆风顺下去,因为某行/列或九宫格所缺的数字比较多,且没有足够条件得出确定值时,我们就要进行必要的猜测了。注意,要针对最少可能性的方格进行假设,这样能最快排除无效分支。 关于技巧就只说这些,讲多了会失去做数独的趣味了,同时 想要快速解出答案还是要靠自己慢慢摸索的。
------------------------------------------------------------------------

如果想快速知道一个数独的解,可以利用小程序找出答案。编程很容易,求解思路姑且叫做候选数法:选出每一个空白的格子里所有可能出现的数字,然后由分支最少的格子填起,每填一个便更新一下候选数字,逐渐删减候选数,最终获得唯一确定的候选数。这种方法逻辑清晰,不走弯路,但只有计算机愿意做这种不知疲倦的单调运算。

------------------------------------------------------------------------

收集了一些入门的数独题目,点击这里下载 可直接打印;更多的题目,推荐一个在线的数独网站: SUDOKU数独
或者也可以点击这里下载到你的电脑,该软件可以生成一百多道难度各异的数独题目。


特别推荐一款手机数独游戏Sensible Sudoku2 for UIQ3,点击这里下载(破解版,随便输入几个数字即可成功注册)。
------------------------------------------------------------------------


除此之外数独还有很多扩展的玩法,比如下面这种叫Killer Sudoke的数独,它真正将算术引进来了,但重点还是靠逻辑、推理。

更丰富的介绍参考这里:http://www.shes.hcc.edu.tw/~oddest/su302.htm

No comments:

Post a Comment