《编程之美》读书笔记(七)：数独游戏解析

《编程之美》读书笔记(七)：数独游戏解析

前言：说实话，所有游戏都是有一定规律可循的，只要掌握游戏规则通关就会变得容易，所以像九连环和魔方这样的游戏会产生看一眼之后就闭着眼睛完成的高手出现。但是数独游戏有所不同，如果其初始状态的生成过程充分随机且空白比较多的话就不那么容易解决，所以数独矩阵的生成就是本题的关键。以往我的关注点主要在补充书中算法的遗漏或不足上面，但是由于感觉这个游戏确实挺好玩，而且作者也没把他的源码公布出来，所以我就利用书中的算法和自己想的算法作了一个数独生成器出来，大家有兴趣的话可以留言管我要，不过要回答本文最后提出的问题才可以J。

1 问题的描述与讨论

本文所说的数独是指：一个由9个3*3的子矩阵组成的9*9矩阵，其中每个3*3矩阵都由1-9这9个数字组成，且数独矩阵中每行每列都没有重复数字。在游戏的初始状态，数独矩阵是残缺不全的，玩家在填入数据时要保证数独的定义规则不被破坏。显然，残缺的数字越多，游戏就越困难。但是，如果被用户看出了数字的生成规律（如书中解法二介绍的行列变换生成法），填数就变成很简单的事情了。

于是我们的关注点就很明显了，就是要研究如何生成一个数独，但在此之前我们考虑一下问题：

1．有多少个数独（符合规则的9*9的矩阵）存在？

2．为什么行列变换生成法可以生成有效的数独？

3．如何使得生成的数独更具随机性？

1.1 关于独立有效的数独数量的讨论

这个问题书中第4.9节给出了一个求解数独数量的估计方法和一个与精确结果相差很小的估计值。大体的思路是，将3个在一行的3*3矩阵视为一个行向量，每个行向量内部仍然保证数独定义的约束，求出所有不同的行向量的数量(M1)3；同理也可以求出所有不同的列向量的数量(M2)3，并假设二者相互独立（事实上不完全独立），得到的估计值为6.657*1021，而精确值为6.671*1021。虽然书中并未给出精确值的求解方法，但是给出了参考文献，有兴趣的话可以去看一下。但是有些令我不解的是，在直观上，假设行列向量相互独立的情况下得出的数独数量应该多于不完全独立情况下的数量，毕竟在完全独立的情况下得到的一些矩阵可能会与数独的“每行每列数字不同”的约束相冲突而不能作为有效的数独。所以按照书中的估计方法，估计值应该大于精确值才对。所以应该用所有“块行解”的值乘2作为估计值，这个值虽然要比精确值大很多，但是觉得似乎更说得通。当然，也可能是我理解有误，有不同意见的朋友可以留言。

1.2 数独生成算法的分析

1.2.1. 方法一：回溯法

书中给出了两种方法，第一种方法还是使用回溯法，原理是构建一棵搜索树（深度为9*9），然后对每一个格子用不同的数字进行尝试，如果不与数独构造法则冲突则继续搜索，否则返回到上一个节点换个数继续搜索。这个方法的缺点很明显，在搜索过程中，对于每一个数都要考察其是否满足数独规则，即是否与所在小矩阵中的数字重复和是否存在行列重复。此外如果运气不好的话搜索过程可能会很漫长。好处是生成的数独足够“随机”，除了数独规则外没有什么规律可循，所以如果游戏的留白比较多的话将是一个很考验智商的题目。同时我们似乎可以用这种方法来得到所有合法数独的精确值（只是不知道我家的老爷机多长时间才能搞定J）。

1.2.2. 方法二：矩阵变换法

相比较第一种而言，书中给出的方法二是简洁高效得过了头。方法是以中间的矩阵为中心，利用列变换生成2号和8号矩阵（我们将所有子矩阵按照行优先的顺序从1-9进行编号），再使用行变换生成4号和6号矩阵，最后分别用4号和6号矩阵利用列变换生成1号、7号矩阵和3号9号矩阵。这样就最重形成了一个合法的数独。这种方法的具体实现过程在下一节会有详细说明。该方法唯一的好处就是简单，但是太过简单的生成方式很容易让玩家找到规律，降低了难度。

我在这里简单说明一下为什么这样做能够产生合法的数独。首先我们知道利用行列变换生成的2、4、5、6、8号矩阵是满足数独规则的，下面就只需要证明1、2、3号矩阵满足“每行都没有重复数字”且1、4、7号矩阵满足“每列都没有重复数字”。首先，4，5，6号矩阵所组成的向量中的每一行都没有重复数字，所以在这4号和5号矩阵内部进行任意的列变换都不会在行上产生重复数字。同时2号矩阵又是5号矩阵通过列变换得到的，所以1，2，3号矩阵在行上不会产生重复数字。而1和7号都是4号矩阵经过列变换的到，所以他们在列上不会有重复数字。证毕！

1.2.3. 方法三：其他方法

既然第二种方法太容易被识破，那么我们似乎应该开发一些复杂度低于第一种方法但是随机性比第二种方法好一些的生成算法来。我简单的想了一个，生成过程如下图所示：

首先随机生成对角线上的3个矩阵，然后按照后两图的方式采用方法一生成最终的数独。我想这样做即增加了随机性，也不会使太过于缓慢。不过这只是抛出去的“砖”而已，希望有兴趣的朋友能够提供一些更好的方法，有“玉”的朋友请不吝留言J。

1.3 数独游戏的实现

由于MSRA的网站上并没给出源码，我就自己用Java写了一个。下图是利用方法二制作数独的过程，有兴趣的朋友可以继续开发新的算法，让这个游戏更加丰满起来，在学到知识的同时还能娱乐自己。

2 后记

本节是我到目前为止看到错误最少的一节，几乎没有什么错误。关于我写的数独代码，自然是希望提供给有兴趣的朋友去研究新的生成算法，免去写界面的麻烦。但是有小小的要求：

1．点击左侧广告一次J

2．假设现要构造的是一个9*9的数独方阵，用Cell[9][9]保存，每个子方阵是3*3，每个子方阵的按照行优先进行编号，其编号分别为1，2，….，9。现给出方阵的编号，如何获取该方阵内的所有格子的坐标。例如，2号子阵中所包含的9个格子的坐标分别为：{{[0][3],[0][4],[0][5]}，{[1][3],[1][4],[1][5]}，{[2][3],[2][4],[2][5]}}；假设现在给出第i号子阵，你能给出取得其中包含的格子坐标的计算公式吗。很简单吧？

3．请回答问题2的答案在程序写程序的时候哪里会用到（写出一个用途即可）。

请在下面用留言方式给出答案和邮箱地址，我会把源码发给回答正确的朋友。回答不正确的朋友也没关系，因为你将获得本游戏的界面源码（算法就靠你自己写了J)