递归求解n皇后问题的解析和求解（矩阵储存版）
1. n皇后问题问题描述
n皇后问题来源于著名的十九世纪著名数学家提出的八皇后问题。问题为：在8×8的棋盘上摆放八个皇后，皇后之间不能互相攻击，既任意两个皇后不在同一行、同一列，也不再同一斜线上。n皇后则是在八皇后的基础上，将棋盘扩充为n×n，皇后的数量也相应改变为n。
2. 利用递归与回溯求解n皇后问题
2.1递归算法
n皇后问题是经典的学习递归算法的经典问题。递归算法是将一种直接或者间接调用自身,将问题分解为同类子问题,从而实现复杂问题求解的一种算法。
递归算法的设计重点有两点:
① 分析问题, 得出递归关系。
② 设置边界条件, 既控制递归出口。
2.2 回溯
回溯算法是指,当对问题进行搜索尝试时,当发现 条件不符合求解条件时,则"回溯"返回,返回到上一步,继续搜索其他路径。
2.3 利用递归和回溯求解n皇后问题
在对问题进行计算机求解时，我们先以四皇后问题为例，以人的思维对四皇后问题进行求解。求解过程如下图：
由上图，我们描述一下求解步骤：由于皇后不能处于同一行，所以我们会一行一行的确定皇后位置。在判断每行的皇后的位置时，会从该行的第一个位置开始遍历该行每个位置，判断该位置是否满足皇后不互相攻击的要求，如果满足，则暂时将皇后放在该位置。继续寻找下一行，如果顺利在最后一行找到符合条件的皇后，则找到答案。但如果出现某一行没有一个位置能够满足皇后放下，则说明目前这种皇后方法不合法，则回退上一个满足条件的皇后拿起，放在同一行中下一个满足条件的地方，如果该行仍没有满足条件的位置，则继续回退。在这样之下，便能得到一个正确的解。
这样的思路，我们同样可以在程序设计上沿用。程序流程为：
① 先从第一行开始遍历，在第一行符合可以放置皇后的位置暂时放下皇后。
② 往下一行遍历，根据之前已经放置皇后的位置，判断该行是否存在可以放置皇后的位置，如果存在，则放置。继续遍历下一行，如果不存在，则退回，将上一行已放置的皇后拿起，寻找下一个可以放置的位置。
③ 反复执行①、②，知道结果输出。
根据以上流程，我们将会得到1个或0个（当n≤3时，没有解）解。那么，如果我们需要的到所有解呢，又该怎么办？其实很简单，只要我们在得到第一个解之后，将之输出，然后回退。那么我们又会重新执行①和②，得到第二个解（如果存在）。继续同样的操作，就可以得到需要的所有解。（此处可能有些难理解，多读几遍，然后自己走一遍四皇后的流程便能理解了）。
那理论存在，我们开始实践。
//在本程序中，*表示棋盘中未放置皇后的位置，$表示皇后,如下：
// * * * * * * * $
// * * * $ * * * *
// $ * * * * * * *
// * * $ * * * * *
// * * * * * $ * *
// * $ * * * * * *
// * * * * * * $ *
// * * * * $ * * *
//首先我们需要编写一个判断目前位置是否可以合法（既是否可以放置皇后的函数）
//其中nQueen数组为棋盘和当前皇后的放置情况，row和col为当前需要判断的棋盘位置
static boolean isLegal(char[][] nQueen,int row,int col){
//如果是棋盘第一行，皇后一定合法;
if (row == 0){
return true;
}else {
//如果不是第一行，则需要通过该行之前已经确定的皇后判断是否该行是否合法
//合法条件是，不能和已确定的皇后处于同一行或者在已确定的皇后的斜线上
for(int i = 0; i < row; i++){
for (int j = 0; j < nQueen.length; j++){
//定位已确定的皇后位置
if (nQueen[i][j] == '$'){
//判断是否和已确定的皇后同一列以及是否在已确定皇后的斜线上
if (col == j || row - i == Math.abs(col - j)){
return false;
}
}
}
}
}
//如果遍历完该点之前所有的皇后都没有返回错误，证明该点合法
return true;
}
然后，我们开始设置递归函数，根据上述程序流程，我们知道每行只能放置一个皇后，因此得到递归出口为放置皇后的行数，当最后一行放置皇后之后，递归可以结束。并且已放置的皇后位置会影响后续皇后的放置。因此函数如下：
static boolean isSafe(int n, int n1, int []num,char[][] nQueen){
//其中n表示目前还有多少个皇后未确定位置，num表示皇后的总数
//如果只需要求解有一个答案，既所有皇后都找到了合法的位置,此时n==0，就return true
//如果求解所有答案，则没每到一个答案，就输出一个答案，num+1。然后返回false，进行回退，继续寻找下一个答案。
if (n == 0){
num[0]++;
print(nQueen);
//分割开每个答案
for (int i = 0; i < 2 * n1 - 1; i++) {
System.out.print("-");
}
System.out.println();
return false;
}else {
//如果所有行的皇后还没有找到，遍历改行每一个，查看符合的位置
for (int i = 0; i < n1; i++){
//如果符合，则暂定该点为皇后位置，然后遍历下一行
if (isLegal(nQueen, n1-n, i)) {
nQueen[n1-n][i] = '$';
if (isSafe(n - 1, n1, num, nQueen)){
return true;
}else {
//如果往下遍历后不成立，则将该点的皇后去掉
nQueen[n1-n][i] = '*';
}
}
}
}
return false;
}
完整可执行代码：
package Test_Package;
import java.util.Scanner;
public class NQueen {
//递归的经典问题。n皇后问题。
public static void main(String[] args) {
//首先对main函数进行处理
//在本程序中，使用*代表棋盘，$好代表皇后位置
Scanner sc = new Scanner(System.in);
//n代表皇后维度
System.out.print("Please enter number of queens: ");
int n = sc.nextInt();
//num代表答案总数，用数组形式便于输出
int[] num = {0};
//消除sc
sc.close();
//nQueen代表棋盘以及皇后的位置
char[][] nQueen = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j= 0; j < n; j++){
nQueen[i][j] = '*';
}
}
isSafe(n, n, num, nQueen);
System.out.println();
System.out.println("Number of solutions = " + num[0]);
}
//递归方法输出皇后结果以及方法个数
static boolean isSafe(int n, int n1, int []num,char[][] nQueen){
//其中n表示目前还有多少个皇后未确定位置，num表示皇后的总数
//如果只需要求解有一个答案，既所有皇后都找到了合法的位置,此时n==0，就return true
//如果求解所有答案，则没每到一个答案，就输出一个答案，num+1。然后返回false，进行回退，继续寻找下一个答案。
if (n == 0){
num[0]++;
print(nQueen);
//分割开每个答案
for (int i = 0; i < 2 * n1 - 1; i++) {
System.out.print("-");
}
System.out.println();
return false;
}else {
//如果所有行的皇后还没有找到，遍历改行每一个，查看符合的位置
for (int i = 0; i < n1; i++){
//如果符合，则暂定该点为皇后位置，然后遍历下一行
if (isLegal(nQueen, n1-n, i)) {
nQueen[n1-n][i] = '$';
if (isSafe(n - 1, n1, num, nQueen)){
return true;
}else {
//如果往下遍历后不成立，则将该点的皇后去掉
nQueen[n1-n][i] = '*';
}
}
}
}
return false;
}
//输出方法，为了方便打印结果缩写的方法
static void print(char[][] nQueen){
for (int i = 0; i < nQueen.length; i++) {
for (int j = 0; j < nQueen.length; j++) {
System.out.print(nQueen[i][j]+" ");
}
System.out.println();
}
}
//通过已确定的位置判断皇后位置是否合法
static boolean isLegal(char[][] nQueen,int row,int col){
//如果是棋盘第一行，皇后一定合法;
if (row == 0){
return true;
}else {
//如果不是第一行，则需要通过该行之前已经确定的皇后判断是否该行是否合法
//合法条件是，不能和已确定的皇后处于同一行或者在已确定的皇后的斜线上
for(int i = 0; i < row; i++){
for (int j = 0; j < nQueen.length; j++){
//定位已确定的皇后位置
if (nQueen[i][j] == '$'){
//判断是否和已确定的皇后同一列以及是否在已确定皇后的斜线上
if (col == j || row - i == Math.abs(col - j)){
return false;
}
}
}
}
}
//如果遍历完该点之前所有的皇后都没有返回错误，证明该点合法
return true;
}
}
输入：8
输出结果：文章来源：https://www.toymoban.com/news/detail-804400.html
（情况太多，截图仅截最后）文章来源地址https://www.toymoban.com/news/detail-804400.html
到了这里，关于递归求解n皇后问题的解析和求解（矩阵储存版）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
