问题描述：
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。
解法：
最初的想法是暴力解法，即每一步都有8*8种可能性，8步棋的时间复杂度为。然后按照当前这步棋不能与前面所有棋冲突的原则，排除掉不合法的下法。这种方法的时间复杂度过高。
但其实仔细思考下这个问题，就会发现其独特性：那就是棋子总共有8个，而棋盘总共为8行8列。也就是说所有的棋子必然在不同行，同时也必然在不同列。每行都有且只有一个棋子，否则就是不合法的。这个规律可以极大的缩小搜索空间，比如：第一行必然有一个棋子，该棋子只有8个可选格子，而不是64个。
据此可以整理出如下算法流程：整体思路是采用回溯算法，逐行搜索合法的棋子位置，合法的标准是当前行棋子不与之前的行冲突。
- 如果当前行号cur==8，则表明已经生成了8个合法的棋子位置，输出对应数组lst。
- 如果当前行号cur==0，此时棋盘上没有棋子，首行8个位置全都是合法的。
- 对于首行的每个合法棋子，采用回溯算法计算下一行的合法棋子位置，即queen(lst,cur+1)。
- 如果cur>0且cur!=8，则需要判断当前行可选的8个棋格中，哪些与此前已有的棋子是不冲突的。
- 只要与已有棋子中的任意一个冲突，则不合法，可以跳出尝试下一个位置。
- 如果与已有棋子全都不冲突，则找到一个当前行合法的位置，将其记录下来。并且用回溯算法计算下一行的合法位置。
cnt=0
# lst是1*8的输出数组，代表棋子在各行的位置，lst中元素的索引表示对应的行号
# cur代表当前行号
def queen(lst,cur):
# 第9行
global cnt
if cur==8:
print lst,cnt
cnt+=1
return
# 首行特殊处理
if cur==0:
for col in range(8):
lst[cur]=col
queen(lst,cur+1)
else:
# 对每一行cur，搜索各列
for col in range(8):
# 标志位必须放在下一层循环外
tag=True
# 对于内层循环中的每一个元素（对应此前的所有棋子），当前行都必须与其不冲突
for i,j in enumerate(lst[:cur]):
# 如果冲突：列相同，或者在同一斜线上
# 注意，不能abs(j-i)==abs(col-cur)，这样会过滤掉合法结果
if col==j or j-i==col-cur or (i+j)==(cur+col):
tag=False
break #跳出内层循环
# 如果不冲突
if tag:
lst[cur]=col
queen(lst,cur+1)#搜索下一层
queen([None]*8,0)
