forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathn-queens.py
More file actions
45 lines (37 loc) · 1.34 KB
/
n-queens.py
File metadata and controls
45 lines (37 loc) · 1.34 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def helper(row: int):
if row==n:
ans.append(convertFormat(queenCols))
return
for col in range(n):
posDiag = row+col
negDiag = row-col
if col in colUsed or posDiag in posDiagUsed or negDiag in negDiagUsed: continue
queenCols.append(col)
colUsed.add(col)
posDiagUsed.add(posDiag)
negDiagUsed.add(negDiag)
helper(row+1)
queenCols.pop()
colUsed.remove(col)
posDiagUsed.remove(posDiag)
negDiagUsed.remove(negDiag)
def convertFormat(queenCols: List[int]) -> List[str]:
output = []
for col in queenCols:
row = ''
for i in range(n):
if i==col:
row += 'Q'
else:
row += '.'
output.append(row)
return output
ans = []
queenCols = []
colUsed = set()
posDiagUsed = set()
negDiagUsed = set()
helper(0)
return ans