撰文╱狄拉贺（Jean-Paul Delahaye）翻译／翁秉仁

想解数独，不但用不到数学，甚至连算术都不需要。不过，这游戏倒是含蕴了几个有趣的数学问题。

数独的前身：数独的数盘是一种特殊的拉丁方阵。拉丁方阵的名称出自于18世纪的数学家欧拉，是一种含有n种符号的n × n方阵，其中每列或每行的ｎ种符号都不可重复出现（例如上图左）上图右则是一个完成的标准数独盘面(也称作终盘)，符合9 × 9拉丁方阵，所增加的额外限制条件是必须满足每一宫中，1到9的数不能重复出现。

大家可能认为，只有很少数的人如数学家、计算机怪胎、嗜赌之徒，会对逻辑游戏感兴趣。但是，数独在短短的时间内就变得极为流行，来势令人想起1980年代的魔术方块风潮。数独与三维的魔术方块不同，它是一个平面的方形格盘游戏，包含了81个小格（九列九行），其中又再分成九个小正方形（称为宫），每宫有九小格。游戏刚开始时，盘面上有些小格已经填了数字（称为初盘），游戏者要在空白的小格中填入1到9的数字，使得最后每行、每列、每宫都不出现重复的数字，而且每一个游戏都只有一个唯一的解答（称为终盘）。反讽的是，尽管数独号称是一种数字游戏，却用不到一丁点儿数学。事实上，完成这个游戏不需要任何数学运算（譬如加法或乘法）。理论上，我们可以将数字代换成另外九种不同的符号，例如字母、颜色、图像等。不过，数独倒是提供数学家和计算机学家许多挑战性的课题。

数独的族谱

有件事倒是解答得很清楚，那就是数独的起源。数独的祖先并不是魔方阵（magic square，填满整数的方阵，其中各行、各列、对角线的总和都必须一样），这点有违一般人的认知。事实上，除了数字和方阵之外，数独几乎和魔方阵没有瓜葛，反倒是和拉丁方阵（Latin square）颇有渊源。n阶拉丁方阵是每边n小格，总共有n2小格的方阵，方阵里填入n种符号，在每行每列中同，一种符号不能重复出现，因此每种符号各出现n次。这个格盘游戏的源头，可以上溯到中世纪。后来，18世纪的大数学家欧拉研究起这个游戏，并且称之为拉丁方阵。标准的数独游戏就像一个九阶的拉丁方阵，只是多了每宫也要包括数字1到9的额外条件。这个游戏第一次出现于1979年5月的《戴尔的铅笔与填字游戏》（Dell Pencil Puzzles and Word Games）杂志，根据《纽约时报》填字游戏编辑薛尔兹的研究，数独是一位退休建筑师格昂斯（Howard Garns）所发明的。格昂斯1989年（或1981年，说法不一）逝世于美国印第安纳波里斯，来不及看到自己的发明席卷全球。戴尔本来称这个游戏为Number Place（数字的位置），1984年这个游戏出现在一本日本杂志后，最后被称为Sudoku（数独），大约是「单一数字」的意思。当这本杂志把这个名称注册为商标后，日本的仿袭者只好回头使用Number Place的名称。这是另一个与数独有关的反讽：日本人称呼这个游戏时，用的是英文名称，而英语世界则使用日文名称。数独后续的成功必须归功于古尔德（Wayne Gould），他是一位住在香港、喜欢四处旅行的退休法官。1997年古尔德造访日本时，无意间发现这个游戏，后来他就写了一个可以自动产生数独游戏的程序。2004年底，伦敦《泰晤士报》接受他的建议，刊登这个游戏，隔年1月《每日电讯报》跟着搭上顺风车。此后，全球有几十家日报相继刊登数独，有些甚至放在头版上，做为促销的手法。其它专门讨论数独的杂志和专书如雨后春笋般出现在市场上，各种竞赛、网站、部落格更是蜂拥而来。

和全球人口一样多

很快的，数学家就开始跟数独玩起「到底有多少种」的游戏。举例来说，他们追问到底有多少种数独终盘的排列可能。显然答案肯定比拉丁方阵的解来得少，因为数独多了各宫限制的条件。目前已知三阶拉丁方阵有12组解，四阶拉丁方阵有576组解，至于九阶拉丁方阵的解，多达5,524,751,496,156,892,842,531,225,600组。不过如果运用群论，可以把从一种解所衍推出的所有解都视为等价。例如，如果有系统地把数字相互调换（好比以1换2、以2换7等），又或者如果把两列或两行交换，这样得到的结果，本质上和原来的解是相同的。假设考虑这种化约的形式，那么九阶拉丁方阵的解，就剩下377,597,570,964,258,816种，这是贝米耳（Stanley E. Bammel）与罗思坦（Jerome Rothstein）1975年发表在《离散数学期刊》（Discrete Mathematics）的研究成果，当时他们还在美国俄亥俄州立大学。要确切知道数独终盘的个数，是非常困难的事。今天只有利用逻辑简化问题，并且利用计算机有系统地检验所有可能性，才有可能算出所有正确数独终盘的数目：6,670,903,752,021,072,936,960组。这是德国德勒斯登工业科技大学的费尔根豪尔（Bertram Felgenhauer）和英格兰雪菲尔德大学的贾维士（Frazer Jarvis）的研究结果，并且经过多次的重复验证（以这种方式得到的结果，验证的工作十分重要）。但是如果把所有等价的化约形式算成一种，那么数独终盘的数目就缩减到5,472,730,538种，大概比地球的人口数少一点。不过尽管数字大大缩水，爱好数独的玩家还是不用担心没游戏可玩。

特别要注意的是，一个完整的数独终盘，可能来自各式各样不同的初盘。还没有人知道到底有多少种不同的初盘。而且，数学家真正感兴趣的是，数字不能再更少的「极小初盘」。意思是说，如果从极小初盘再移走一个数字，就不可能有唯一解。目前没有人知道有多少个极小初盘，这个数字相当于数独游戏的真正总数，势必将是数学家短期之内所要挑战的问题。
另外还有一类「极小」的问题也还没有解决：在保证有唯一解的条件下，一个初盘至少需要几个数字？答案似乎是17个。西澳大学的罗艾尔（Gordon Royle）已经搜集了38000多个满足这个条件的例子，这些例子是已经化约过，不能靠换行或换列来相互转换的。
爱尔兰国立大学梅努斯校区的麦盖尔（Gary McGuire）正在彻底搜寻着，希望可以找出16数字初盘并且有唯一解的情形，然而到目前为止还没有什么成果，看来似乎是没有这种可能性。另一方面，罗艾尔和其它人已经各自在寻找16数字初盘只有两个解的情形，不过迄今也还没有找到更多的例子。
有没有人已经快要证明16数字初盘不会有唯一解呢？麦盖尔认为还早，假设计算机每秒可以分析一组方阵，他说：「我们就可以在173年内搜寻完毕，很不幸，我们目前还做不到这一点，即使是现在的高速计算机也不行。」他认为不久之后，计算机会进步到平均每分钟可以处理一组方阵，但是以这种速度，将需要10380年才能完成搜寻。「即使分散到一万部计算机，也还需要一年的时间，」麦盖尔补上一句：「我们实在必须在理论上有所突破，做搜寻才比较有可能。要嘛我们得缩减搜寻的空间，不然就需要更棒的搜寻算则。」
数学家倒是知道最少初始数字相反问题的答案，也就是不能保证唯一解的初盘的最多数字，答案是77。就80、79或78个数字的初盘而言，都很容易说明这些情况保证有唯一解，但是77个数字的初盘就无法保证了。

计算机解题者

除了「有多少种」的问题外，数学家和计算机科学家也很喜欢思考，在解出或生成数独问题时，哪些是计算机能做？哪些是计算机不能做的事？就9×9的标准数独游戏来说，写一个能解出所有正确初盘的程序说不上困难。