n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：[["Q"]]
提示：
1 <= n <= 9- 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
Related Topics
题解
里面加了个printMap方法，可以看到每一步执行的情况。
大概的输出情况如下
o o o o
o o o o
o o o o
o o o o
-0--------------------
Q . . .
. . o o
. o . o
. o o .
-1--------------------
Q . . .
. . Q .
. . . .
. o . .
-2--------------------
Q . . .
. . . Q
. o . .
. . o .
-2--------------------
Q . . .
. . . Q
. Q . .
. . . .根据题意，和皇后棋的特性，米字型方向，长度无限的走法。那么我们可以得出一个初步的结论，要想在NxN的棋盘上放满N个皇后，那必然满足的条件是在每一行上有且只有一个皇后，在每一列上也是有且只有一个皇后。
按照这个思路我们就在棋盘上，从左上角，第一个格子开始排起，分别求出下一行可能的情况，如果下一行上摆放不了任何一个皇后棋子，那说明这个摆放方法是不可行的，就必须回退上一步，尝试另一种摆放方法。并按照这个规则，直至最后一行也能放下一颗皇后棋子，则说明这种摆放方法是可行的。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<List<String>> solveNQueens(int n) {
char[][] availableMap = new char[n][n];
for (int i = 0; i < n; i++) {
char[] a = new char[n];
//设为空 empty
Arrays.fill(a,'o');
availableMap[i] = a;
}
List<List<String>> res = new ArrayList<>();
resolve(res,availableMap,0);
// System.out.println(res);
return res;
}
// private void printMap(char[][] originMap, int row){
// return;
//// for (char[] chars : originMap) {
//// StringBuilder str = new StringBuilder();
//// for (char aChar : chars) {
//// str.append("\t\t").append(aChar);
//// }
//// System.out.println(str);
//// }
//// System.out.println("-"+row+"--------------------");
//// System.out.println("");
// }
private void resolve(List<List<String>> res,char[][] originMap,int row){
// 根据特征，我们以第一行的情况开始，每一行必定有一个，且一定只有一个，
// 不能满足这种情况的摆放方法，必然不能满足这种条件
int n = originMap.length;
// printMap(originMap,row);
for (int x = 0; x < n; x++){
boolean rowInsertQ = false;
//每一行，每一列的不同选择都会派生出不同的分支
char[][] map = cloneCharArr(originMap);
for (int i = 0; i < n; i++) {
if ( map[row][i] != 'o'){
continue;
}
if (i==x){
map[row][i] = 'Q';
rowInsertQ = true;
//那么对应的所有行上的第i列,和对应行上的斜线坐标格子 都是不可用状态,
for (int j = row+1; j < n; j++) {
map[j][i] = '.';
int left = i-(j-row);
int right = i+(j-row);
if (left >= 0 && map[j][left]=='o'){
map[j][left] = '.';
}
if (right <n && map[j][right]=='o'){
map[j][right] = '.';
}
}
}else{
map[row][i] = '.';
}
}
if (!rowInsertQ){
//这行不能插入新皇后，可以提前终止了
continue;
}
//有插入了新的皇后，可以向下一行探测,如果没有下一行则表示当前行已经是最后一行，那边添加进res中
if (row<n-1){
resolve(res,map,row+1);
}else{
toResult(res,map);
}
}
}
private char[][] cloneCharArr(char[][] map){
char[][] temp = new char[map.length][map[0].length];
for (int i = 0; i < map.length; i++) {
System.arraycopy(map[i], 0, temp[i], 0, map[0].length);
}
return temp;
}
private void toResult(List<List<String>> res, char[][]arr){
List<String> stringList = new ArrayList<>();
for (char[] chars : arr) {
stringList.add(new String(chars));
}
res.add(stringList);
}
}
//leetcode submit region end(Prohibit modification and deletion)补充个回溯
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<List<String>> solveNQueens(int n) {
char[][] chess = new char[n][n];
for (char[] chars : chess) {
Arrays.fill(chars, '.');
}
List<List<String>> res = new ArrayList<>();
solve(chess, res, 0);
return res;
}
private void solve(char[][] chess, List<List<String>> res, int row) {
if (row == chess.length) {
res.add(construct(chess));
return;
}
//从第⼀⾏开始找
for (int col = 0; col < chess.length; col++) {
//判断当前位置是否能放置皇后
if (valid(chess, row, col)) {
chess[row][col] = 'Q';
solve(chess, res, row + 1);
chess[row][col] = '.';
}
}
}
//判断当前位置是否能放置皇后
private boolean valid(char[][] chess, int row, int col) {
//通俗⼀点就是判断当前坐标位置的上⾯有没有皇后
for (int i = 0; i < row; i++) {
if (chess[i][col] == 'Q') return false;
}
//判断当前坐标的右上⾓有没有皇后
for (int i = row - 1, j = col + 1; i >= 0 && j < chess[i].length; i--, j++) {
if (chess[i][j] == 'Q') return false;
}
//判断当前坐标的左上⾓有没有皇后
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chess[i][j] == 'Q') return false;
}
return true;
}
// 数组转集合
private List<String> construct(char[][] chess) {
List<String> path = new ArrayList<>();
for (char[] chars : chess) {
path.add(new String(chars));
}
return path;
}
}
发表评论