数独

山色空蒙

数独

数独是源自18世纪瑞士的一种数学游戏，是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

这种游戏只需要逻辑思维能力，与数字运算无关。虽然玩法简单，但提供的数字却千变万化，所以不少人认为数独是锻炼脑筋的好方法。

                               
登录/注册后可看大图

山色空蒙

1、历史发展
起源
既然“数独”有一个字是“数”，人们也往往会联想到数学，那就不妨从大家都知道的数学家欧拉说起，但凡想了解数独历史的玩家在网络、书籍中搜索时，共同会提到的就是欧拉的“拉丁方块（Latin square）”。

拉丁方块的规则：每一行（Row）、每一列（Column）均含1-N（N即盘面的规格），不重复。这与前面提到的标准数独非常相似，但少了一个宫的规则。

近代发展
数独起源于18世纪初瑞士数学家欧拉等人研究的拉丁方阵（Latin Square）。19世纪80年代，一位美国的退休建筑师格昂斯（Howard Garns）根据这种拉丁方阵发明了一种填数趣味游戏，这就是数独的雏形。20世纪70年代，人们在美国纽约的一本益智杂志《Math Puzzles and Logic Problems》上发现了这个游戏，当时被称为填数字（Number Place），这也是目前公认的数独最早的见报版本。1984年一位日本学者将其介绍到了日本，发表在Nikoli公司的一本游戏杂志上，当时起名为“数字は独身に限る”（すうじはどくしんにかぎる），就改名为“数独”（すうどく），其中“数”（すう）是数字的意思，“独”（どく）是唯一的意思。后来一位前任香港高等法院的新西兰籍法官高乐德（Wayne Gould）在1997年3月到日本东京旅游时，无意中发现了。他首先在英国的《泰晤士报》上发表，不久其他报纸也发表，很快便风靡全英国，之后他用了6年时间编写了电脑程序，并将它放在网站上（这个网站也就是著名的数独玩家论坛），后来因一些原因，网站被关闭，幸好数独大师Glenn Fowler恢复了数据，玩家论坛有了新处所。在90年代国内就有部分的益智类书籍开始刊登，南海出版社在2005年出版了《数独1-2》，随后日本著名数独制题人西尾彻也的《数独挑战》也由辽宁教育出版社出版。《北京晚报》、《扬子晚报》、《羊城晚报》、《新民晚报》、《成都商报》等等报纸媒体也先后刊登了数独游戏。

山色空蒙

2、组成元素编辑

方格

水平方向有九横行，垂直方向有九纵列的矩形，画分八十一个小正方形，称为九宫格（Grid），如图一所示，是数独（Sudoku）的作用范围。[1]

                               
登录/注册后可看大图

数独元素 - 九宫格

行

水平方向的每一横行有九格，每一横行称为行（Row），如图二所示。

                               
登录/注册后可看大图

数独元素 - 单元

列

垂直方向的每一纵列有九格，每一纵列称为列（Column），如图三所示。

                               
登录/注册后可看大图

数独元素 - 列

宫

三行与三列相交之处有九格，每一单元称为小九宫（Box、Block），简称宫，如图四所示（在杀手数独中，宫往往用单词Nonet表示）。

                               
登录/注册后可看大图

数独元素 - 宫

组成

上述行、列、宫、单元格统称为单元（Unit）；而行、列、宫统称为区域（Region）。

区块

由三个连续宫组成大行列（Chute），分大行（Floor）及大列（Tower）。

第一大行：由第一宫、第二宫、第三宫组成。

第二大行：由第四宫、第五宫、第六宫组成。

第三大行：由第七宫、第八宫、第九宫组成。

第一大列：由第一宫、第四宫、第七宫组成。

第二大列：由第二宫、第五宫、第八宫组成。

第三大列：由第三宫、第六宫、第九宫组成。

格位编号

格位按所处的行列单元赋予坐标值，如图五所示。

                               
登录/注册后可看大图

数独元素 - 格位

坐标有多种标示法，有横行 A~I，纵列 1~9（如中国），也有横行 1~9，纵列 A~I（如日本），这两种标示容易混淆，故最被广泛使用的是横行R1~R9，纵列C1~C9的标示法。

提示数

在九宫格的格位填上一些数字，做为填数判断的线索（Hint），称为提示数（Clue），如图六所示。

                               
登录/注册后可看大图

数独元素 - 提示数

山色空蒙

3、解题手法编辑

依解题填制的过程可区分为直观法与候选数法。

直观法就是不做任何记号，直接从数独的盘势观察线索，推论答案的方法。

候选数法就是删减等位群格位已出现的数字，将剩余可填数字填入空格做为解题线索的参考，可填数字称为候选数(Candidates，或称备选数)。

直观法和候选数法只是填制时候是否有注记的区别，依照个人习惯而定，并非鉴定题目难度或技巧难度的标准，无论是难题或是简单题都可上述方法填制，一般程序解题以候选数法较多。

4、基础解法编辑

排除法（摒除法）

摒除法：用数字去找单元内唯一可填空格，称为摒除法，数字可填唯一空格称为排除法 (Hidden Single)。

根据不同的作用范围，摒余解可分为下述三种：

数字可填唯一空格在「宫」单元称为宫排除（Hidden Single in Box），也称宫摒除法。

数字可填唯一空格在「行」单元称为行排除法（Hidden Single in Row），也称行摒除法。

数字可填唯一空格在「列」单元称为列排除法（Hidden Single in Column），也称列摒除法。

唯一余数法

                               
登录/注册后可看大图

Peer等位群格位唯一余数法：用格位去找唯一可填数字，称为余数法，格位唯一可填数字称为唯余解（Naked Single）。

余数法是删减等位群格位（Peer）已出现的数字的方法，每一格位的等位群格位有 20 个，如图七所示。

山色空蒙

5、进阶解法编辑

上述方法称为基础解法（Basic Techniques），其他所有的解法称为进阶解法（Advanced Techniques），是在补基本解法之不足，所以又称辅助解法。

进阶解法包括：区块摒除法（Locked Candidates）、数组（Subset/Tuple）、二链列（X-Wing）、唯一矩形（Unique Rectangle）、全双值格致死解法（Bivalue Universal Grave）、同数链（X-Chain）、异数链（Multidigit Chain）及其他数链的高级技巧等等。已发展出来的方法有近百种之多。

其中前三种加上基础解法为一般数独书中介绍并使用的方法，同时也是大部分人可以理解并掌握的数独解题技法。

通过基础解法出数只需一种解法，摒除法或唯余法，超出此范围而需要施加进阶解法时，解题点需要进阶解法协助基础解法来满足隐性唯一或显性唯一才能出数，该解题点的解法需要多个步骤协力完成，因此称做组合解法。

解题必须以逻辑为依归，提倡数独的本意。

区块摒除法

区块摒除法包括宫区块摒除法（Pointing）与行列区块摒除法（Claiming）。

在基础题里，利用区块摒除可以替代一些基础解法的观察，或辅助基础解法寻找焦点。

在非基础题里，区块可以隐藏任何其他结构，简单的可以把基础解法隐藏起来，难的可以隐藏数对等等其他进阶技巧。

例如：

                               
登录/注册后可看大图

区块摒除法

首先数字6对第五宫摒除，得到第五宫的6在R4C5或者R6C5。

不论是在R4C5或者R6C5，C5的其他格都不能再有数字6。（R4C5与R6C5就是数字6的区块，这也是区块摒除作用的观点）

数字6对第二宫摒除，得解R1C4=6。

山色空蒙

数对法

当一个单元（行、列、宫）的某两个数字仅可能在某两格时，我们称这两个格为这两个数的数对（Pairs）。

数对出现在宫称为宫数对；数对出现在行列成为行列数对。

用候选数法的观点去看，数对有两种，一种是在同单元内其中两格有相同的双候选数，一看就明白，因此称为显性数对（Naked Pair），另一种是，同单元内有两个候选数占用了相同的两格，该两格因为还有其它候选数很难辨认，因此称为隐性数对（Hidden Pair）。[2]

                               
登录/注册后可看大图

合并图册(2)例子：

左图：数字2与7同时对第一宫摒除，得到这两个数字均只可能在r2c2与r3c2这两个位置，我们称r2c2与r3c2是27数对。

右图：数字8对第一宫摒除，得到摒余解r1c3=8。

6、难度划分编辑

影响数独难度的因素很多，就题目本身而言，包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。对于玩家而言，了解的技巧数量、熟练程度、观察力自然也影响对一道题的难度判断。市面上数独刊物良莠不齐，在书籍、报纸、杂志中所列的难度或者大众解题时间纯属参考，常有难度错置的情况出现，所以不必特别在意。网络上有很多数独难度的分析软件，比较著名的是 Nicolas Juillerat 开发的Sudoku Explainer和 Bernhard Hobiger 开发的Hodoku，它们都是免费的软件。因为每种软件的都有不同的解题策略，所以也只能作为难度的大致界定，无法真正的解析出难度的内涵。

如果一道题目的提示数少，那么题目就会相对难，提示数多则会简单，这是一般人判断难易的思维模式，但数独谜题提示数的多寡与难易并无绝对关系，多提示数比少提示数难的情况屡见不鲜，同时也存在增加提示数之后题目反而变难的情形，即使是相同提示数（甚或相同谜题图形）也可以变化出各式各样的难度。提示数少对于出题的困难度则有比较直接的关系，以20-35提示数而言，每少一个提示数，其出题难度会增加数倍，在制作谜题时，提示数在22以下就非常困难，所以常见的数独题其提示数在23~30之间，其原因在于制作比较不困难，可以设计出比较漂亮的图形（Pattern），另外这个提示数范围的谜题变化多端是一个重要因素。

山色空蒙

7、终盘数量编辑

数独中的数字排列千变万化，那么究竟有多少种终盘的数字组合呢？

6,670,903,752,021,072,936,960（约为6.67×10的21次方）种组合，2005年由Bertram Felgenhauer和Frazer Jarvis计算出该数字，并将计算方法发布在他们网站上，如果将等价终盘（如旋转、翻转、行行对换，数字对换等变形）不计算，则有5,472,730,538个组合。数独终盘的组合数量都如此惊人，那么数独题目数量就更加不计其数了，因为每个数独终盘又可以制作出无数道合格的数独题目。

8、标准数独编辑

目前（截止2011年）发现的最少提示数9×9标准数独为17个提示，截止2011年11月24日16:14，共发现了非等价17提示数谜题49151题，此数量仍在缓慢上升中，如果你先发现了17提示数的题目，可以上传至“17格数独验证”网站，当然你也可以在这里下载这49151题。

关于是否有16提示数的合格题目，网络上也争论很久，有发现16提示数双解的，但是仍未发现唯一解。国外有网友给出了关于为什么至少需要17提示的证明，受到了大家的质疑，比如9×9对角线数独（在标准数独规则基础上，两条大对角线的数字不重复）的最小提示数为12，按照他的理论则需要更多的提示数。

另外在2006年Gary McGuire撰写了程式，试图通过暴力法来证明16提示数的数独是否存在，方法很简单，既然Bertram Felgenhauer和Frazer Jarvis已经计算出不等价的终盘总数为5,472,730,538个，那么将每个终盘是16提示的情况都跑一遍，如果没有找到16提示的数独，那么就可以证明最少提示数为17个。但因为是暴力方法，对于一台单核的电脑来说需要跑30万年才能跑出结果。台湾的吴毅成教授和他的团队将Gary McGuire的程式加以改进，使得效率大幅提升，大约2417年即可完成演算。并放在BOINC（伯克利开放式网络计算平台）上让世界加入BOINC的电脑一同演算，令人欣喜的是，截至编辑2012年4月18日已经完成了51.73%。

Gary McGuire的团队在2009年设计了新的算法，利用致命结构的思路，花费710万小时CPU时间后，于2012年1月1日提出了9×9标准数独不存在16提示唯一解的证明，继而说明最少需要17个提示数。并将他们的论文以及源代码更新在2009年的页面上。

山色空蒙

9、变形数独编辑

数独到如今发展，出现了越来越多的变形（Variants），按照规则划分则成百上千，各国的数独爱好者也不断制作出新的变形。

一般意义上，按照最为基础的数独规则，一般称为标准数独（Standard Sudoku）。而产生的解题思路和技巧，也称为标准数独技巧。

下面列出最常见的几种变形：

对角线数独

对角线数独（Diagonal Sudoku、Sudoku-X）：

在标准数独规则基础上，两条大对角线的数字不重复。

                               
登录/注册后可看大图

对角线数独

迷你数独

迷你数独（Mini Sudoku）：

每个谜题都由一个在不同位置给与提示数字的4x4或6x6网格组成。游戏的目的是将空方格填上数字1到4（对于4x4大小的谜题）或者1到6（对于6x6的谜题），使得每一行，每一列以及每一个宫都没有重复的数字出现。

                               
登录/注册后可看大图

                               
登录/注册后可看大图

山色空蒙

锯齿数独

锯齿数独（Jigsaw Sudoku）：

相对标准数独而言，宫变成了不规则的。玩家需在对应的锯齿方框内填入不重复的九个数或N个数，并保证横纵也不重复。

                               
登录/注册后可看大图

连体数独

连体数独（Multi Sudoku）：

每个谜题都由俩个或者更多的数独网格重叠组成，该网格可能是标准数独谜题也可能是混合类型的数独谜题，这些网格都有一个或多个宫重叠。游戏的目的是通过其规则将每个网格均解出。温馨提示，重叠的区域必须同时满足其所在网格的规则。

                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图