K.I.S.S

自己好几年之前无聊的时候写解数独程序的时候看的,原以为到现在还没人翻译成中文版的,搜了搜,果然已经有了. 自己用的约束传递的方法,不过当时还不知道这个名词,结果发现有缺陷,于是又考虑的在约束传递基础上暴力解决,其实吧,就是后面的搜索,但是感觉暴力太难看,就搜网上的方法,于是就看到了这篇文章,但是当时写完约束传递已经过了热情期了,扔那不管了,果然编程语言很重要.只要不是确实有限制,性能问题还是扔一边吧.好的算法可以弥补性能问题,快速解决问题多好. 英文原版来自Google的Peter Norvig 的 blog，中文版本转自 Shenli's Blog ，与英文原文有出入，可能是版本原因，在此基础上根据原文做了修正。¹ 文中译后记的拼写检查器的中文地址:http://blog.youxu.info/spell-correct.html

by Peter Norvig

在这篇文章里，我将提出一种数独(Sudoku)迷题的通用解法。它看上去相当简单（大约100行代码），并采用了两个思想：约束传递（constraint propagation）和搜索（search）。

函数parse_{grid调用assign}(values,s,d)来将数字d赋予方块s的值。所以，我们希望以values[s]=d来结束，但是我们还是想要用一些其他的方法来改变values。特别是我们希望在s的peers里消除所有可能的d。如果消除d导致其中的一个peer变成一种可能（译者注：即只有一个数字），我们称之为d2，那么我们希望从这个peer的peer消除所有可能的d2，（译者注：这里好像和代码有些出入？，代码里是消除d导致方块s的值变成一种可能），等等。以上被称为约束传递(constraint propagation)：将某个约束置于一个方块之上会引发蝴蝶效应，即将更多的约束递推到了其它方块上。

这里还有第二种约束传递。比如说我们刚刚将6从方块A1的所有可能值中消去。而假如我们看到包含A1的第一个unit里面所有的方块里，只有C1将6作为它的可能值。我们可以将6赋给C1。所以我们需要两个函数：assign(values,s,d) 和eliminate(values,s,d)，它们会互相调用来实现约束传递（我们将这种函数称为mutually recusive）。虽然不是很明显，但是我们有可能会犯一个错误：我们会试图将一个不符合数独规则的数赋给方块。在这种情况下，我们希望assign()和eliminate()返回False来指示错误。在通常情况下，每一个函数都会用传递来的约束稍稍改变一下数值，然后返回给另一个函数。以下是实现代码：

def assign(values, s, d):
    "Eliminate all the other values (except d) from values[s] and propagate."
    if all(eliminate(values, s, d2) for d2 in values[s] if d2 != d):
        return values
    else:
        return False






def eliminate(values, s, d):
    "Eliminate d from values[s]; propagate when values or places <= 2."
    if d not in values[s]:
        return values ## Already eliminated
    values[s] = values[s].replace(d,'')
    if len(values[s]) == 0:
        return False ## Contradiction: removed last value
    elif len(values[s]) == 1:
        ## If there is only one value (d2) left in square, remove it from peers
        d2, = values[s]
        if not all(eliminate(values, s2, d2) for s2 in peers[s]):
            return False
    ## Now check the places where d appears in the units of s
    for u in units[s]:
        dplaces = [s for s in u if d in values[s]]
        if len(dplaces) == 0:
            return False
        elif len(dplaces) == 1:
            # d can only be in one place in unit; assign it there
            if not assign(values, dplaces[0], d):
                return False
    return values

这里有一种有用的设计模式，好像从没有人提过。这个模式是：

如果你有两个mutually-recursive的函数分别影响一个对象的状态，请试着将所有的功能代码移到其中一个函数去。否则，你最后会发现有许多重复代码。

我是在许多年的Lisp编程后发现这个设计模式的，在Lisp里mutually-recursive函数很常见。看看我们怎么样在这个问题里应用这个模式：有人会认为assign()将包含赋值语句values[s]=d，而且会包含传递约束。你可以试着写这样一个函数。我想，你最后会发现你是在重复eliminate()里的代码。所以为了避免绕这么个弯子，我推论assign()函数做的就是消去方块s里除了d以外所有的数字，所以我将所有的功能代码写到了eliminate()里。

在我们探索更远之前，我们需要能够检验一下数独盘面的状态。以下就是printboard()的代码：

def printboard(values):
    "Used for debugging."
    width = 1+max(len(values[s]) for s in squares)
    line = '\n' + '+'.join(['-'*(width*3)]*3)
    for r in rows:
        print ''.join(values[r+c].center(width)+(c in '36' and '' or '')
                      for c in cols) + (r in 'CF' and line or '')
    print

现在我们可以开始解题了。我选了easy puzzles上的第一个问题，试了一下：

>>> grid = """
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300"""

>>> printboard(parse_grid(grid))
4 8 3 9 2 1 6 5 7
9 6 7 3 4 5 8 2 1
2 5 1 8 7 6 4 9 3
------+------+------
5 4 8 1 3 2 9 7 6
7 2 9 5 6 4 1 3 8
1 3 6 7 9 8 2 4 5
------+------+------
3 7 2 6 8 9 5 1 4
8 1 4 2 5 3 7 6 9
6 9 5 4 1 7 3 8 2

在这个例子里，这个数独迷题完全被我们的约束传递解开了！只是通过赋予32个方块值，我们简单的约束传递规则就把剩下来的所有方块都填满了。但是，不是所有的题都是这么容易。接下来是hard puzzles里的第一个问题:

>>> grid = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'

>>> printboard(parse_grid(grid))
   4      1679   12679    139     2369    269      8      1239     5
 26789     3    1256789  14589   24569   245689  12679    1249   124679
  2689   15689   125689    7     234569  245689  12369   12349   123469
------------------------+------------------------+------------------------
  3789     2     15789    3459   34579    4579   13579     6     13789
  3679   15679   15679    359      8     25679     4     12359   12379
 36789     4     56789    359      1     25679   23579   23589   23789
------------------------+------------------------+------------------------
  289      89     289      6      459      3      1259     7     12489
   5      6789     3       2      479      1       69     489     4689
   1      6789     4      589     579     5789   23569   23589   23689

在这个例子里，我们离解出这个问题还差得很远。我们开始只有17个方块填了数字（这被认为是最少的可以达到唯一解的数目），在约束传递之后，只有3个方块被解了出来（虽然所有的方块都被消去了一些可能值）。

我们接下来要怎么做呢？我们可以尝试一些更加复杂的约束传递技巧，就像这里说的。比如说naked pairs技巧寻找在同一个unit里的两个方块，它们有两个相同的可能值。假设A1和A4都有2和6的可能值。我们可以推论2和6一定在A1和A4里（虽然我们不知道究竟哪个在哪个里面），而且我们可以将2和6从这个A行unit里面的其它方块里面消去。我们可以仅仅在在代码里加上几行，比如elif len(values[s]) == 2来实现这个功能。

类似的代码技巧是可行的，但是会导致代码量的膨胀（大概有二三十种技巧），而且我们永远不会知道我们是否能依靠这些技巧解出所有迷题。

另一条路是通过搜索来得到答案：全面尝试所有的可能性知道我们恰巧得到一个可行的解答。这种方法的代码时候很少的几行，但是我们会面临另一个问题：有可能永远也算不完。让我们回到上面提到的hard puzzle，A2有4种可能（1679），A3有5种可能（12679）；那么现在一共有20种可能，如果我们连乘下去，对于这个迷题，我们会得到462838344192000000000000000000000000000 (或大约 4 ×10³⁸)种可能。你肯定吗？一定确定以及肯定，这里有61个待解开的方块，并且每一个这种方块都有4或5种可能。而且，事实上4⁶¹<4x10³⁸<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”。