北京做网站供应商/杭州谷歌推广
八皇后问题主要是：在一个8*8的棋盘上，放置八个皇后，这八个皇后不能处在同一行、同一列以及统一斜线，问符合要求的安置方法有多少种情况？
高斯说64种，随着计算机的高速发展，而今人类用计算机计算得出的记过是92种，那我们是如何借助计算机实现的呢？
首先，我们先聊聊思路
至于图上第4步为什么会回溯呢？
理由是：假设说如第4点的操作，第8个皇后（不一定是第8个皇后，也许是前面的皇后就已经出现了所有列数的安放位置都不符合条件）的安放位置都不符合情况，这时候该递归方法并没有return结束，所以第七个皇后的安放列数仍然向下遍历，故这就解决了回溯的情况。
要点：
1.理论上是需要创建一个二维数组来记录棋盘的，但是这里数组比较多位置会是没有落子的，即都为0 既为了节省空间，也为了简便，故我们这里可以直接创建一个一维数组 下标代表行数，数组内的值代表列数，如arr[1]=3,即代表落子在第一行第三列
2.这里判断是否在同一斜线上，我们通过一个数学结论去判断：如果对角线的行之差的绝对值等于列之差的绝对值，则在同一斜线上
下面附上具体代码实现
package com.liu.recursion;
/*** @author liuweixin* @create 2021-09-09 16:15*/
//处理八皇后问题
public class Queue8 {//先创建一个棋盘//理论上是需要创建一个二维数组，但是这里数组比较多位置会是没有落子的//既为了节省空间，也为了简便，故我们这里可以直接创建一个一维数组// 下标代表行数，数组内的值代表列数，如arr[1]=3,即代表落子在第一行第三列int[] arr;//用于储存八皇后放置的结果int maxSize = 8;//皇后的数量int count;//记录八皇后的数public Queue8() {arr = new int[maxSize];}public static void main(String[] args) {Queue8 queue8 = new Queue8();queue8.dealQueue8(0);System.out.println("八皇后结果的总数为:"+queue8.count);}/*** 处理八皇后问题* 八个皇后不能处于同一行、同一列、同一斜线** @param n 安放第n个皇后*/public void dealQueue8(int n) {if(n==maxSize){//此时八皇后已经安放好
// System.out.println("八皇后的位置已经安放好");count++;//每进入这个判断一次，就是一种结果show();return;}else{for (int i = 0; i < arr.length; i++) {arr[n]=i;//因为这是第n个皇后，所以也就在对应的第n行，我们遍历安放列数//判断安放位置是否冲突if(check(n)){//此时不冲突，则安放下一个dealQueue8(n+1);}//如果冲突，就会通过循环把n放在下一列，然后循环比较}}}/*** 检查放置的第n个皇后是否符合要求** @param n 传入的第n个皇后* @returni 如果符合要求，则返回true*/public boolean check(int n) {for (int i = 0; i < n; i++) {if (arr[i] == arr[n] || (Math.abs(n - i) == Math.abs(arr[n] - arr[i]))) {//判断是否在同一列或者在统一斜线//对角线的行之差的绝对值等于列之差的绝对值，此时为在统一斜线上return false;}}return true;}/*** 遍历八皇后结果*/public void show(){for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");}System.out.println();}}