```
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
solutions, ans = [], []
self.helper(solutions, 0, n, [])
for solution in solutions:
matrix = [['.']*n for _ in range(n)]
for (x,y) in solution:
matrix[x][y] = 'Q'
ans.append([''.join(line) for line in matrix])
return ans
def helper(self, solutions, i, n, temp):
if i == n:
solutions.append(temp[:])
for j in range(n):
if self.valid(i,j,temp):
self.helper(solutions, i+1, n, temp+[(i,j)])
def valid(self,i,j,temp):
for a, b in temp:
if b == j:
return False
if i-a == abs(j-b):
return False
return True
```