Python 秒掉八皇后问题！

时间：2007-07-30 来源：h0ng123

来源：http://www.javaeye.com/topic/106747 引用在函数式编程语言曲高和寡？一文中，我们看到 Haskell 能用两行代码代码
sort [] = []
sort (x:xs) = sort [y | y <- xs, y < x] ++ [x] ++ sort [y | y <- xs, y >= x] 搞定快速排序算法。这是偶然，还是必然？在这篇文章中，lichray 用我们所熟悉的 Python 语言，几行代码搞定很多学编程几年的人都只是一知半解的算法——八皇后问题，展示和上篇文章中的快速排序一样清晰的、令人耳目一新的函数式算法思想。

预备知识：
这一部分对于那些 Python 老手和已经知道八皇后问题定义的程序员来说是多余的。
　　1. 八皇后问题（摘自 SICP ed2 中文版 P84 练习2.42）
　　“八皇后谜题”问的是怎样将八个皇后摆在国际象棋棋盘上，使得任意一个皇后都不能攻击另一个皇后（也就是说，任意两个皇后都不在同一行、同一列或者同一对角线上）。一个可能的解如图所示。
　　┌──┬──┬──┬──┬──┬──┬──┬──┐
　　│　　│　　│　　│　　│　　│ Q　│　　│　　│
　　├──┼──┼──┼──┼──┼──┼──┼──┤
　　│　　│　　│ Q　│　　│　　│　　│　　│　　│
　　├──┼──┼──┼──┼──┼──┼──┼──┤
　　│ Q　│　　│　　│　　│　　│　　│　　│　　│
　　├──┼──┼──┼──┼──┼──┼──┼──┤
　　│　　│　　│　　│　　│　　│　　│ Q　│　　│
　　├──┼──┼──┼──┼──┼──┼──┼──┤
　　│　　│　　│　　│　　│ Q　│　　│　　│　　│
　　├──┼──┼──┼──┼──┼──┼──┼──┤
　　│　　│　　│　　│　　│　　│　　│　　│ Q　│
　　├──┼──┼──┼──┼──┼──┼──┼──┤
　　│　　│ Q　│　　│　　│　　│　　│　　│　　│
　　├──┼──┼──┼──┼──┼──┼──┼──┤
　　│　　│　　│　　│ Q　│　　│　　│　　│　　│
　　└──┴──┴──┴──┴──┴──┴──┴──┘
　　在这篇文章中，我们要解决的问题比这个范围还要更广一点，即：允许棋盘是 n × m 大小的。也就是说，所谓的 n 皇后问题只是我们给出的程序的 n ＝ m 时的版本。不过别担心，函数式编程的力量就在于抽象等级的空前提高，问题越抽象，解决起来越顺手。
　　
　　2. 列表领悟特性
　　现在应该绝大多数动态语言的程序员都对这个特性很了解了，因为常见的 Python, Ruby, ErLang, Haskell 甚至是 JavaScript 都加上了这个特性。这是一种通过给出列表中每一项的形式和组成形式的元素要满足的条件自动生成列表的语法糖。下面是 Python 中的两个例子：

代码

# 得到一个 2 到 20 中的偶数组成的列表，只要写
>>> [x for x in range(2, 21) if x % 2 == 0]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
# 记住，只需给出一个形式，比方说想求两个列表的“笛卡尔乘积”
>>> [(x , y) for x in range(4) for y in [3,1,7,8]]

　　很明显，仅仅使用列表领悟特性就可以表示一些算法了，比如提到过的快速排序：
代码

def sort (ls):
　　return [] if ls == [] \
　　　else sort([y for y in ls[1:] if y < ls[0]]) + \
　　　[ls[0]] + \
　　　sort([y for y in ls[1:] if y >= ls[0]])
　　# 别忘了 python-2.5 的新特性条件分支表达式哦！可惜太长，不得不强制换行。

　　但要注意一点：实现拙劣的多未知数列表领悟（比如 Python）可能会崩了你的程序，文中会谈到这一点。

算法描述：
　　首先我们要认识到一点，算法所对应的函数的输入和输出分别是什么。我们需要的是一个函数 queens()，它接受两个参数，自然数 row 和 col，分别表示行数和列数；坐标是 (col, row) 形式的序对，下标从 0 开始计数。例如，对于一个 3 × 4 的棋盘，
　　┌──┬──┬──┬──┐
　　│0, 0│1, 0 │　　│　　│
　　├──┼──┼──┼──┤
　　│　　│ Q　│2, 1│　　│ row = 3
　　├──┼──┼──┼──┤
　　│　　│　　│2, 2│　　│
　　└──┴──┴──┴──┘
　　　　col = 4
　　我们把输出的结果表示为棋盘格局描述组成的列表。那棋盘格局呢？难道表示为所有棋子的坐标，像 [(5,0), (2,1), (0,2),(6,3), (4,4), (7,5), (1,6), (3,7)] ？不需要吧，看也能看出来，完全可以使得下标 col、row 中有一个是有序排列的。在这里，我们认为 row 是有序的，对于上面的例子，只须表示为 [5, 2, 0, 6, 4, 7, 1, 3] 即可，row 是一个解的下标。
　　那么，整个函数的输出就应该类似这样：[[1, 3, 0, 2], [2, 0, 3, 1]]；这是 queens(4,4) 的输出结果。

归纳法定义：
　　什么是归纳法定义？回忆一下经典的求级数例程是怎么写出来的。我们根据数学归纳法得到：
　　f (0) = 1
　　f (n) = 1 + f (n - 1)
　　然后把这些抄成编程语言的形式。对于函数 queens 也是这样，我们要确定这个函数的递归下界和递推表示。
　　递归下界很好办，就是 queens(n,0) （此处 n 忽略，因为不影响结果）的输出结果。对于一个没有列数的棋盘，只有一个解，空解 []；同时，输出的解集也只有这一个元素，为 [[]]（下面的数学定义使用了集合表示代替列表）。
　　f (*,0) = {{}}
　　递推表示是什么呢？我们可以在纸上画画图，不难发现，对于一个解，你画出的最后一个位置就是在前面已画出的少一个棋子的格局的基础上再加一个位置安全的棋子。设这个“加”函数为 g (x,y)，“安全”函数为 s (x,y)。那么
　　f (n,m) = {g (x,y) | x ∈ [0, n], y ∈ f (n,m-1) s (x,y) = true}

形式化的思考：
　　有了上面的数学定义，抄成 Python 代码，那就是用脚趾都能搞定呀。

代码

def queens (row, col):
　　return [[]] if col == 0 \
　　　else [[ran] + rst \ # 在 Python 中，g(x,y)=[x]+y
　　　for ran in range(row) \
　　　for rst in queens(row, col - 1) \
　　　if safe(ran, rst)]

　　不难看出，有了列表领悟这个强大的武器，我们就可以放心大胆地利用描述一个元素形式的思路来解决这类列表输出的问题。这就是列表领悟最根本的思想：“形式化的思维方式”。
　　现在只剩一个问题了：safe() 函数。先应用一次我们的“图形化的思考”。对一个格局（解，rst）来说，新加入的棋子的 col 值 ran 必须对这个格局中所有已存在的位置满足一个测试 check()，这个测试对于一个位置 (x,y)，要求（col 值不等已自动满足） ran ≠ x and |ran - x| ≠ y + 1。
　　ran ≠ x 很好理解，就是不为同一列；|ran - x| ≠ y + 1 则意味着左右不在同一斜线上。
　　┌──┬──┬──┬──┐
　　│　　│ran │　　│　　│　0
　　├──┼──┼──┼──┤
　　│x¹y │　　│　　│ Q　│　1
　　├──┼──┼──┼──┤
　　│ Q　│　　│　　│x²y │　2
　　├──┼──┼──┼──┤
　　│　　│　　│ Q　│　　│　3
　　└──┴──┴──┴──┘
　　　　0　　1　　2　　3
　　如图，算一算图中的两个点 (x¹,y) 和 (x²,y)，是不是满足了上面的式子？
　　由于这里要同时用到 rst 中点的 col 值和 row 值，这样解决：在前文的算法描述中已经指出，因为 row 值被认为是有序的，事实上是一个解的下标，我们 check 一下这个下标，在 check() 的过程中去获取 col 值不就行了？
代码

　　def check (pos):
　　　　# 表达式变个形式，少打点字
　　　　return not (ran == rst[pos] or abs(ran - rst[pos]) == pos + 1)

　　值得注意的是，由于这里 check() 用到了逃逸变量 ran 和 rst，check 函数体就必须写在 safe() 函数体内部以使这它们在其闭包环境中出现。
　　safe() 函数也就很明了了：先生成一个由全部 check(pos), pos ∈ [0, #rst] 结果组成的列表，然后判断一下这个列表中每一项是否都为真。假设我们已得到这样的一种测试一个列表中元素是否全为 True 的函数叫 ands()。
代码

def safe (ran, rst):
　　def check (pos):
　　　　return not (ran == rst[pos] or abs(ran - rst[pos]) == pos + 1)
　　return ands([check(pos) for pos in range(len(rst))])

　　前文已经说明，ands() 函数接受一个列表为参数，如果列表中每一项都为 True 则返回 True，否则返回 False。还是直接把数学定义抄一遍：
代码

def ands (ls):
　　return True if ls == [] \
　　　else (False if not ls[0] \
　　　else ands(ls[1:]))

　　于是，我们的程序就写完啦！试着跑一下 queens(4,4)，
代码

>>> queens(4,4)
[[1, 3, 0, 2], [2, 0, 3, 1]]

　　没问题！再跑一下 queens(8,8)！奇怪，为什么跑了 10 分钟还没出结果？

问题在哪儿：
　　拙劣的列表领悟实现。Python 在处理列表领悟时，一方面把“形式”部分封装为一个函数，然后找出所有未知数的列表，组装成一个大的矩阵，然后对矩阵中的每一项应用该函数。问题出在哪儿？先生成了所有项，占用了过多的空间。如果在 Haskell 里面，这样做是无所谓的，因为惰性的列表会生成一点，计算一点，抛弃一点，输出一点；但这对于严格（采用应用序求值）的命令式语言 Python 来说，这种实现仅仅是玩具级的。
　　其实，列表领悟不仅仅是一个语法糖，在严格的语言实现它需要一定技巧：首先分析未知数对于的列表的计算所消耗时间（数据流分析 call 的次数），把计算耗时最多的列表应用群体操作，对结果的每一项应用产生下一个列表的群体操作，依此类推，只要产生一个包含所有未知数的序对就应用包装好的函数。空泛的讲这些用处不大，下面我们手工把这个该死的程序救活。

通用列表操作：
　　关键在于处理掉这一句：

代码

[[ran] + rst \
　　　for ran in range(row) \
　　　for rst in queens(row, col - 1) \
　　　if safe(ran, rst)]

　　首先对最耗时的列表 queens(row, col - 1) 应用群体操作 flatmap(newcol, queens(row, col - 1))。这里需要注意的是，光用 map() 是不够的，因为下面会根据另一个列表 rang(row) 中的每一项产生一个新列表，导致多出一个列表层。所以我们需要用 flatmap() 函数，它在普通的 map() 操作之后会用 append() 把产生的列表联结起来（所以叫“展平”的 map），把多出的一层列表消去：
代码

def flatmap (opt, ls):
　　# 小技巧：累积器在连接列表时可以不用 lambda x,y: x+y，直接用 list.__add__，
　　# 重点是类型出错时有报警
　　return reduce(list.__add__, map(opt, ls))

　　接下来，根据列表和列表生成列表（在通用列表操作的世界中，就是 list, list, and list），注意原来的形式 [ran] + rst 是怎么被函数封装掉的：
代码

def newcol (rst):
　　# 顺手解决 filter 只能传递一个参数的限制，用 lambda 代掉
　　return filter(lambda ls: safe(ls[0], rst), map(lambda x: [x] + rst, range(row)))

　　其它什么内容都不用改了（当然了，如果你有心情，还可以把另一个列表领悟替换掉，
代码

def safe (ran, rst):
　　return every(check, range(len(rst)))
# every() 函数相当于打过兴奋剂的 ands
def every (test, ls):
　　return True if ls == [] \
　　　else (False if not test(ls[0]) \
　　　else every(test, ls[1:]))

　　不过单层的列表领悟没有性能问题）。现在可以完美地输出八皇后问题的 92 个解了（这里就不列了，太长了）。来源：http://www.javaeye.com/topic/106747