递归法
- 用一个一维N元数组来存放每一行皇后的位置，这样就不存在行冲突了，只要判断哪一列可以放置就可以了，如果找到一个可以放置皇后的位置j后，则会递归探测下一行，结束后则会继续探测i行j+1列，故可以找到所有的N皇后的解。
class Solution:
#最后mark数组里面标记的是皇后的位置，例如mark[0] = 2, 表示第一行皇后放在第3列的位置
def make(self, mark):
#初始化数组
r = [['.' for _ in range(len(mark))] for _ in range(len(mark))]
#将每一行中皇后的位置用‘Q’代替
for i in mark:
r[i][mark[i]] = 'Q'
#枚举，将原来散的元素连接成字符串
for k, v in enumerate(r):
r[k] = ''.join(v)
return r
#递归函数，核心
def recursive(self, mark, cur, ret):
#如果当前行是最后一行，记录一个解，并返回上一级调用，继续探测
if cur == len(mark):
ret.append(self.make(mark))
return
#试探处理，将当前行的皇后应该在的位置遍历每一列，如果满足条件，递归调用处理下一行
for i in range(len(mark)):
mark[cur], down = i, True
for j in range(cur):
if mark[j] == i or abs(i-mark[j]) == cur - j:
down = False
break
if down:
self.recursive(mark, cur+1, ret)
def solveNQueens(self, n):
ret = []
self.recursive([None]*n, 0, ret)
return ret
enity = Solution()
print enity.solveNQueens(4)
