forked from luliyucoordinate/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0051.py
37 lines (31 loc) · 1.16 KB
/
0051.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
class Solution:
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
result, R, col, dia1, dia2 = list(), list(), list(), list(), list()
col = [0 for i in range(n)]
dia1 = [0 for i in range(2*n - 1)]
dia2 = [0 for i in range(2*n - 1)]
def generateBoard(m, row):
board = [str() for i in range(n)]
for i in range(m):
board[i] = row[i]*'.' + 'Q' + '.'*(m - row[i] - 1)
return board
def putQueen(m, index, row):
if index == m:
result.append(generateBoard(m, row))
return
for i in range(m):
if not (col[i] or dia1[index + i] or dia2[index - i + m - 1]):
row.append(i)
col[i], dia1[index + i], dia2[index - i + m - 1] = 1, 1, 1
putQueen(m, index + 1, row)
col[i], dia1[index + i], dia2[index - i + m - 1] = 0, 0, 0
row.pop()
putQueen(n, 0, R)
return result
if __name__ == '__main__':
n = 4
print(Solution().solveNQueens(n))