"八皇后"问题的Python解法
2016-06-15 14:20阅读：
解法一：利用递归和生成器
import random
def conflict(state,nextX):
nextY = len(state)
for i in range(nextY):
if
abs(nextX-state[i]) in (0, nextY-i):
return True
return False
def queens(num=8,state=()):
for pos in range(num):
if not
conflict(state,pos):
if len(state) == num-1:
yield
(pos,)
else:
for result
in queens(num,state + (pos,)):
yield (pos,) + result
def prettyprint(solution):
def line(pos, length =
len(solution)):
return
'.'*(pos) + 'X' + '.'*(length-pos-1)
for pos in solution:
print
line(pos)
prettyprint(random.choice(list(queens(8))))
其中函数conflict是检测下一个要放置的皇后，是否与之前放置的皇后位置冲突。nextX表示下一个皇后的X坐标，nextY表示Y坐标。条件判断语句写得很高端，是判断下一个皇后是否与前一个皇后的水平距离为0（即列相同），或者等于垂直距离（在一条对角线上）。注意最后一个return
False语句的缩进位置。
函数queens是主体部分。如果是最后一个皇后，执行完结束；如果不是，则进行递归。Python中的yield语句就是生成器。语句中(pos,)的逗号表示设置为元组而不是简单的加上括号。
函数prettyprint是简单的图形化输出。random表示随机选取一个解进行图示。因为八皇后问题有92组解。
==========
解法二：列表领悟特性
from itertools import permutations
for vec in permutations(range(8)):
if (8 == len(set(vec[i]+i for i in
range(8)))== len(set(vec[i]-i for i in range(8)))):
print
vec
更为简洁，只有两行代码。
其中vec[i]+i for i in range(8)等同于下列代码：
for i in range(8)
vec[i]+i
set()去掉其中重复的数字。
于是条件判断部分意义为：每个数加下标，与每个数减下标，如果它们都含有8个不同元素时，输出结果。
Python的这个特点被称为：列表领悟特性。只要给出列表中每一项的形式，以及需要满足的条件，自动生成列表。这也是近年来很多编程语言，例如Haskell，甚至JavaScript的共同特性。
