參考別人的算法做出了n皇后诚卸，開心。n皇后本質(zhì)是求矩陣中如何放棋子圣拄，使每行每列嘴秸，斜著的沒有同時放兩顆棋子。
用一維數(shù)列記錄棋子的位置，例如 [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
