Solving Every Sudoku Puzzles: Part 2

Contiune Solving Every Sudoku Puzzles: Part 2

数独(Sudoku)迷题的通用解法: Part 2

搜索

另一条路是通过搜索来得到答案：全面尝试所有的可能性知道我们恰巧得到一个可行的解答。这种方法的代码时候很少的几行，但是我们会面临另一个问题：有可能永远也算不完。让我们回到上面提到的hard puzzle，A2有4种可能（1679），A3有5种可能（12679）；那么现在一共有20种可能，如果我们连乘下去，对于这个迷题，我们会得到462838344192000000000000000000000000000 (或大约 4 ×10^38)种可能。你肯定吗？一定确定以及肯定，这里有61个待解开的方块，并且每一个这种方块都有4或5种可能。而且，事实上4^61<4x10^38<5^61。我们怎么来对付它呢？看来有两种选择。>首先，我们可以尝试蛮力法(brute force)。假设我们有一个非常智能的搜索算法可以用一条指令估计一个位置，而且我们有下一代的计算技术，就假设是一中1024核的10GHz处理器，我们买了一百万颗这样的处理器，当我们在购物的同时，还买了一台时间机器，帮助我们回到开天辟地的时候，让这个代码跑起来。就这道题目直到现在，我们大概可以计算过大概1%的可能值。

第二种选择是用某种方法使得每条机器指令处理估计一种以上的可能。这看起来不太可能，而幸运的是这种方法就是约束传递所作的。我们不用试过所有4 x 10^38种可能，因为我们只要试过一种，马上就可以消去很大一部分的可能值。例如，方块H7有两种可能，6和9。我们可以试试9，很快会发现有一个冲突，这意味着我们不仅消去了一种可能，而是4 x 10^38种可能的一半。

事实上，在解这个问题的时候我们只需要试25种可能值和9个方块（一共61个待解方块）；而约束传递解决了剩下来的问题。对于剩下来的95个hard puzzles，我们平均需要试64种可能值和不超过16个方块。

那什么是搜索算法呢？简单：先确定我们是不是已经得到结论了或者存在冲突，如果都不是，再选择一个待解方块并尝试它所有的可能值。一次一个，尝试给每一个方块赋所有的可能值，并且从已知的盘面开始搜索。换言之，我们搜索一个值d，使得我们可以成功的从将d赋值给方块中解出需要的解。这就是recursive search，我们将它称为depth-first搜索，因为我们（递归地）考虑values[s]=d是中所有，之后再考虑方块s的其它可能值。

为了防止bookkeeping nightmares，我们为每一次search递归调用复制一个新的拷贝。（译者注：bookkeeping nightmare不太理解，可能和实参形参有关）这样一来search tree的每一个branch都是独立的，不会相互干扰。（作者注：这就是为什么我选择将一个方块的可能值的集合设计成一个字符串’：我可以用简单有效的values.copy()来复制拷贝。而假如我用Python的set或list来实现这个可能值的集合，我不得不用copy.deepcopy(values)，而这个方法效率比较低。）另一种方法是保持values每一次改变的值，当我们碰到一次False的时候就将改变前的值恢复出来。这被称为backtracking search。这种方法在每一步都是单个改变（single change）的时候才有意义，而在我们的迷题的算法中有许多改变都来自于约束传递，这样的技巧会将我们引入复杂的泥潭。

所以，余下来的问题就是如何在搜索的每一步选择一个方块s来赋值。让我们回到上面的hard puzzle，假设我们选择B3，它有7种可能值（1256789），所以我们猜错的可能性是6/7。而，如果我们选择H7，它只有2种可能值（69），我们猜错的可能性是1/2。很明显，选择H7会更可能将我们引导到正确的答案，所以我们总是选择有最少可能值（或者其中一个）的待解方块s。

现在我们可以实现search函数了：

def search(values):
    "Using depth-first search and propagation, try all possible values."
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in squares):
        return values ## Solved!
    ## Chose the unfilled square s with the fewest possibilities
    _,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
    return some(search(assign(values.copy(), s, d))
                for d in values[s])

终于完成了！我们现在可以在理论上解决所有的数独迷题。在实际应用中，hard puzzles上的95个难题，我们的程序以每秒钟8个难题的速度解决；easy puzzle的容易题则是每秒钟30个。（假如我为了执行效率改写程序，这个程序可以快10倍，但是代码长度会增长到2到5倍。）然而，是否有可能存在这样一个迷题，我们的程序会用极长的时间去解它；我想这是不存在的。在零点几秒的时间里，这个程序可以解决全空数独迷题（81个未解方块），以及我在hardest sudoku上看到的五个迷题。特别的是，有一篇新文章描述了芬兰数学家Arto Inkala所说的“史上最难的数独迷题”；我的程序只用了0.013秒就解出来了（大约超过300次尝试）。

结论
你可以在这里看到Python源代码（100行），或者95个hard puzzle迷题的输出结果（1140行）。

译后记
读Peter Norvig的文章和代码，有如沐春风的感觉。另一篇”Spell Corrector”也值得一读，在Norvig的网站上，已有中文翻译。
Peter Norvig，现在是Google的技术主管。在UCB期间，合著影响广泛的“Modern AI”。