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
|
class Solution:
res = []
def backtrack(self, n: int, row: int, chessboard: List[List[str]]):
if row == n:
temp_res = []
for temp in chessboard:
temp_str = ''.join(temp)
temp_res.append(temp_str)
self.res.append(temp_res)
return
for col in range(n):
if self.isValid(n, row, col, chessboard):
chessboard[row][col] = 'Q'
self.backtrack(n, row + 1, chessboard)
chessboard[row][col] = '.'
def isValid(self, n: int, row: int, col: int, chessboard: List[List[str]]):
for i in range(row):
if chessboard[i][col] == 'Q':
return False
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if chessboard[i][j] == 'Q':
return False
i -= 1
j -= 1
i, j = row - 1, col + 1
while i >= 0 and j < n:
if chessboard[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def solveNQueens(self, n: int) -> List[List[str]]:
self.res.clear()
chessboard = [['.' for _ in range(n)] for _ in range(n)]
self.backtrack(n, 0, chessboard)
return self.res
|