问题描述：有N个皇后，需要放在N*N的棋盘上，同一行、同一列、同一对角线不能同时出现两个及以上的皇后，一共有多少种方法？
思路：
- 使用长度为N的向量a保存第I行的皇后所在的列的位置。
- 判断第i行第j列是否可以放置皇后的条件：
1、所在行所在列没有皇后，a的其他元素值没有为j的；
2、所在对角线没有皇后，abs(a[i]-col) == abs(row-i) - 逐行遍历
import numpy as np
def to_list(a):
l = []
for i in range(len(a)):
p = list('.' * len(a))
p[int(a[i])] = 'Q'
l.append(''.join(p))
return l
def is_valid(row, col, a, num_queen):
for i in range(num_queen):
if a[i] == col or (abs(a[i]-col) == abs(row-i)):
return 0
return 1
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
num_queen = n
a = np.ones(num_queen)*(-888)
i = j = 0
num_result = 0
result = []
while i < num_queen:
while j < num_queen:
#如果i行j列可以放皇后, 第i行找到位置放皇后
if is_valid(i, j, a, n):
a[i] = j
j = 0
break
else:
j += 1
#如果i行没有找到位置放皇后
if a[i] < 0:
if i==0:
break
else:
i -= 1
j = a[i] + 1
a[i] = -888
continue
#如果i行找到位置，如果是最后一行，说明找到了一个结果
if i == num_queen-1:
b = a.copy()
result.append(to_list(b))
num_result += 1
j = a[i] + 1
a[i] = -888
continue
#如果找到位置，且不是最后一行，寻找下一行
i += 1
return result
