三种编程范式解决八皇后问题(1)

众所周知，命令式编程(Imperative programming)，声明式编程(Declarative programming)，函数式编程(Functional programming)都是常见的编程范式。目前编程语言中运用最广泛的还是命令式编程语言了，本文将以Python为例展示如何使用命令式编程语言解决经典的八皇后问题。

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。

八个皇后在8x8棋盘上共有4,426,165,368种摆放方法，但只有92个互不相同的解。如果将旋转和对称的解归为一种的话，则一共有12个独立解，其中一个解如下图1所示：

首先需要讨论的是如何表示棋盘的摆放，可以使用一个8x8的二维数组表示整个棋盘，但这样需要的空间相对比较多。可以发现，为了满足八皇后问题的条件，棋盘上的每一行必然只能有一个皇后，所以可以使用一个长度为8的数组，分别表示8行，数组中每个元素表示在该行中皇后被摆在第几列。例如上述棋盘中的摆放为[3,6,2,7,1,4,0,5]。首先在Python中写一个方法用来打印棋盘：

def printBoard(columns, n=8):
    print "\n".join(['-' * col + 'Q' + '-' * (n - col - 1) for col in columns])

上述棋盘将被打印为：
---Q----
------Q-
--Q-----
-------Q
-Q------
----Q---
Q-------
-----Q--
可以看到，‘Q’表示皇后的位置，‘-’表示空的位置。

由于现代计算机的计算速度非常快，枚举所有的摆放情况也可以在合理的时间内找出所有的有效解，但是一些简单的优化便可以大幅度的减少枚举中可能出现的情况。可以注意到的是，由于同一行和同一列都只会有一个皇后，所有有效解必然是[0,1,2,3,4,5,6,7]的一个排列(Permutation)，那么需要枚举的数量一下缩小到了8!=40,320种。

接下来需要的是如何检验一种摆放是符合要求的，由于使用上述的表示方式和Permutation，已经保证了横向和纵向上没有冲突，所有只需要检查斜线是否冲突。在这里使用一种检查斜线上棋子的方法：

def checkDiagonal(columns):
    return len(columns) == \
        len(set(columns[i] + i for i in range(len(columns)))) == \
        len(set(columns[i] - i for i in range(len(columns))))

这种检验斜线的方法的原理是对于每一条斜线的两个位置在加上或者减去其列号后的值都是相同的。上述代码执行了这个操作，然后用set去除重复的值，再检验留下元素的数量以判断是否有重复的值。这种检验方法可以在线性的时间内完成。

结合Python的itertools库中的permutations方法，只需要添加几行代码便可以解决八皇后问题：

from itertools import permutations
def nQueensBrute(n=8):
    solutions = []
    for board in permutations(range(n)):
        if checkDiagonal(board):
            solutions.append(board)
    return solutions

若将上面三个方法写成一个函数，不到10行便可以解决8皇后问题，这就是Python的简明之处。但是使用permutations方法还是会有很多没有必要的检验，在生成摆放时如果进行动态的剪枝还可以缩短运行的时间。例如，对于所有开头为[0,1]的排列，由于前两个皇后已经在一条斜线上了，可以知道无论接下来的序列如何都是不可能符合要求的。然而对于开头为[0,2]的排列，在没有进行更深层的检验时，可以认为它们是有可能符合要求的。以下程序中使用一个队列保存这些有可能符合要求的部分排列，并动态的添加新的皇后：

def nQueensDynamic(n=8):
    partials=[[]]
    solutions=[]
    while partials :
        partial = partials.pop(0)
        if len(partial) >= n :
          solutions.append(partial)
        else :
          for col in xrange(n) :
              if col not in partial and checkDiagonal(partial+[col]):
               partials.append(partial+[col])
    return solutions

动态的剪枝性能明显优于普通的方法，并且由于普通的方法的复杂度以阶乘的形式上升，当n增大时两种方法的差距异常明显。从下面的运算时间统计可以看出，当n为10时，动态的方法运行的时间仅为普通方法的二十分之一。

timeit nQueensDynamic(8)
100 loops, best of 3: 17.7 ms per loop

timeit nQueensBrute(8)
10 loops, best of 3: 92.3 ms per loop

timeit nQueensDynamic(10)
1 loop, best of 3: 469 ms per loop

timeit nQueensBrute(10)
1 loop, best of 3: 9 s per loop