递归-------八皇后

解题思路:一维数组递归实现八皇后

最重要的是理解check方法：  当第n个皇后一直找不到合适位置时会发生什么

    1.当冲突时，继续执行 array[i]=n，直到找到合适的
    2.当冲突时，并一直解决不了会弹栈·回溯

judge方法一个简单的规则方法：判断第n个皇后与前面放置的皇后是否冲突

1. 当在同一列时的情况：array[i] == array[n]

2. 当在同一斜线的情况：Math.abs(i - n) == Math.abs(array[i] - array[n])

3. 当在同一行的情况，但这个情况没必要写，因为n一直递增
   

最重要的是理解为什么会发生回溯：实际上是递归方法在栈中的弹栈的一个状况

注意事项:

这是用GPT描述八皇后递归在栈中的情况

具体来说，假设我们需要放置n个皇后，那么在递归调用的过程中，栈的使用情况如下：

初始状态：栈为空。

第一次递归调用：将第一个皇后放置在第一行的第一列。将当前的皇后位置信息和其他必要的参数压入栈中。

第二次递归调用：在第二行尝试放置皇后，如果符合条件则继续递归调用，否则进行回溯。将当前的皇后位置信息和其他必要的参数压入栈中。

第三次递归调用：在第三行尝试放置皇后，如果符合条件则继续递归调用，否则进行回溯。将当前的皇后位置信息和其他必要的参数压入栈中。

...

第n次递归调用：在第n行尝试放置皇后，如果符合条件则继续递归调用，否则进行回溯。将当前的皇后位置信息和其他必要的参数压入栈中。

当达到递归终止条件时，开始进行回溯。系统从栈中弹出上一次递归调用的信息，回到上一次调用的下一行代码。

继续回溯，直到回到初始状态，即所有的解决方案都找到了。

参考代码:

import java.util.Queue;
import java.util.Scanner;

public class Main {
   private static int max;
   private static  int [] array;
   private static int count=0;
   private static int count2=0;

   public static void main(String[] args) {
       Scanner scanner=new Scanner(System.in);
        max=scanner.nextInt();
        array=new int[max];

       Main main=new Main();
       main.check(0);
       System.out.println(count);

   }
   private  void check(int n){

       if (n==max){ //当最后一个皇后的最后一个时，表示结束
           print();
           count++;//记录解法
           return;
       }
       for (int i=0;i<max;i++){
           array[n]=i;//先放到第一行第一列，依次进行
           if (judge(n)){//当符合规则时进入递归，判断第n个皇后和n前面的皇后是否冲突
               check(n+1);
           }
           //当冲突时，继续执行 array[i]=n，直到找到合适的
           //若没找到合适位置，弹栈，回溯

       }
   }

   //判断是否满足八皇后规则

/**
*
* @param n 表示第n个皇后
* @return
*/

   private    boolean judge(int n) {
       for (int i = 0; i < n; i++) {
           //1.判断第n个皇后是否和第n-1皇后是否在同一列
           //2.判断是否为同一斜线，在坐标系中两个点的横坐标之差的绝对值和竖坐标之差的绝对值相等斜率为1，即为对角线
           if (array[i] == array[n] || Math.abs(i - n) == Math.abs(array[i] - array[n])) {
               return false;
           }

       }
       return true;
   }
   //打印皇后摆放的位置
   public void print(){
      if (count2<3){//限制三次
       for (int i=0;i<array.length;i++){

           System.out.print(array[i]+1+" ");
       }
       count2++;
       System.out.println();
   }
   }
}