Java数据结构算法（八皇后问题使用递归解法）

八皇后问题

解决思路：

1. 定义一个一维数组 queue[] 用于存放各个皇后的位置（由于每一行只能放一个皇后，因此第 n 个皇后存放于数组下标为n-1的行）

2. 依次将 8 个皇后放入棋盘，首先将第 1 个皇后放到第一行第一列，判断是否有冲突，若有冲突，则将第一个皇后向右边移动一列，若没冲突，则使用递归放入第 2 个皇后，接着判断前面的皇后是否有冲突，有冲突则向右移动一列，没冲突则依照放入第1、2个皇后的步骤继续放入剩下的皇后，当即将要放入的皇后的个数大于需要放入的皇后的个数时，输出queue数组中存放的值（即满足8皇后问题的各个皇后的 y 坐标的值），终止本次递归。

3. 代码实现如下（共有92种放法）：

public class Queue8 { // 皇后的个数 int max = 8; // 第 n+1 个皇后存放位置的列值（行值为数组下标） int queue[] = new int[max]; // 满足8皇后问题的有多少种放法 private static int num=0; public static void main(String[] args) { Queue8 queue8=new Queue8(); queue8.check(0); System.out.println(num); } /**
     * 放入第 n+1 个皇后 （使用下标为0 的数组存放第 1 个皇后的位置）
     * @param n
     * @return
     */ public void check(int n){ if (n==max){ for (int i = 0; i < queue.length; i++) { System.out.print(queue[i]+" "); } num++; System.out.println(); return ; } for (int i = 0; i < max ; i++) { queue[n] = i; if (isLegal(n)){ check(n+1); } } } /**
     * 判断放入第 n+1 个皇后是否和前面的n个皇后冲突
     * @param n
     * @return
     */ public boolean isLegal(int n){ for (int i = 0; i < n; i++) { if (queue[n] == queue[i] || Math.abs(queue[n] - queue[i])== Math.abs(n-i)){ return false; } } return true; } } 

本文地址：https://blog.csdn.net/weixin_43193439/article/details/107889141