用 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
　　├──┼──┼──┼──┤
　　│x1y │　　│　　│ Q　│　1
　　├──┼──┼──┼──┤
　　│ Q　│　　│　　│x2y │　2
　　├──┼──┼──┼──┤
　　│　　│　　│ Q　│　　│　3
　　└──┴──┴──┴──┘
　　　　0　 　1　 　2　 　3
　　如图，算一算图中的两个点 (x1,y) 和 (x2,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 个解了（这里就不列了，太长了）。

反思：

• 函数式编程的思想描述算法绝对强，无论是列表领悟还是通用列表操作都十分清晰，仿佛能感受到数据在表达式间游动；
• 和平起见，就不把我那个传说中的只有一行代码的版本拿来和几十行的命令式风格的代码比较了，但大家应该心领神会；
• 有时候，把问题想的简单一些，思维更“形而上学”一些，反而能更快的得到解决问题的思路，顺着思路再改进也不迟；
• Python 的表达式版的分支语句很漂亮，但被该死的换行限制给玷污了；另外列表领悟实现得够烂，眼下只能是玩玩儿。

最后留个小问题：我们在算法描述一节中提到了一种解的表示方法，把一个格局中所有棋子的坐标表示为序对，然后返回解的列表。请给出一个小函数，把我们现在的实现版本输出的解转换为这种形式。数据的本质是信息。信息的完全是首要的，数据的表示只是个次要问题。

除了列表领悟(貌似其它的地方都翻译成列表内涵，但都是词不达意的说法)，python还有一个类似的lazy匹配物generator.
主贴的算法没仔细看，最烦看算法了，但是我想下面的这个generator的例子足以解决文中那段因为“拙劣”的列表领悟实现而必须挽救的代码。

>>> a = ( a+b for a in xrange(1,10) for b in xrange(100,300,100) if a%2)
>>> a.next()
101
>>> a.next()
201
>>> a.next()
103
>>> a.next()
203
>>> a.next()
105
>>> a.next()
205
>>> b = list(( a+b for a in xrange(1,10) for b in xrange(100,300,100) if a%2))
>>> b
[101, 201, 103, 203, 105, 205, 107, 207, 109, 209]

这篇文章Code Like a Pythonista: Idiomatic Python中给出了generator和list comprehensions的适用场合：

对于主贴中的情形。既要拿结果，又要惰性求值，只能用list(...)这个方式了。
另外,xrange代替range也能在一定程度上消减空间开销。

不过，我对list comprehension的求值中

这句话深表怀疑，即便使用range,按照常识推断，list comprehension的实现的空间展开耗用也就是x(外层)+y(内层),就把它直接当作两个嵌套的for循环，不至于是x*y的展开吧。
当然，没时间去看规范和具体实现.但从下面的代码

>>> x = [ x+y for x in range(1,1000000) for y in range(1,1000000) if (x+y)%19999
99999 == 0 ]

执行时的情况来看，我的机器的CPU始终在99-100%之间，但是内存耗用并没有直线上升，python进程的内存占用最终稳定在35M. 而如果参数完全展开的话，足以让我的机器直接趴下.
或者尝试不带if语句，直接生成那种规模的列表(相当于参数直接展看的空间耗用量)，我在python进程的内存耗用上涨到500M时及时将其终止。

因此，从这个侧面来说，python的list comprehension实现并没有做将未知数展开到先生成所有项即x*y(在这里是1000000*1000000)这样的程度。充其量也就是x+y级别(在分别变换几次内外层循环上限并观察内存耗用之后基本确认)和eager求值而已.

因此，并不是list comprehension的实现拙劣，而是主贴中在希望lazy求值的情形下用到了这个eager求值的方法。

有个小地方说错了：ruby并不支持list comprehension

关于我说的“拙劣的实现”，我早上起来脑中闪过 SICP 的练习 4.42，然后恍然大悟——太对不起各位了！
是这样的：对于解释器来说，不可能执行判断未知数计算复杂程度这样的高级优化，实践列表领悟的时候只能按顺序把它们转换为文章中第二个程序中 flatmap + map + filter 的版本。这个顺序是未知数的参考顺序（在列表领悟的形式部分之后给出的描述部分）：谁在前，先把谁 flatmap。也就是说，我们的第一个程序最后一句只要变成 [[ran] + rst for rst in queens(row, col - 1) for ran in range(row) if safe(ran, rst)] 问题就解决近了！我白白在这儿卖弄了一回列表领悟展开！
这给我们一个教训：以后用列表领悟的时候，哪个未知数难算，它的描述要先出现。
另外，我看了 LLS 的帖子之后想直接用 xrange() 代替 range()，发现没有。当然没有，只有一个函数是惰性的，其它函数都回 force 它求值。看到生成器之后，我又想用函数式的生成器——延续来做，转念一想：纯属浪费，还要生成大量额外的小函数。如果确实要用生成器的话，可以考虑变革整个程序的思想，看看能不能在函数式的主框架下用生成器。
PS: Ruby 没有列表领悟？很好，什么时候我来做一个。

列表领悟总感觉怪怪的，我还是喜欢叫列表推断

兄弟，你在给我们上python的基础概念课啊。pep202里面清楚的描述了list comprehension嵌套的含义:

对于多层无依赖循环，要把index计算量最大的放在外层.这是和list comprehension无关的一个基础知识点啊。


确实都是force求值，但是空间的耗用不一样。
但其实有那么一点点区别。range这个东西放在for .. in ..里面做种子时，是在循环定义时直接空间展开的，xrange则是类似于generator的做法。这是一个时间换空间的做法。
很明显，前面的那段代码

 x = [ x+y for x in range(1,1000000) for y in range(1,1000000) if if (x+y)%1999999999 == 0]

和xrange版本

 x = [ x+y for x in xrange(1,1000000) for y in xrange(1,1000000) if if (x+y)%1999999999 == 0]

虽然都是eager求值，但是内存的耗用上有着数量级的差别.运行的时候用taskmgr看一下就清楚了。
python3000貌似把两个统一了，废弃了xrange,但修改range的语义，做成一个iterator了。应该说python3000中的range更加类似于之前的xrange


确实没必要。如你前面所说，主贴中的问题并不是未知数空间展开的问题，而是重复计算内层循环index计算带来的时间复杂度，用generator消减不了这方面的开销。

generator也有表达式的形式，是使用(x for x in range(100))这样的表示就可以了

xrange与range好象是某个版本就一致了，不过记不清了。也就是range就是xrange的实现了。而且后续的python版本中，大量的是使用generator来代替以前的list comprehension的做法了。

xrange 只是为了兼容 老的版本才 不是返回一个iterator,你如果需要一个iterator，那就要iter(xrange())了， 估计后续的版本会直接返回一个iterator的.

PS;估计3k就是直接把range 换成直接 返回一个iterator了.

我来个js版本：

function queen(x, y) {
	if (x < y || y < 1) throw Error();
	
	var r = [];
	
	if (y == 1) {
		for (var i = 0; i < x; i++) {
			r.push([i]);
		}
		return r;
	}
	
	var r0 = queen(x, y - 1);
	for (var r0n = r0.length, r0i = 0; r0i < r0n; r0i++) {
		var a = r0[r0i];
		var n = a.length;
		var p = [];
		for (var i = 0, j = n; i < n; i++, j--) {
			p[a[i]] = true;
			p[a[i] + j] = true;
			p[a[i] - j] = true;
		}
		for (var i = 0; i < x; i++) {
			if (p[i]) continue;
			r.push(a.concat([i]));
		}
	}
	return r;
}