```
class Solution:
# @return a list of lists of string
def solveNQueens(self, n):
self.result=[] # stores the position of Queens at each row
for i in range(n):
self.check([i],n)
return self.output(self.result,n)
def check(self, Qs,n):
ql=len(Qs)
if ql==n: # the condition to end
self.result.append(Qs)
return
for i in range(n): # the loop of choosing the current pos
if i in Qs: # should not be another Queen in the same column
continue
else:
success=True
for j,Qj in enumerate(Qs):
# the key requirement to continue to next row
# namely we do not accept a previous Queen which already occupied a
# diagonal line of the current position
if i==Qj+ql-j or i==Qj-ql+j:
success=False
break
if success: # Qj loop finishes
Qs2=Qs[:] # a copy of Qs
Qs2.append(i)
self.check(Qs2,n)
def output(self,Qs,n):
out=[]
for qs1 in Qs: # qs1 is a list
temp1=[]
for i in qs1:
temp=''
temp+='.'*i + 'Q' + '.'*(n-i-1)
temp1.append(temp)
out.append(temp1)
return out
```