<div><p>The <strong>n-queens</strong> puzzle is the problem of placing <code>n</code> queens on an <code>n x n</code> chessboard such that no two queens attack each other.</p>
<p>Given an integer <code>n</code>, return <em>all distinct solutions to the <strong>n-queens puzzle</strong></em>. You may return the answer in <strong>any order</strong>.</p>
<p>Each solution contains a distinct board configuration of the n-queens' placement, where <code>'Q'</code> and <code>'.'</code> both indicate a queen and an empty space, respectively.</p>
<p> </p> <p><strong>Example 1:</strong></p> <img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/queens.jpg" style="width: 600px; height: 268px;"> <pre><strong>Input:</strong> n = 4 <strong>Output:</strong> [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] <strong>Explanation:</strong> There exist two distinct solutions to the 4-queens puzzle as shown above </pre>
<p><strong>Example 2:</strong></p>
<pre><strong>Input:</strong> n = 1 <strong>Output:</strong> [["Q"]] </pre>
<p> </p> <p><strong>Constraints:</strong></p>
<ul> <li><code>1 <= n <= 9</code></li> </ul> </div>
题目大意：
八皇后问题，求所有解
Global dict算法思路(推荐)：
DFS填位法模板
注意事项：
- 用3个set，col_set, 对角线，反对角线set来提高效率。
- path用append的方法加入，这样终止条件用n来比较，不能用len(path)
- 打印函数中，one_result在每轮后reset；字符串不能改其中一个，只能用子串+Q+子串： ('.' * path[i]) + 'Q' + ('.' * (n - path[i] - 1))
Python代码：
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
27def solveNQueens(self, n: int) -> List[List[str]]:
res, path = [], []
self.dfs(n, 0, path, res, set(), set(), set())
result = self.convert(res)
return result
def dfs(self, n, start, path, res, col_set, diag_set, anti_diag_set):
if start == n: # remember not len(path)
res.append(list(path))
return
for i in range(n): # 4
if not self.is_valid(start, i, col_set, diag_set, anti_diag_set):
continue
path.append(i) # [0, 2]
col_set.add(i)
diag_set.add(start - i)
anti_diag_set.add(start + i)
self.dfs(n, start + 1, path, res, col_set, diag_set, anti_diag_set)
anti_diag_set.remove(start + i)
diag_set.remove(start - i)
col_set.remove(i)
path.pop()
def is_valid(self, i, val, col_set, diag_set, anti_diag_set):
if val in col_set or i - val in diag_set or i + val in anti_diag_set:
return False
return True
算法分析：
时间复杂度为O(n x n!)，解大小乘以path长度,空间复杂度O(n^2)
常数空间算法II解题思路(推荐)：
较直观的方法，但复杂度稍差
Python代码：
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
38def solveNQueens2(self, n: int) -> List[List[str]]:
res, path = [], []
self.dfs2(n, 0, path, res)
result = self.convert(res)
return result
def dfs2(self, n, start, path, res):
if start == n: # remember not len(path)
res.append(list(path))
return
for i in range(n): # 4
path.append(i) # [0, 2]
if self.is_valid2(path):
self.dfs2(n, start + 1, path, res)
path.pop()
def is_valid2(self, path):
if len(path) != len(set(path)):
return False
for i in range(len(path)):
for j in range(i + 1, len(path)):
#if i == j:
# continue
if abs(i - j) == abs(path[i] - path[j]):
return False
return True
def convert(self, res):
result, one_result = [], []
for k in range(len(res)):
one_result = [] # remember
path = res[k]
n = len(path)
for i in range(n):
s = ('.' * path[i]) + 'Q' + ('.' * (n - path[i] - 1)) # remember not s[path[i]] = 'Q'
one_result.append(s)
result.append(one_result)
return result
Java代码：
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
33public List<List<String>> solveNQueens2(int n) {
List<List<String>> res = new ArrayList<>();
int[] col = new int[n];
solveR(n, col, 0, res);
return res;
}
// 5/2/2020
void solveR(int n, int[] col, int st, List<List<String>> res) {
if(st == n) {
print(col, res);
return;
}
for(int i = 0; i < n; i++) {
col[st] = i;
if(isValid(col, st))
solveR(n, col, st + 1, res);
}
}
boolean isValid(int[] col, int k) {
for(int i = 0; i < k; i++) {
if(col[i] == col[k])
return false;
}
for(int i = 0; i < k; i++) {
if(Math.abs(k - i) == Math.abs(col[k] - col[i])) //use abs
return false;
}
return true;
}
算法分析：
时间复杂度为O(n x n!)，空间复杂度O(n^2)
