数独游戏是个 9×9 的方格， 方格中填1–9， 其中部分方格填的数告诉你了， 让你推理出其他的方格。 规则是每行每列，以及9个3×3 的区块中都正好是 1–9。 详细的解释请自己搜索。。

用计算机解这个问题显然是很方便的， 即使最简单的搜索也不会很慢。 但这里介绍是另一种方法。

 

如果把每一行，或者每一列，或者9个3×3的区块中任一一个， 都称为一个 group 的话， 那么整个盘面上共有 9 + 9 + 9 = 27 个 group。 如果任意两个在同一个 group 里的方格，称为相邻的话， 那么可以证明任意 k (k>=3) 个两两相邻的方格都在同一个 group 里面。

 

接着，除了一开始告诉你的格子以外， 每一个不确定的格子都初始化为九种可能都可能的状态。 也就是说， 每个格子相当于一个有可能的数的集合， 一开始告诉你的格子，它的集合就一个元素， 否则就是9个元素。

接下来就是不断删除可能性集合中元素的过程，如果一个 group 中一个数只出现了一次， 那么就是它。 比如某 group 中某个格子是 {1,2,3}, 但是其余格子都没有出现2， 那么它就是2。

 

另一种最简单的删除是，任何一个 group 中某个格子确定后， 它的邻居都可以把这个数删除掉。但是这种是可以推广的： 假设有 k 个两两相邻的格子的集合之并恰好有 k 个元素， 那么它们就正好使用这 k 个元素。

前面已经说过了，k 个两两相邻的格子必然在同一个 group 里面， 那么我们只需要对每个 group 挑出 k 个元素， 把他们并起来，如果恰好是 k 个元素，那么此 group 的另外 n-k （这里 n = 9）个格子就可以把这 k 个元素都删除。

 

根据我的实验，所有数独游戏都可以按照上面的方法解出来，虽然我实验的也不多。。 这种方法的好处是：1。 容易推广， 如果 n增加，比如等于 16， 那么这种方法变慢的幅度比搜索小， 因为一个是 n^(n^2) 阶的，一个是 n^n 阶的。。虽然实际上的速度都要比这个阶快很多。。 2。 有很多附带的信息， 如果是仅仅搜索的话， 你只能得到一个结果， 但是这个你得到很多信息， 比如你可以知道某个格子是如何被计算出来的， 这样你可以估算出问题的难度， 而且可以给出“人能看懂”的提示。