【常见面试算法】n皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
package Leetcode;
import java.util.ArrayList;
import java.util.List;
public class n皇后3刷 {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
if (n == 0) return res;
dfs(res, new ArrayList<>(),0,n);
return res;
}
private static void dfs(List<List<String>> res, List<String> list, int row, int n) {
if (row == n && list.size() == n) {
res.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < n; i++) {
if (isValid(list,i,n)) {
list.add(generateQ(i,n));
dfs(res,list,row + 1, n);
list.remove(list.size() - 1);
}
}
}
private static boolean isValid(List<String> list,int i, int n) {
for (int j = 0; j < list.size(); j++) {
if (list.get(j).charAt(i) == 'Q') return false;
}
for (int j = list.size() - 1, count = 1; j >= 0; j--, count++) {
if (i + count < n) {
if (list.get(j).charAt(i + count) == 'Q') return false;
}
if (i - count >= 0) {
if (list.get(j).charAt(i - count) == 'Q') return false;
}
}
return true;
}
private static String generateQ(int i, int n) {
StringBuilder res = new StringBuilder();
for (int j = 0; j < n; j++) {
if (j == i) {
res.append('Q');
} else {
res.append(".");
}
}
return res.toString();
}
}
查看12道真题和解析