题目链接 : https://leetcode-cn.com/problems/n-queens/
题目描述:
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
思路:
回溯算法
记录 行, 列, 正对角,负对角,不能有两个以上的棋子.
如何判读是否在对角上呢?
正对角就是相加之和一样的
负对角就是相减只差一样的
关注我的的知乎专栏,了解更多的解题技巧,共同进步!
代码:
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
s = "." * n
def backtrack(i, tmp,col,z_diagonal,f_diagonal):
if i == n:
res.append(tmp)
return
for j in range(n):
if j not in col and i + j not in z_diagonal and i - j not in f_diagonal:
backtrack(i+1,tmp + [s[:j] + "Q" + s[j+1:]], col | {j}, z_diagonal |{i + j} , f_diagonal |{i - j} )
backtrack(0,[],set(),set(),set())
return res
public class NQueens {
public List<List<String>> solveNQueens(int n) {
Set<Integer> col = new HashSet<>();
Set<Integer> z_diagonal = new HashSet<>();
Set<Integer> f_diagonal = new HashSet<>();
List<List<String>> res = new ArrayList<>();
backtrack(0, n, res, new ArrayList<String>(), col, z_diagonal, f_diagonal);
return res;
}
private void backtrack(int i, int n, List<List<String>> res, ArrayList<String> tmp, Set<Integer> col, Set<Integer> z_diagonal, Set<Integer> f_diagonal) {
if (i == n) {
res.add(new ArrayList<>(tmp));
return;
}
for (int j = 0; j < n; j++) {
if (!col.contains(j) && !z_diagonal.contains(i + j) && !f_diagonal.contains(i - j)) {
col.add(j);
z_diagonal.add(i + j);
f_diagonal.add(i - j);
char[] s = new char[n];
Arrays.fill(s, '.');
s[j] = 'Q';
tmp.add(new String(s));
backtrack(i+1,n,res,tmp,col,z_diagonal,f_diagonal);
tmp.remove(tmp.size() - 1);
col.remove(j);
z_diagonal.remove(i + j);
f_diagonal.remove(i - j);
}
}
}
}