传送门：51. N皇后。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
img
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中
'Q'和'.'分别代表了皇后和空位。示例:
输入: 4 输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。
分析：对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。
回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
- 找到一个可能存在的正确的答案
- 在尝试了所有可能的分步方法后宣告该问题没有答案
在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。
八皇后问题是应用回溯法求解的典型案例。
这篇文章给以 LeetCode 第 51 题为背景，示例了 n 皇后问题的求解。
我们介绍 3 种解法，其核心思想是递归回溯算法。这 3 种解法的不同之处，就在于判断皇后棋子是否可以摆放上，其中用到的方法都很基础，我个人认为都不难理解，并且都应该掌握。
解法 1 ：在尝试摆放皇后棋子之前，判断当前考虑的这个位置是否可以放置皇后棋子。
Java 代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
// https://leetcode-cn.com/problems/n-queens/description
// 只用一张棋盘摆放的方法完成了 n 皇后问题
public class Solution3 {
private List<List<String>> res;
private boolean[][] solution; // true 就表示当前位置放置了皇后，false 就表示没有放置皇后
public List<List<String>> solveNQueens(int n) {
res = new ArrayList<>();
solution = new boolean[n][n];
nQueens(0, n, solution);
return res;
}
private void nQueens(int row, int n, boolean[][] solution) {
if (row == n) {
// 将 solution 处理成为一个棋盘 generateChessboard
List<String> board = generateChessboard(solution, n);
res.add(board);
return;
}
// 站在当前这一行（索引为 row），去一列一列检查是否可以放皇后
for (int i = 0; i < n; i++) {
if (notInDanger(row, i, n, solution)) {
solution[row][i] = true;
nQueens(row + 1, n, solution);
solution[row][i] = false;// 因为下一列的放置与上一列应该是在同样的环境下进行考虑，棋盘要重置
}
// 如果每一列都不能放置，那么这个方法就自动退出了，当前错误的棋盘摆放就不会被保存
}
}
private List<String> generateChessboard(boolean[][] solution, int n) {
List<String> res = new ArrayList<>();
StringBuilder stringBuilder;
for (int i = 0; i < n; i++) {
stringBuilder = new StringBuilder();
for (int j = 0; j < n; j++) {
if (solution[i][j]) {
stringBuilder.append("Q");
} else {
stringBuilder.append(".");
}
}
res.add(stringBuilder.toString());
}
return res;
}
// i，j 表示当前尝试放置皇后棋子的坐标
private boolean notInDanger(int i, int j, int n, boolean[][] solution) {
// 设置一些标志，看看当前位置是不是危险的
// 从之前递归的写法来看，一定是处于不同行的，所以要接着判断，属于不同的列，不同的主对角线和副对角线
// 判断在 (2,3) 之前的那些行，在 3 这一列上是否有皇后，即 (0,3)、 (1,3)
for (int r = i; r >= 0; r--) {
if (solution[r][j]) {
return false;
}
}
// 判断在 (2,3) 之前的那些行，在它的主对角线上是否有皇后（向右上方走）
for (int r = i, c = j; r >= 0 && c < n; r--, c++) {
if (solution[r][c]) {
return false;
}
}
// 判断在 (2,3) 之前的那些行，在它的副对角线上是否有皇后（向左上方走）
for (int r = i, c = j; r >= 0 && c >= 0; r--, c--) {
if (solution[r][c]) {
return false;
}
}
// 全部判断完以后，才表示安全
return true;
}
public static void main(String[] args) {
Solution3 solution = new Solution3();
List<List<String>> solveNQueens = solution.solveNQueens(8);
int solveSize = solveNQueens.size();
System.out.println("一共有 " + solveSize + " 种解。");
for (int i = 0; i < solveNQueens.size(); i++) {
System.out.println("第 " + (i + 1) + " 种解：");
for (String line : solveNQueens.get(i)) {
System.out.println(line);
}
}
}
}
- 我个人觉得这种解法使用了典型的回溯方法的套路。我们看递归方法
private void nQueens(int row, int n, boolean[][] solution)：
我们观察这个方法是如何调用自己的：在一个循环中递归调用自己，而仅仅只是参数不同，在调用自己前设置状态，在调用自己后取消状态。是不是非常像回溯法解决排列问题。
解法 2：使用三个一维数组记录了是否可以摆放皇后棋子。
下面这种解法，在主对角线和副对角线上是否可以摆放元素使用了并不太难的技巧，使得求解更加简洁。
Java 代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
// https://leetcode-cn.com/problems/n-queens/description
// 刘宇波老师介绍的 n 皇后问题的解法
public class Solution2 {
private List<List<String>> res;
private boolean[] col;
private boolean[] dia1;
private boolean[] dia2;
public List<List<String>> solveNQueens(int n) {
res = new ArrayList<>();
col = new boolean[n];
// 可以用归纳法计算出对角线数组元素的个数为 2*n-1
// 这里要动手用纸笔计算一下，并不难
dia1 = new boolean[2 * n - 1];
dia2 = new boolean[2 * n - 1];
// 表示一行数据，第 0 个数字表示"第 0 行的皇后应该摆放在哪个索引位置"
LinkedList<Integer> row = new LinkedList<>();
putQueen(n, 0, row);
return res;
}
// 在一个 n 皇后问题中，尝试在第 index 行如何摆放一个皇后
// 我们将它设计成一个递归调用的函数，所以要想清楚两个步骤
private void putQueen(int n, int index, LinkedList<Integer> row) {
if (index == n) {
res.add(generateBoard(n, row));
}
for (int i = 0; i < n; i++) { // i 表示列数，index 表示行数
if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
// 设置状态
row.addLast(i);
col[i] = true;
dia1[index + i] = true;
dia2[index - i + n - 1] = true;
putQueen(n, index + 1, row);
// 重置状态（与前面设置状态的步骤是一一对应的）
col[i] = false;
dia1[index + i] = false;
dia2[index - i + n - 1] = false;
row.removeLast();
}
}
}
private List<String> generateBoard(int n, LinkedList<Integer> row) {
List<String> board = new ArrayList<>();
for (int i = 0; i < n; i++) {
char[] charArray = new char[n];
Arrays.fill(charArray, '.');
charArray[row.get(i)] = 'Q';
board.add(new String(charArray));
}
return board;
}
public static void main(String[] args) {
Solution2 solution = new Solution2();
List<List<String>> solveNQueens = solution.solveNQueens(8);
int solveSize = solveNQueens.size();
System.out.println("一共有 " + solveSize + " 种解。");
for (int i = 0; i < solveNQueens.size(); i++) {
System.out.println("第 " + (i + 1) + " 种解：");
for (String line : solveNQueens.get(i)) {
System.out.println(line);
}
}
}
}
解法 3 ：使用一个二维数组记录了每添加一个皇后，棋盘中被已经存在的皇后可以攻击到的范围。
下面的这种写法可能看起来篇幅比较长，但是其中用到的使用方向数组进行状态设置的技巧还是可以参考的。
另外，还要注意，下面的这个方法涉及到二维数组的复制，Java 中并不支持直接对二维数组进行深复制，因此最简单的做法，就是将二维数组中的元素一个一个进行复制。
Java 代码：
import java.util.ArrayList;
import java.util.List;
// https://leetcode-cn.com/problems/n-queens/description/
// 这一版使用了递归回溯的思想完成
// 使用 marked 数组把皇后四面八方的攻击范围都给标记上了
public class Solution {
// x-1,y-1 x-1,y x-1,y+1
// x,y-1 x,y x,y+1
// x+1,y-1 x+1,y x+1,y+1
private static int[] dx = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
private static int[] dy = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
private int n;
// 当前坐标 x,y 放上了皇后以后，它的 8 个方向都应该被标记不能放置其它皇后
// 标记 marked 数组，给皇后的四面八方都标记上
private void put_down_the_queen(int x, int y, boolean[][] marked) {
marked[x][y] = true;
// 从 1 开始， 从 0 开始也可以，只不过重复了 marked[x][y] = true;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 8; j++) {
// 不要忘记乘以 i
int new_x = x + i * dx[j];
int new_y = y + i * dy[j];
// 只要都在棋盘内
if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < n) {
marked[new_x][new_y] = true;
}
}
}
}
public List<List<String>> solveNQueens(int n) {
this.n = n;
List<List<String>> res = new ArrayList<>();
// 默认值是 false ，表示当前没有放置皇后
boolean[][] marked = new boolean[n][n];
// n 皇后问题的一个解
char[][] solution = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
solution[i][j] = '.';
}
}
generate(0, n, marked, solution, res);
return res;
}
// 在第 k 行（从 0 开始计算）考虑，这一行的 n 个元素，搜索皇后应该摆放在哪里
// 皇后摆放的位置应该在 marked 数组中标记为 false 的地方，此时已经摆放皇后的情况位于 solution 数组中
// 所有已经得到的 n 皇后问题的解位于 res 中
private void generate(int k, int n, boolean[][] marked, char[][] solution, List<List<String>> res) {
if (k == n) {
res.add(transform2str(solution));
return;
}
for (int i = 0; i < n; i++) {
if (!marked[k][i]) { // 如果没有标记过，表示当前位置是安全的，可以放置皇后
// 注意：对于二维数组的复制，不能简单实用 clone() 或者 System.arraycopy() 或者 Arrays.copyOf() 方法
// 应该对它们在一维数组上使用
boolean[][] temp_mark = copyNewArr(marked);
solution[k][i] = 'Q';
put_down_the_queen(k, i, marked);
generate(k + 1, n, marked, solution, res);
marked = temp_mark;
solution[k][i] = '.';
}
}
}
// 复制一个 marked 数组
private boolean[][] copyNewArr(boolean[][] marked) {
boolean[][] res = new boolean[n][n];
for (int i = 0; i < n; i++) {
System.arraycopy(marked[i],0,res[i],0,n);
}
return res;
}
private List<String> transform2str(char[][] solution) {
List<String> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
res.add(new String(solution[i]));
}
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
List<List<String>> solveNQueens = solution.solveNQueens(8);
int solveSize = solveNQueens.size();
System.out.println("一共有 " + solveSize + " 种解。");
for (int i = 0; i < solveNQueens.size(); i++) {
System.out.println("第 " + (i + 1) + " 种解：");
for (String line : solveNQueens.get(i)) {
System.out.println(line);
}
}
}
}
（本节完）
网友评论