参考别人的算法做出了n皇后，开心。n皇后本质是求矩阵中如何放棋子，使每行每列，斜着的没有同时放两颗棋子。
用一维数列记录棋子的位置，例如 [1,2,3,0]就表示4*4的期盼中，第一行放在第一列，第二行放第二列，第三行放第三列，第四行放第零列。然后用dfs和backtracking去放每一行，直到放到最后一行。
python代码：
class Solution:
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
pos = [-1] * n
usedcol = set()
useddia = set()
output = []
self.dfs(n, pos, usedcol, useddia, output, 0)
res = []
for i in range(len(output)):
res.append([])
for j in output[i]:
string = ['.']*n
string[j] = 'Q'
res[i].append(''.join(string))
return res
def dfs(self, n, pos, usedcol, useddia, output, index):
if index >= n:
output.append(list(pos))
return
for i in range(n):
if i not in usedcol and not self.isdia(index, i, useddia):
pos[index] = i
usedcol.add(i)
useddia.add((index, i))
self.dfs(n, pos, usedcol, useddia, output, index+1)
usedcol.remove(i)
useddia.remove((index, i))
return
def isdia(self, i, j, useddia):
for pos_x, pos_y in useddia:
if abs(i - pos_x) == abs(j - pos_y):
return True
return False
