LeetCode-51. N 皇后
2020-09-032020-09-04
问题地址
LeetCode51. N 皇后
问题描述
规则
- $n$ 皇后问题研究的是如何将 $n$ 个皇后放置在 $n×n$ 的棋盘上，并且使皇后彼此之间不能相互攻击。
-
上图为 8 皇后问题的一种解法。
- 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
- 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例1
输入：4
输出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
提示
- 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
解析
解题思路
- 遍历n×n棋盘，根据约束条件摆放皇后，根据结束条件结束递归
- 约束条件：任何两个皇后都不能处于同一条横行、纵行或斜线上
- 结束条件：
- 当每一行都成功放下了一个皇后时，说明得到了一个合法的解法
- 当棋盘遍历结束，已放置的皇后数量<皇后总数量则该解法不合法
复杂度分析
- 时间复杂度，O(N!)，其中 N 是皇后数量。
- 空间复杂度，O(N)，其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 N，数组的长度为 N，每个集合的元素个数都不会超过 N。
数据操作分析
编码实现
官方解法
前言
- 「N 皇后问题」研究的是如何将 N 个皇后放置在 N \times N 的棋盘上，并且使皇后彼此之间不能相互攻击。
- 皇后的走法是：可以横直斜走，格数不限。因此要求皇后彼此之间不能相互攻击，等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。
- 直观的做法是暴力枚举将 NN 个皇后放置在 N \times N 的棋盘上的所有可能的情况，并对每一种情况判断是否满足皇后彼此之间不相互攻击。暴力枚举的时间复杂度是非常高的，因此必须利用限制条件加以优化。
- 显然，每个皇后必须位于不同行和不同列，因此将 N 个皇后放置在N \times N 的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。基于上述发现，可以通过回溯的方式寻找可能的解。
- 回溯的具体做法是：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后。每次新放置的皇后都不能和已经放置的皇后之间有攻击：即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并更新数组中的当前行的皇后列下标。当 N 个皇后都放置完毕，则找到一个可能的解。当找到一个可能的解之后，将数组转换成表示棋盘状态的列表，并将该棋盘状态的列表加入返回列表。
- 由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有 NN 列可以选择，第二个皇后最多有 N-1 列可以选择，第三个皇后最多有 N-2 列可以选择（如果考虑到不能在同一条斜线上，可能的选择数量更少），因此所有可能的情况不会超过 N! 种，遍历这些情况的时间复杂度是 O(N!)。
- 为了降低总时间复杂度，每次放置皇后时需要快速判断每个位置是否可以放置皇后，显然，最理想的情况是在 O(1) 的时间内判断该位置所在的列和两条斜线上是否已经有皇后。
- 以下两种方法分别使用集合和位运算对皇后的放置位置进行判断，都可以在 O(1) 的时间内判断一个位置是否可以放置皇后，算法的总时间复杂度都是 O(N!)。
基于集合的回溯
思路：
- 为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 \textit{columns}、\textit{diagonals}_1 和 \textit{diagonals}_2 分别记录每一列以及两个方向的每条斜线上是否有皇后。
- 列的表示法很直观，一共有 N 列，每一列的下标范围从 0 到 N-1，使用列的下标即可明确表示每一列。
- 如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。
- 方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
- 方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0) 和 (1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。
- 每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。
复杂度分析：
- 时间复杂度，O(N!)，其中 N 是皇后数量。
- 空间复杂度，O(N)，其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 N，数组的长度为 N，每个集合的元素个数都不会超过 N。
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> solutions = new ArrayList<List<String>>();
int[] queens = new int[n];
Arrays.fill(queens, -1);
Set<Integer> columns = new HashSet<Integer>();
Set<Integer> diagonals1 = new HashSet<Integer>();
Set<Integer> diagonals2 = new HashSet<Integer>();
backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
return solutions;
}
public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
if (row == n) {
List<String> board = generateBoard(queens, n);
solutions.add(board);
} else {
for (int i = 0; i < n; i++) {
if (columns.contains(i)) {
continue;
}
int diagonal1 = row - i;
if (diagonals1.contains(diagonal1)) {
continue;
}
int diagonal2 = row + i;
if (diagonals2.contains(diagonal2)) {
continue;
}
queens[row] = i;
columns.add(i);
diagonals1.add(diagonal1);
diagonals2.add(diagonal2);
backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
queens[row] = -1;
columns.remove(i);
diagonals1.remove(diagonal1);
diagonals2.remove(diagonal2);
}
}
}
public List<String> generateBoard(int[] queens, int n) {
List<String> board = new ArrayList<String>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[queens[i]] = 'Q';
board.add(new String(row));
}
return board;
}
}
基于位运算的回溯
思路：
- 方法一使用三个集合记录分别记录每一列以及两个方向的每条斜线上是否有皇后，每个集合最多包含 N 个元素，因此集合的空间复杂度是 O(N)。如果利用位运算记录皇后的信息，就可以将记录皇后信息的空间复杂度从 O(N) 降到 (1)。
- 具体做法是，使用三个整数 \textit{columns}、\textit{diagonals}_1 和 \textit{diagonals}_2 分别记录每一列以及两个方向的每条斜线上是否有皇后，每个整数有 NN 个二进制位。棋盘的每一列对应每个整数的二进制表示中的一个数位，其中棋盘的最左列对应每个整数的最低二进制位，最右列对应每个整数的最高二进制位。
- 那么如何根据每次放置的皇后更新三个整数的值呢？在说具体的计算方法之前，首先说一个例子。
- 棋盘的边长和皇后的数量 N=8。如果棋盘的前两行分别在第 2 列和第 4 列放置了皇后（下标从 0 开始），则棋盘的前两行如下图所示。
- 如果要在下一行放置皇后，哪些位置不能放置呢？我们用 00 代表可以放置皇后的位置，11 代表不能放置皇后的位置。
- 新放置的皇后不能和任何一个已经放置的皇后在同一列，因此不能放置在第 2 列和第 4 列，对应 \textit{columns}=00010100_{(2)} 。
- 新放置的皇后不能和任何一个已经放置的皇后在同一条方向一（从左上到右下方向）的斜线上，因此不能放置在第 4 列和第 5 列，对应 diagonals_1=00110000_{(2)} 。其中，第 4 列为其前两行的第 2 列的皇后往右下移动两步的位置，第 5 列为其前一行的第 4 列的皇后往右下移动一步的位置。
- 新放置的皇后不能和任何一个已经放置的皇后在同一条方向二（从右上到左下方向）的斜线上，因此不能放置在第 0 列和第 3 列，对应 diagonals_2=00001001_{(2)} 。其中，第 0 列为其前两行的第 2 列的皇后往左下移动两步的位置，第 3 列为其前一行的第 4 列的皇后往左下移动一步的位置。
- 由此可以得到三个整数的计算方法：
- 初始时，三个整数的值都等于 00，表示没有放置任何皇后；
- 在当前行放置皇后，如果皇后放置在第 i 列，则将三个整数的第 i 个二进制位（指从低到高的第 i 个二进制位）的值设为 1；
- 进入下一行时，\textit{columns} 的值保持不变，\textit{diagonals}_1 左移一位，\textit{diagonals}_2 右移一位，由于棋盘的最左列对应每个整数的最低二进制位，即每个整数的最右二进制位，因此对整数的移位操作方向和对棋盘的移位操作方向相反（对棋盘的移位操作方向是 \textit{diagonals}_1 右移一位，\textit{diagonals}_2 左移一位）。
- 思路分析：以 4 皇后问题为例，它的「搜索」过程如下。大家可以在纸上模拟下面这个过程：
- 每次放置皇后时，三个整数的按位或运算的结果即为不能放置皇后的位置，其余位置即为可以放置皇后的位置。可以通过 (2^n-1)~\&~(\sim(\textit{columns} | \textit{diagonals}_1 | \textit{diagonals}_2)) 得到可以放置皇后的位置（该结果的值为 1 的位置表示可以放置皇后的位置），然后遍历这些位置，尝试放置皇后并得到可能的解。
- 遍历可以放置皇后的位置时，可以利用以下两个按位与运算的性质：
- $x~\&~(-x)$ 可以获得 x 的二进制表示中的最低位的 1 的位置；
- $x~\&~(x-1)$ 可以将 x 的二进制表示中的最低位的 1 置成 0。
- 具体做法是，每次获得可以放置皇后的位置中的最低位，并将该位的值置成 0，尝试在该位置放置皇后。这样即可遍历每个可以放置皇后的位置。
复杂度分析：
- 时间复杂度，O(N!)，其中 N 是皇后数量。
- 空间复杂度，O(N)，其中 N 是皇后数量。由于使用位运算表示，因此存储皇后信息的空间复杂度是 O(1)，空间复杂度主要取决于递归调用层数和记录每行放置的皇后的列下标的数组，递归调用层数不会超过 N，数组的长度为 N。
class Solution {
public List<List> solveNQueens(int n) {
int[] queens = new int[n];
Arrays.fill(queens, -1);
List<List> solutions = new ArrayList<List>();
solve(solutions, queens, n, 0, 0, 0, 0);
return solutions;
}
public void solve(List<List> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
if (row == n) {
List board = generateBoard(queens, n);
solutions.add(board);
} else {
int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
while (availablePositions != 0) {
int position = availablePositions & (-availablePositions);
availablePositions = availablePositions & (availablePositions - 1);
int column = Integer.bitCount(position - 1);
queens[row] = column;
solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) <> 1);
queens[row] = -1;
}
}
}
public List generateBoard(int[] queens, int n) {
List board = new ArrayList();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[queens[i]] = 'Q';
board.add(new String(row));
}
return board;
}
}
小结
- 回顾这道题，拿到这道题的时候，其实我们很容易看出需要使用枚举的方法来求解这个问题，当我们不知道用什么办法来枚举是最优的时候，可以从下面三个方向考虑：
- 子集枚举：可以把问题转化成「从 n^2 个格子中选一个子集，使得子集中恰好有 n 个格子，且任意选出两个都不在同行、同列或者同对角线」，这里枚举的规模是 2^{n^2} ；
- 组合枚举：可以把问题转化成「从 n^2 个格子中选择 n 个，且任意选出两个都不在同行、同列或者同对角线」，这里的枚举规模是 {n^2} \choose {n} ；
- 排列枚举：因为这里每行只能放置一个皇后，而所有行中皇后的列号正好构成一个 1 到 n 的排列，所以我们可以把问题转化为一个排列枚举，规模是 n!。
- 带入一些 n 进这三种方法验证，就可以知道那种方法的枚举规模是最小的，这里我们发现第三种方法的枚举规模最小。这道题给出的两个方法其实和排列枚举的本质是类似的。
精彩评论
跳转地址：回溯算法（转换成全排列问题 + 剪枝）- 题解后有相关问题
递归 思路
- 一句话题解：回溯算法是一种遍历算法，以 深度优先 遍历 的方式尝试所有的可能性。有些教程上也叫「暴力搜索」。回溯算法是 有方向地 搜索，区别于多层循环实现的暴力法。
许多复杂的、规模较大的问题都可以使用回溯法，有「通用解题方法」的美称。（来自 百度百科）
- 说明：
- N 皇后问题很多时候作为例题出现在教科书中，可以当做理解回溯算法的例题进行学习；
- 对于回溯算法还比较陌生的朋友，可以参考我的题解 《回溯算法入门级详解 + 练习（持续更新）》。
- 思路分析：以 4 皇后问题为例，它的「搜索」过程如下。大家可以在纸上模拟下面这个过程：
理解树形结构
先尝试画出递归树，以 4 皇后问题为例，画出的递归树如下：
- 搜索的过程蕴含了 剪枝 的思想。「剪枝」的依据是：题目中给出的 「N 皇后」 的摆放规则：1、不在同一行；2、不在同一列；3、不在同一主对角线方向上；4、不在同一副对角线方向上。
小技巧：记住已经摆放的皇后的位置
- 这里记住已经摆放的位置不能像 Flood Fill 一样，简单地使用 visited 布尔数组。放置的规则是：一行一行考虑皇后可以放置在哪一个位置上，某一行在考虑某一列是否可以放置皇后的时候，需要根据前面已经放置的皇后的位置。
- 由于是一行一行考虑放置皇后，摆放的这些皇后肯定不在同一行，为了避免它们在同一列，需要一个长度为 NN 的布尔数组 cols，已经放置的皇后占据的列，就需要在对应的列的位置标注为 True。
考虑对角线（找规律）
- 下面我们研究一下主对角线或者副对角线上的元素有什么特性。在每一个单元格里写下行和列的 下标。
-
为了保证至少两个皇后不同时出现在 同一主对角线方向 或者 同一副对角线方向。检查策略是，只要「检测」到新摆放的「皇后」与已经摆放好的「皇后」冲突，就尝试摆放同一行的下一个位置，到行尾还不能放置皇后，就退回到上一行。
-
可以像全排列 used 数组那样，再为 「主对角线（Main diagonal）」 和 「副对角线（Sub diagonal）」 设置相应的 布尔数组变量，只要排定一个 「皇后」 的位置，就需要占住对应的位置。
编码
我们使用一个 1 到 4 的排列表示一个 4 \times 4 的棋盘，例如：
- 得到一个符合要求的全排列以后，生成棋盘的代码就很简单了。
-
说明：
- 将「行状态」、「主对角线状态」、「副对角线状态」 设置为成员变量，以避免递归方法参数冗长（参考代码 2、参考代码 3 类似看待）。至于是否有必要这样做，以后在项目开发中需要遵守项目文档的规定；
- Java 中 Stack 已经废弃，推荐使用 ArrayDeque，可以查阅文档。
方法：回溯搜索算法（深度优先遍历）
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
private int n;
// 记录某一列是否放置了皇后
private boolean[] col;
// 记录主对角线上的单元格是否放置了皇后
private boolean[] sub;
// 记录了副对角线上的单元格是否放置了皇后
private boolean[] main;
private List<List> res;
public List<List> solveNQueens(int n) {
res = new ArrayList();
if (n == 0) {
return res;
}
// 设置成员变量，减少参数传递，具体作为方法参数还是作为成员变量，请参考团队开发规范
this.n = n;
this.col = new boolean[n];
this.sub = new boolean[2 * n - 1];
this.main = new boolean[2 * n - 1];
Deque path = new ArrayDeque();
dfs(0, path);
return res;
}
private void dfs(int row, Deque path) {
if (row == n) {
// 深度优先遍历到下标为 n，表示 [0.. n - 1] 已经填完，得到了一个结果
List board = convert2board(path);
res.add(board);
return;
}
// 针对下标为 row 的每一列，尝试是否可以放置
for (int j = 0; j < n; j++) {
if (!col[j] && !sub[row + j] && !main[row - j + n - 1]) {
path.addLast(j);
col[j] = true;
sub[row + j] = true;
main[row - j + n - 1] = true;
dfs(row + 1, path);
main[row - j + n - 1] = false;
sub[row + j] = false;
col[j] = false;
path.removeLast();
}
}
}
private List convert2board(Deque path) {
List board = new ArrayList();
for (Integer num : path) {
StringBuilder row = new StringBuilder();
row.append(".".repeat(Math.max(0, n)));
row.replace(num, num + 1, "Q");
board.add(row.toString());
}
return board;
}
}
参考代码2：
- 其实已经摆放皇后的列下标、占据了哪一条主对角线、哪一条副对角线也可以使用哈希表来记录。
- 实际上哈希表底层也是数组，使用哈希表可以不用处理已经占据位置的皇后的主对角线、副对角线的下标偏移问题。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
private Set col;
private Set sub;
private Set main;
private int n;
private List<List> res;
public List<List> solveNQueens(int n) {
this.n = n;
res = new ArrayList();
if (n == 0) {
return res;
}
col = new HashSet();
sub = new HashSet();
main = new HashSet();
Deque path = new ArrayDeque();
dfs(0, path);
return res;
}
private void dfs(int row, Deque path) {
if (row == n) {
List board = convert2board(path);
res.add(board);
return;
}
// 针对每一列，尝试是否可以放置
for (int i = 0; i < n; i++) {
if (!col.contains(i) && !sub.contains(row + i) && !main.contains(row - i)) {
path.addLast(i);
col.add(i);
sub.add(row + i);
main.add(row - i);
dfs(row + 1, path);
main.remove(row - i);
sub.remove(row + i);
col.remove(i);
path.removeLast();
}
}
}
private List convert2board(Deque path) {
List board = new ArrayList();
for (Integer num : path) {
StringBuilder row = new StringBuilder();
row.append(".".repeat(Math.max(0, n)));
row.replace(num, num + 1, "Q");
board.add(row.toString());
}
return board;
}
}
参考代码3：
- 搜索问题一般来说复杂度很高，因此在线测评系统的后台测试数据不会很大。因此布尔数组可以只用一个整数来代替（int 或者 long 根据情况决定），int 类型整数等价于一个 32 位布尔数组，long 类型整数等价于一个 64 位布尔数组。
- 使用一个整数代表一个布尔数组，在比较布尔数组所有的位的值是否相等时，只需要 O(1)，并且传递参数、复制也是相对方便的。这样的技巧叫做「状态压缩」，动态规划问题里有一类问题就叫做状态压缩 dp（我学不过来了，以后学会了再向大家介绍，请谅解）。
- 状态压缩的缺点是：编码得很细心，不容易调试。
- 力扣」第 1371 题：每个元音包含偶数次的最长子字符串「，是每日一题出现过的状态压缩的经典问题，综合使用了很多算法思想和技巧，感兴趣的朋友可以复习一下。
- 说明：使用 状态压缩 技巧，可以完成 「力扣」第 52 题：「N皇后 II」。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution3 {
private List<List> res;
private int n;
public List<List> solveNQueens(int n) {
this.n = n;
res = new ArrayList();
if (n == 0) {
return res;
}
int col = 0;
int main = 0;
int sub = 0;
Deque path = new ArrayDeque();
dfs(0, col, main, sub, path);
return res;
}
private void dfs(int row, int col, int sub, int main, Deque path) {
if (row == n) {
List board = convert2board(path);
res.add(board);
return;
}
// 针对每一列，尝试是否可以放置
for (int i = 0; i > i) & 1) == 0
&& ((sub >> (row + i)) & 1) == 0
&& ((main >> (row - i + n - 1)) & 1) == 0) {
path.addLast(i);
col ^= (1 << i);
sub ^= (1 << (row + i));
main ^= (1 << (row - i + n - 1));
dfs(row + 1, col, sub, main, path);
main ^= (1 << (row - i + n - 1));
sub ^= (1 << (row + i));
col ^= (1 << i);
path.removeLast();
}
}
}
private List convert2board(Deque path) {
List board = new ArrayList();
for (Integer num : path) {
StringBuilder row = new StringBuilder();
row.append(".".repeat(Math.max(0, n)));
row.replace(num, num + 1, "Q");
board.add(row.toString());
}
return board;
}
}
同类问题
参考资料
- liuyubobobo 老师在慕课网上开设的课程《玩转算法面试》代码仓库；
- 《剑指 Offer（第 2 版）》面试题 38 ：字符串的排列，相关题目 2。
一个回溯算法可视化的小项目
- 通过可视化帮助理解回溯算法的思想。写 Java 的朋友可以看看，这是我写的一个练习的项目，学习的价值不大，不用点赞。
GitHub 地址：Backtracking-Visualization