互动科普

你多半会以为没有几个人会对逻辑游戏感兴趣——也许只有数学家、电脑狂、无可救药的赌徒这类人才会为之心动。然而，一种名叫“数独”(Sudoku)的逻辑游戏却在极短时间内风靡全球，令人不禁回想起20世纪80年代初鲁比克魔方（Rubik’s Cube）的狂热风潮。

与三维的魔方不同，数独是一种平面的方格游戏。数独通常有81个小方格（9行9列），分成9个九宫格，每个九宫格含有3×3共9个小方格。游戏开始时，某些小方格中已经填进了数字。玩家必须用从1到9的数字把所有空格填满，条件是任何一个数字不能在同一行、同一列或者同一个九宫格中出现两次。而且每道数独题的答案都是惟一的。

有趣的是，尽管数独是数字游戏，但玩这种游戏的人却无需具备什么数学知识。事实上，填满数独的所有格子，完全不用求助于任何运算（包括加法、乘法这样的基本运算），而且从理论上讲，我们也可以用其他任何九个不同的符号来填，例如字母、颜色、图案等等都可以。然而，这个似乎与数学无关的数独游戏，却暗藏了许多数学家和计算机专家感到棘手的难题。

数独的来历

数独的起源并不神秘。许多人以为数独的祖先是幻方，但事实并非如此。（幻方和数独一样，也是在一个由若干行若干列小方格组成的阵列中填入整数数字，但它要求各行各列以及对角线上的数字加起来相等。）其实，除了都是在方格中填入数字以外，数独跟幻方可以说风马牛不相及，但它同拉丁方格（简称拉丁方）却有千丝万缕的联系(参见下一页的表格)。

n阶拉丁方是一个每边各有n个方格的正方形矩阵，共有n2个方格。用n种符号填进方格，要求同一种符号在同一行同一列中不能重复出现（因此每一种符号都不多不少，正好用n次）。这类方阵的起源可以追溯到中世纪；后来，瑞士数学家莱昂哈德·欧拉（Leonhard Euler，1707年－1783年）将它们命名为拉丁方，并对它们进行了详细研究。

标准的数独游戏与九阶拉丁方有异曲同工之妙，两者的区别仅在于数独还有一条要求：每个九宫格中必须有从1到9的9个数字。第一种数独游戏出现在1979年5月出版的《戴尔纸笔游戏及纵横字谜》（Dell Pencil Puzzles and Word Games）中；《纽约时报》纵横字谜专栏编辑威尔·肖茨（Will Shortz）经过考证后发现，数独好像是由一位名叫霍华德·加恩斯（Howard Garns）的退休建筑师发明的。加恩斯已于1989年（也可能是1981年，说法不一）在美国印第安纳波利斯去世了，过早离世使他未能看到自己的发明在全球大行其道，实为憾事。

戴尔最初推出这项游戏时，称它为“数位”（Number Place）。1984年，日本一家杂志介绍了这个游戏，并最终把它命名为“数独”（Sudoku，日文为すうどく）按字面大意就是“单独的数字”。杂志为这个名称申请了注册商标，因此日本那些抄袭者为免惹上侵权官司，仍然沿用“数位”的提法。于是一个有意思的现象出现了：日本人用数独的英文名字来称呼这个游戏，而讲英语的人却用数独的日文名字来称呼它。

数独后来的迅速走红，主要归功于一位名叫韦恩·古尔德（Wayne Gould）的退休法官。古尔德现在定居在新西兰，1997年，他到日本旅游时，无意中发现这个游戏，并编写了一个计算机程序来自动生成完整的数独方阵。2004年年底，伦敦《时报》在古尔德的建议下开辟了数独专栏，《每日电讯报》紧随其后，在2005年1月登出了数独。后来，世界各国数十家日报相继开辟专栏来介绍数独，有的甚至把它摆在头版大事炒作、招徕读者。专门介绍这种娱乐的杂志和一本又一本的书籍如雨后春笋般涌现，相关的比赛、网站和博客等等，也接二连三地冒出来。

有多少人就有多少种数独？

很快，数学家就开始研究有多少种数独游戏。数独面世之后，他们马上就提出了这样一个问题：只有惟一解的数独方阵（即只能用一种方式填满的数独方阵）有多少种？显然，这个问题的答案必定小于拉丁方的数目，因为数独游戏还要受到九宫格中必须填入9个不同数字的条件限制。

三阶拉丁方只有12种，四阶拉丁方有576种，而九阶拉丁方则有5,524,751,496,156,892,842,531,225,600种之多。但群论（也就是有关对称的数学）认为，一个拉丁方如果能从另一个拉丁方中衍生而来，那么这两个拉丁方就是等价的。例如，统一把每个数都替换成另一个数（比如把所有1都换成2，所有2都变成7，所有7又改成其他某个数等等），或者交换两行或两列，那么最终结果在实质上应该是一样的。假如我们把所有等价的拉丁方都只算作一种，那么九阶拉丁方的总数就有377,597,570,964,258,816种。这个结果是当时还在美国俄亥俄州立大学的斯坦利·E·巴梅尔（Stanley E.Bammel）与杰罗姆·罗思坦因（Jerome Rothstein）1975年在《离散数学》杂志上公布的。

到底有多少种数独方阵？确定数独方阵的总数始终是个相当棘手的问题。只有通过运用逻辑推理来简化问题，并利用计算机系统地考察了各种可能之后，我们才得以估算出有效数独方阵的总数：6,670,903,752,021,072,936,960种。这个结果包含了通过基本变换从某一数独方阵中衍生出来的所有方阵，是由德国德累斯顿理工大学的贝尔特拉姆·费尔根豪尔（Bertram Felgenhauer）和英国谢菲尔德大学的弗雷泽·贾维斯(Frazer Jarvis)得出的，到现在它已经通过了好几次验证（用这种方式获得的结果，验证是必不可少的）。

如果所有等价的数独方阵只算一种，那么数独方阵的总数就减少为5,472,730,538种，比地球的人口总数稍小一点。虽然总数大为缩水，但数独迷根本无须担心找不到足够多的难题来过瘾。即使你能每分钟攻下一道题，即使做到一百岁，解决的数独题充其量也只有总数的区区百分之一。

应当指出，从起始方阵（或提示方格）出发，到填出一个完整的数独方阵，途径可能不只一条（在某一给定的完整方阵中删去一部分数字，得出的就是等待我们征服的数独游戏，也就是这里说的起始方阵）。至今还没人能够确定究竟有多少种不同的起始方阵，而且一个起始方阵究竟是不是最小方阵，只有数学家才会感兴趣。（所谓最小方阵就是不能变得更小的方阵，也就是说，如果从这个方阵中取出一个数，那它的解就不再惟一。）现在还没人求出最小方阵的总数。算出这个数字，就等于知道了究竟有多少种不同的数独游戏。近期内，肯定有人会来啃这块硬骨头。

另一个小问题也还没有被攻克——一个起始方阵中最少可填进多少数，仍能保证它有惟一解？这个问题的答案似乎是17。澳大利亚大学的戈登·罗伊尔（Gordon Royle）已经收集了超过3.8万个符合这一指标，而且不能通过诸如交换行列之类的简单操作互相转换的数独实例。

爱尔兰国立梅努斯大学的加里·麦圭尔(Gary McGuire），针对有16个提示数字的数独方阵展开拉网式排查，试图从中找出只有一个解的方阵，结果一无所获。看来这样的数独似乎并不存在。而另一方面，罗伊尔和其他一些研究人员彼此独立地发现了一个有16个提示数字的数独，它只有两个解。但这样的例子至今仍只此一个，再没有发现其他的。

会不会很快就有人证实不存在只有16个提示数字的数独呢？麦圭尔的回答是否定的。他指出：“如果我们能够以每秒一个的速度分析数独方阵，那么用173年时间就能搜索完所有数独方阵。遗憾的是，现在我们还无法做到，即便用高速计算机也不行。”他又说，或许不久之后，在一台功能强大的计算机上可以达到平均每分钟搜索一个方阵的速度，但以这样的速度完成全部搜索仍需要10,380年。“即使把搜索工作分配给一万台计算机，也需要一年左右。我们对数独的认识的确需要有根本突破，才能使搜索所有数独方阵的工作变得可行。要么就缩小搜索范围，要么就找到一种快得多的搜索算法”。

把上面讨论的最少提示数字的问题反过来，就成了最大提示数字问题：不能保证数独方阵有惟一解的提示数字最多是多少？数学家已经知道答案：77。显而易见，有80、79或78个提示数字的数独方阵，如果有解，就必定是惟一的解。但是有77个提示数字的方阵，就不能肯定它的解是否惟一 (见66页下方的图表)。

电脑战数独

除了“有多少”这种问题以外，数学家也非常热衷考虑计算机能为数独的求解和生成做点什么，又有哪些事是计算机无能为力的。针对标准的9×9数独，编写能够找出所有有效方阵的计算机程序还比较容易。

求解程序可以采用几种方法，最常用的是回溯法，即通过反复尝试，逐渐摸索出最终答案的一种系统搜索方法。它首先提出一个初步的解，然后通过尝试来逐步完善，一旦发现有错，就稍加改动再作尝试。

基本的回溯跟踪算法是这样操作的：首先在第一个空格中填入数字1；如果这个数字同已有的提示数字不矛盾，那么程序就进行到第二个空格，在这个空格中也填入数字1。如果遇到冲突（这种情况往往很快就会发生），程序就抹掉刚刚填入的数字1改填2，如果2不行，继续改，以此类推，直到填入一个与已有数字不冲突的数字为止。然后程序立刻转到下一个空格，而且仍然从1开始尝试。

如果程序进行到某一空格，发现它尝试填入的数字一直增大到9还是不行，那么，根据标准数独的规则，它已经不可能填入更大的数字。这时程序就退回到前一格中，把数字（即它填入的倒数第二个数字）加1。而后继续推进，直到发现矛盾（有时程序会退回好几次后，才能又向前移动）。一个精心编写的程序，将通过尝试法对所有可能进行一个不漏的地毯式搜索。如果数独有解，程序找到这个解就算大功告成了。如果数独有多个解（一个存在漏洞的数独就可能出现这种情况），那么程序将把所有解一一挖出来。

当然，我们可以对上述最基本的搜索方法作种种改进，以便更快找出数独的惟一解。“约束传播法”（constraint propagation）是大受青睐的改进技巧之一：每填入一个新数字，程序便自动生成一张表，显示出还剩下哪些数字可以填入空格中。以后填数字时，它就只能选择该表中的数字。

回溯法可以用相当简短的求解程序来实现。实际上，人们已经用Prolog语言编写了非常简洁的数独求解程序。Prolog是法国马赛大学的阿兰·柯麦劳（Alain Colmerauer）和菲利普·罗素（Philippe Roussel）在上世纪70年代后期开发的计算机语言，它包含了一种回溯算法。

对数独玩家而言，计算机程序所采用的回溯算法是不实用的，因为这样一个一个地反复尝试，需要非凡的耐心。玩家们往往是八仙过海、各显神通，采用种种更巧妙的方法来应战。反复尝试，这种靠蛮力的笨办法只是迫不得已才使用。有些程序也在一定程度上模仿了人的技巧：这类程序比其他的更长，但效率并不落于人后。模拟人类推理方法的程序，也可以用来评估数独的难度（可以把数独分成若干难度等级，最容易的只须用到一些简单的技巧就可以完成，最难的则是令人望而生畏的“魔鬼题”，需要运用极费脑筋的逻辑规则才能解决）。

在考虑如何解决数独时，计算机专家常用的思路之一，就是把它与图形着色问题（graph-coloring problem）等同起来，也就是要求相邻的两个方格（用图论术语就是“用一条边连接起来的两个顶点”）不能涂上同一种颜色，而且可用的颜色只有9种。实际上，这个问题非常复杂，因为每个9×9方阵转化为图形后都有几百条边。每个空格都是含有其他8格的一行的一部分，也是含有其他8格的一列的一部分，还是含有其他8格的九宫格的一部分（这个九宫格中已经有4个空格算在上面提到的行或列中了）。因此，81个空格中的每一个都间接地跟其他的20（8＋8＋4）个空格连接在一起，总计为1,620个空格，而1,620个空格中，每一个都与相邻的空格共有一条边，这又意味着边的总数为810（1620÷2）条。

数独可以转化为着色问题，这对科学家而言具有重大意义，因为它把数独跟一类重要的数学问题联系起来了。特别值得一提的是，日本东京大学的八登崇之（Takayuki Yato）和濑田刚广（Takahiro Seta）不久前证明数独属于NP完全问题（NP-complete problem）。这类问题多半不能在合理时间内解答。三色问题就是众所周知的NP完全问题之一——它要求我们证明，能否用三种颜色给一个图内的所有顶点着色，使每条边所连接的两个顶点的颜色均不相同。对数独而言，如果我们把传统的32×32（9×9）数独方阵推广到一般形式的n2×n2方阵（其中n为任意正整数），那么要编写一种高效的程序，试图求出n为任意值的数独游戏的解，看来是一项不可能完成的任务。任何一个程序都不可能高效解决所有的数独问题，因为随着n的增大，求解所需的时间将以令人瞠目的速度疯长。

如果你有一种解决数独问题的算法，那么你可以以此为基础，编写算法来设计数独。实际上，早期的数独游戏是人想出来的，而如今几乎所有数独，都是根据下面的方法，或者其他类似的方法，用计算机程序生成的。把若干数字随机地摆放在一个数独空格内，然后对这个起始方阵应用求解程序（例如回溯程序）。如果它有惟一解，程序在找到这个惟一解后就停止运行。如果起始方阵无解，那么程序就从中拿掉一个数字，继续运行。如果有若干不同的解，那么程序就选择其中一个，然后逐步向起始方阵添加数字，直到这个被选中的解成为惟一解。

玩家取胜之道

喜欢自己动手同数独较量的玩家，有很多招数可以选择，不过一开始最好依靠两条基本技巧来应战：第一条是寻找那些约束条件最多的空格，也就是在已经被填得相当满的行列或九宫格中寻找。在某些情况下，排除不可能填入的数字（已经占据了同一行列或九宫格中其他空格的数字），你将会发现可以填入选定空格的数字只有一个，因此无须犹豫，赶快把它填进去。无论如何，用这种方法应该会大大缩小可选范围。

第二条技巧，就是寻找一个特定数字在某一行、列或九宫格中可以摆放的位置（例如寻找“3”这个数字在第四行中能放进哪些空格）。有时你会发现这样的空格只有一个；有时不止一个，但知道“3”只能放在某两个或三个空格中，对最终解决也大有帮助(具体细节参看64页和65页的图表)。此外，读者还可以在“拓展阅读”列出的网站中，找到许多同数独斗智的秘诀，其中一些被冠以“箭鱼”或“金链”之类富有创意的名称。

许多软件程序可以生成具有指定难度的数独题，并帮助你找出答案（当然不会越俎代庖替你完成），你只要上网便能轻而易举找到这些程序。有的可以让你在空格中随意加入临时性的记号，不用时可以擦去，这就省去了纸笔之类的工具；有的甚至可以让你把各个方格联系起来。不要小看了这些程序，它们让你摆脱了擦写之类的繁琐操作，有助于真正体会数独这种逻辑游戏那妙不可言的复杂和别具魅力的精巧。

如果你有一天厌倦了传统数独，不妨看看花样繁多的变形数独。这些另类数独同样可以让你大呼过瘾。其中有的把标准数独方阵重叠起来，有的用其他种种图形来代替方阵，还有的加上了更多约束条件。形形色色的另类数独，激励你去探索新的逻辑对策，它们同样让人无法自拔。此外，道行颇深的数独高手或许只需要一时半刻就可以降伏传统数独，但当他们遇到大量的另类数独，说不定就会整天沉浸在空格与数字反复组合的无尽乐趣之中。好了，还啰嗦什么，赶快动手解决你的下一个数独难题吧！