The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
Example 1:
_ Q _ _ _ _ Q _
_ _ _ Q Q _ _ _
Q _ _ _ _ _ _ Q
_ _ Q _ _ Q _ _
Input: n = 4
Output: [
[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [["Q"]]
Constraints:
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def dfs(queens, dif_set, sum_set):
x = len(queens)
if x == n:
result.append(queens)
return
for y in range(n):
# whenever a location (x, y) is occupied,
# any other locations (p, q)
# where p + q == x + y or p - q == x - y
# would be invalid.
if (
y not in queens
and x-y not in dif_set
and x+y not in sum_set
):
dfs(
queens + [y],
dif_set | {x-y},
sum_set | {x+y}
)
result = []
dfs([], set(), set())
return [
['.'*i + 'Q' + '.'*(n-i-1) for i in sol]
for sol in result
]
'''
Back tracking
'''
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def backtrack(board, row):
if row == n:
res.append([''.join(r) for r in board])
return
for col in range(n):
if not is_valid(board, row, col):
continue
board[row][col] = 'Q'
backtrack(board, row + 1)
board[row][col] = '.'
def is_valid(board, row, col):
# check column
for i in range(row+1):
if board[i][col] == 'Q':
return False
i, j = row - 1, col + 1
# check top-right
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
i, j = row - 1, col - 1
# check top-left
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
return True
res = []
board = [['.'] * n for i in range(n)]
backtrack(board, 0)
return res
|