回溯法--N皇后问题

一、问题描述

1、按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
2、n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

二、示例

2.1 四皇后的2个可行解

2.2 过程图示

以四皇后为例，展示寻找一种可行解的过程

三、问题分析

3.1涉及到的概念

递归

自己调自己,在方法中调用方法本身。
使用递归需要注意：
1、递归要有出口，不能是死循环，死循环会造成栈溢出。
2、递归次数不宜过多，过多也会有栈溢出的问题。

回溯

回溯法是一种解决问题的算法，它会尝试每一种可能的解决方案来找到最佳解。

3.2 分析

回溯法一般通过递归实现。在n皇后问题中，我们可以从第一行开始，每行放置皇后，检查该皇后是否与之前的皇后冲突，如果没有则放置下一行的皇后，如果发现无解则回溯到上一行重新尝试。

回溯用递归的方式去控制for嵌套的层数，4×4递归4层，每一层有一个for循环，遍历每一层对应的位置。时间复杂度和嵌套for循环一致。

四、 代码实现

4.1 实现思路

宏观：

使用深度搜索的方法，按照先行后列的顺序，查看每一个位置是否满足条件。

微观：

1. 定义二维数组表示棋盘，定义一个变量n表示几个皇后
2. 定义一个方法用来判断当前摆放的皇后是否与之前的皇后冲突（同列、左上方，右上方)，冲突返回0；否则，返回1，表示此位置可以放置皇后。
3. 定义一个递归函数，尝试在当前行放置皇后。

这里给一个回溯代码模板

if(终止条件){收集结果；return;
}for(遍历本层集合中的元素){处理节点；递归；回溯，撤销处理结果
}

4.2 递归函数NS图

4.3 代码

package com.lsn.NQueen;public class NQueens {// 定义一个二维数组表示棋盘int[][] board;// 定义一个变量表示几个皇后int n;// 构造函数，初始化棋盘和npublic NQueens(int n) {board = new int[n][n];this.n = n;}// 判断当前摆放的皇后是否与之前的皇后冲突public boolean isSafe(int row, int col) {int i, j;// 检查当前列是否有皇后for (i = 0; i < row; i++) {if (board[i][col] == 1) {return false;}}// 检查左上方是否有皇后for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {if (board[i][j] == 1) {return false;}}// 检查右上方是否有皇后for (i = row, j = col; i >= 0 && j < n; i--, j++) {if (board[i][j] == 1) {return false;}}// 如果都没有冲突，则返回truereturn true;}// 递归函数，尝试在当前行放置皇后public boolean solve(int row) {// 如果所有行都已经摆放完毕，则返回true（终止条件，收集结果）if (row == n) {return true;}// 尝试在当前行的每一列放置皇后（单层逻辑，处理节点）for (int col = 0; col < n; col++) {// 判断当前位置是否安全if (isSafe(row, col)) {// 如果安全，则将皇后放置在当前位置board[row][col] = 1;// 递归调用solve函数，尝试在下一行放置皇后if (solve(row + 1)) {return true;}// 如果下一行无法放置皇后，则回溯到当前行，重新尝试放置皇后（撤销处理节点的情况）board[row][col] = 0;}}// 如果当前行的每一列都无法放置皇后，则返回falsereturn false;}// 打印棋盘public void printBoard() {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.print(board[i][j] + " ");}System.out.println();}}public static void main(String[] args) {// 创建一个NQueens对象，并初始化规模为8NQueens nQueens = new NQueens(3);// 调用solve函数，尝试解决N皇后问题if (nQueens.solve(0)) {// 如果找到了解，则打印棋盘nQueens.printBoard();} else {// 如果没有找到解，则打印无解System.out.println("No solution found.");}}
}