6
【算法】给你一个整数 n ，返回所有不同的 n 皇后问题
source link: https://blog.51cto.com/u_15312559/5811236
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
【算法】给你一个整数 n ，返回所有不同的 n 皇后问题
精选 原创n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互吃子。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
输入：n = 1
输出：[[“Q”]]
提示：
1 <= n <= 9
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
以下程序实现了这一功能，请你填补空白处内容：
import java.util.List;
import java.util.ArrayList;
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<List<String>>();
int[] queenList = new int[n];
placeQueen(queenList, 0, n, res);
return res;
}
private void placeQueen(int[] queenList, int row, int n, List<List<String>> res) {
if (row == n) {
ArrayList<String> list = new ArrayList<String>();
for (int i = 0; i < n; i++) {
String str = "";
for (int col = 0; col < n; col++) {
if (queenList[i] == col) {
str += "Q";
} else {
str += ".";
}
}
list.add(str);
}
res.add(list);
}
for (int col = 0; col < n; col++) {
if (isValid(queenList, row, col)) {
queenList[row] = col;
________________________;
}
}
}
private boolean isValid(int[] queenList, int row, int col) {
for (int i = 0; i < row; i++) {
int pos = queenList[i];
if (pos == col) {
return false;
}
if (pos + row - i == col) {
return false;
}
if (pos - row + i == col) {
return false;
}
}
return true;
}
}
空白处填入的代码如下
placeQueen(queenList, row + 1, n, res);
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK