N皇后
难度：困难
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
**注意：**leetcode上有两个n皇后，难度都是困难，其实处理没什么区别，都可以采用回溯法，一个是返回List，一个是返回数字。
这里将题目修改为输出：个数 + List，如果你只需要返回List或者返回数字，可以将代码删去不需要的，进一步提高效率节省内存。
示例:
输入: 4
输出:
2
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
# 解释: 4 皇后问题存在两个不同的解法。
提示：
官方解法的速度
本次解法（单纯返回List）的速度
思路介绍
理解该题解法之前，你需要对深度优先搜索有一定了解。
深度优先搜索：从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。
三个判断条件来决定该位置是否可以放置皇后：
假设一个前提，坐标为 [ i , j ]
- 该列 没有皇后：列
i的坐标即可表示，很直观 - 左下 到 右上 没有皇后：使用
i + j作为下标判断是否有皇后 - 左上 到 右下 没有皇后：使用
i - j + n作为下标判断是否有皇后
注意：由于我们是一行一行找，所以不需要判断改行是否有皇后了
存储数据说明：
boolean[] down; //左下 到 右上
boolean[] up;//左上 到 右下
boolean[] col;//列
int n;
boolean[][] visited;//是否有皇后
//List版本
List<List<String>> res = new ArrayList<>();
//数字版
int sum = 0;
因为是N个棋盘及N个皇后，所以每一行都会有一个皇后，首先初始化第一行的不同放置方式：
void start(int n) {
this.n = n;
down = new boolean[2 * n + 1];//防止越界
up = new boolean[2 * n + 1];//防止越界
col = new boolean[n + 1];
visited = new boolean[n + 1][n + 1];
//初始化
Arrays.fill(down, false);
Arrays.fill(up, false);
Arrays.fill(col, false);
for (int j = 1; j <= n; j++) {
Arrays.fill(visited[j], false);
}
//第一行的不同防止方式
for (int i = 1; i <= n; i++) {
visited[1][i] = true;
col[i] = true;
down[1 + i] = true;
up[1 - i + n] = true;
dfs(2);//从第二行开始，不断深入！
visited[1][i] = false;
col[i] = false;
down[1 + i] = false;
up[1 - i + n] = false;
}
}
接下来我们要寻找第二行是否有可以放置的，如果有就继续进入k+1（下一行），继续寻找。直到第n行都完成了摆放，那么就可以对需要返回的结果作出修改
void dfs(int k) {
if (k == n + 1) {
//List版本
ArrayList<String> strings = new ArrayList<>();
for (int i = 1; i <= n; i++) {
//采用StringBuilder又快又好，可以深入了解一下java中String不可变性
StringBuilder s = new StringBuilder();
for (int j = 1; j <= n; j++) {
if (visited[i][j]) s.append('Q');
else s.append('.');
}
strings.add(s.toString());
}
res.add(strings);
//数字版本
sum += 1;
return;
}
for (int i = 1; i <= n; i++) {
if (col[i] || down[k + i] || up[k - i + n]) continue;
visited[k][i] = true;
col[i] = true;
down[k + i] = true;
up[k - i + n] = true;
dfs(k + 1);
visited[k][i] = false;
col[i] = false;
down[k + i] = false;
up[k - i + n] = false;
}
}
详细代码（附带输入测试）：
只需要删除测试模块即可通过leetcode中两道N皇后的题目，不过理解后自己写一遍才有用，复制黏贴不可取!
/***
* @author: G_night
* 转载请声明作者
* Reprint please state the author
***/
import java.util.*;
class Solution {
boolean[] down;
boolean[] up;
boolean[] col;
int n;
boolean[][] visited;
//List版本
List<List<String>> res = new ArrayList<>();
//数字版
int sum = 0;
//返回数字版
public int totalNQueens(int n) {
//初始化数据并设置最初的位置
start(n);
return sum;
}
//返回List版本
public List<List<String>> solveNQueens(int n) {
//初始化数据并设置最初的位置
start(n);
return res;
}
void start(int n) {
this.n = n;
down = new boolean[2 * n + 1];
up = new boolean[2 * n + 1];
col = new boolean[n + 1];
visited = new boolean[n + 1][n + 1];
//初始化
Arrays.fill(down, false);
Arrays.fill(up, false);
Arrays.fill(col, false);
for (int j = 1; j <= n; j++) {
Arrays.fill(visited[j], false);
}
for (int i = 1; i <= n; i++) {
visited[1][i] = true;
col[i] = true;
down[1 + i] = true;
up[1 - i + n] = true;
dfs(2);
//重新恢复false防止之前的造成影响
visited[1][i] = false;
col[i] = false;
down[1 + i] = false;
up[1 - i + n] = false;
}
}
void dfs(int k) {
if (k == n + 1) {
//List版本
ArrayList<String> strings = new ArrayList<>();
for (int i = 1; i <= n; i++) {
StringBuilder s = new StringBuilder();
for (int j = 1; j <= n; j++) {
if (visited[i][j]) s.append('Q');
else s.append('.');
}
strings.add(s.toString());
}
res.add(strings);
//数字版本
sum += 1;
return;
}
for (int i = 1; i <= n; i++) {
if (col[i] || down[k + i] || up[k - i + n]) continue;
visited[k][i] = true;
col[i] = true;
down[k + i] = true;
up[k - i + n] = true;
dfs(k + 1);
visited[k][i] = false;
col[i] = false;
down[k + i] = false;
up[k - i + n] = false;
}
}
}
//测试
class try {
public static void main(String[] args) {
int n=4;
System.out.println(new Solution().totalNQueens(n));
System.out.println(new Solution().solveNQueens(n));
}
}
后记
这个只是一种解法，其实还有更简单的判断方式（使用bigmap思维），不过面试中这个方法好理解也容易想到并解释。这道题在以前大一的时候作为学校的选修考题之一，虽然写着困难的难度，其实理解和实操都是比较简单的。
转载：https://blog.csdn.net/weixin_44626319/article/details/106745055
查看评论