# Python 69 ms,97.62%,use backtracking

• ``````class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
res = [] # result
row = [] # row[i] = k,  Q of i-th row should be placed in the k-th column, store the correct column position Q
col = [False] * n # column visited
dia1 = [False] * (2 * n - 1) # diangle1, /
dia2 = [False] * (2 * n - 1) # \
self.putQueen(n, 0, row, res, col, dia1, dia2)
return res

def putQueen(self, n, index, row, res, col, dia1, dia2):
if index == n:
res.append(self.generateBoard(n, row))
return
for i in range(n):
# index row , i cloumn
if not col[i] and not dia1[index+i] and not dia2[index-i+(n-1)]:
row.append(i)
col[i] = True
dia1[index+i] = True
dia2[index - i + (n - 1)] = True
self.putQueen(n, index+1, row, res, col, dia1, dia2)
col[i] = False
dia1[index + i] = False
dia2[index - i + (n - 1)] = False
row.pop()
return

def generateBoard(self, n, row):
if len(row) != n:
return False
board = [["."] * n for _ in range(n)]
for i in range(n):
board[i][row[i]] = "Q"
board[i] = "".join(board[i])
return board
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.