-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode 51.py
38 lines (31 loc) · 1.07 KB
/
LeetCode 51.py
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
class Solution:
def solveNQueens(self, n):
if n < 1: return []
self.result = []
self.cols = set(); self.pie = set(); self.na = set()
self.DFS(n, 0, [])
# return self.result
return self.generate(n)
def DFS(self, n, row, cur_state):
if row >= n:
self.result.append(cur_state)
return
for col in range(n):
if col in self.cols or row + col in self.pie or row - col in self.na:
continue # <- go die!
self.cols.add(col)
self.pie.add(row + col)
self.na.add(row - col)
self.DFS(n, row + 1, cur_state + [col])
self.cols.remove(col)
self.pie.remove(row + col)
self.na.remove(row - col)
def generate(self, n):
board = []
for res in self.result:
for i in res:
board.append("." * i + "Q" + "." * (n - i - 1))
return [board[i: i + n] for i in range(0, len(board), n)]
s = Solution()
result = s.solveNQueens(4)
print(result)