数独生成浅尝

Sudoku

数独是一种非常有意思的游戏,也是我很喜欢的一种游戏,当闲来无事的时候,常常会打开手机里的数独游戏来打发时间。当我们在享受数独游戏的时候,有没有想过每一局游戏是如何生成的呢?看似简单,其实很复杂。有不少相关的算法,还有一个困惑了数学家多年的谜题(2011年12月被解开)。下面就让我们一起来看看数独的生成。

什么是数独

可能有些朋友还不知道什么是数独,下面是来自维基百科的解释:

數獨 Sudoku(数独,sūdoku,すうどく)

/suːˈdoʊkuː/soo-DOH-koo是一種邏輯性的數字填充遊戲,玩家須以數字填進每一格,而每行、每列和每個宮(即3x3的大格)有齊1至9所有數字。遊戲設計者會提供一部份的數字,使謎題只有一個答案。

一個已解答的數獨其實是一種多了宮的限制的拉丁方陣,因為同一個數字不可能在同一行、列或宮中出現多於一次。

这种游戏只需要逻辑思维能力,与数字运算无关。虽然玩法简单,但数字排列方式却千变万化,所以不少教育者认为数独是锻炼脑筋的好方法。因为数独上的数字没有运算价值,仅仅代表相互区分的不同个体,因此可以使用其他的符号比如拉丁字母、罗马字母甚至是不图形状的图案代替。

下面是一个数独的题目以及解答:

Sudoku Example Sudoku Solution

如何生成数独的解答

要生成一个数独,直接生成它的迷局比较困难,我们可以先从解答开始。当我们看到数独的时候,就会发现他其实就是一种数学矩阵,当我们在考虑如何生成数独的时候,也可以从矩阵变换的角度来考虑。我们可以从一个完成的数独开始,例如:

Sudoku Origin

对于这个9x9的矩阵,我们现在要考虑的就是如何打乱每个数字的位置,而不破坏它的规律——每行、每列、每宫都有1至9的所有数字。符合这个条件的矩阵变化有以下几种:

  • 交换每组(1-3行为一组,4-6行为一组,7-9行为一组)中的任意两行:

    Sudoku Transform 1

  • 同样也可以交换每组中的任意两列。

  • 组之间的行互换:

    Sudoku Transform 2

  • 同样也可以组之间的列互换。

  • 矩阵转置:

    Sudoku Transform 3

几乎各种编程语言都会有矩阵计算的库,由于本人比较专注于JavaScript,所以这里推荐一个JavaScript的矩阵计算库:Sylvester,有了矩阵计算库的支持,再加上前面几种等价变换,我们可以很容易生成出一个数独的结局。

如何生成数独的迷局

结局生成好了以后,下一步就是要清空其中的某些数字格,从而生成迷局,这是最难也最有讲究的。数独游戏有一个“潜规则”:每个游戏只能有一个解答,如果有两个或者以上的解答,那么游戏的难度将会降低。所以我们在清空数字格的时候也不能随意的清空,我们必须保证它最后只有唯一解。

很遗憾的是,在我的能力范围之内以及搜索范围内没有找到有哪种算法可以保证数独只有唯一解,也没有某种算法可以验证一个谜题是否一定有多个解(除非有一组三行全为空)。不过一些研究标明,有某种pattern会导致数独一定有多个解,请见“Deadly Pattern”。我们可以做的有以下几点:

  • 保证在去掉数字格的过程中不会同时去掉一组的三行
  • 使用Solver验证生成的迷局是否有多个解
  • 当出现“Deadly Pattern”时,撤销上一次去掉数字格的操作,重新去掉一个新的,再次回到上一步做验证

数独的数学谜题

这里还有一个困扰了数学家数十年的问题:数独游戏最少需要多少个数字,才能保证最后有唯一解?曾经有数学家找到过17个数字并且具有唯一解的数独,但是一直没有找到16个数字的唯一解数独。于是部分数学家相信17个数字就是唯一解数独的最少数字了,也有数学家任然在寻找16个数字的唯一解数独,只是一直都无法证明17这一最少数字,也一直没有找到16个数字的唯一解数独。

这个谜题终于在2011年12月被Gary McGuire以及他在都柏林大学的朋友们一起破解了,他们利用计算机程序遍历了所有16数字的数独,最终没有发现唯一解数独,从而以穷举的方式证明了数独游戏最少需要17个数字,才能保证最后有唯一解。他们利用对称性去掉了所有等价的数独,任然计算了5,472,730,538次以及一年的时间才得到这个结果。

参考资料: