```
def printAns(row, col, ans):
map = []
for i in range(len(row)):
str = ""
for j in range(len(row)):
if row[i] == j:
str = str + 'Q'
else:
str = str + '.'
map.append(str)
ans.append(map)
def dfs(row, col, n, ans, t, add, menus):
if n == 0:
printAns(row, col, ans)
i = t - n
for j in range(t):
if col[j] == -1:
a = i + j
m = i - j + t
if add[a] == 0 and menus[m] == 0:
row[i] = j
col[j] = i
add[a] = 1
menus[m] = 1
dfs(row, col, n - 1, ans, t, add, menus)
add[a] = 0
menus[m] = 0
row[i] = -1
col[j] = -1
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
row = [-1 for i in range(n)]
col = [-1 for i in range(n)]
add = [0 for i in range(2*n+1)]
menus = [0 for i in range(2*n+1)]
ans = []
dfs(row, col, n, ans, n, add, menus)
return ans
```