思路分析： 把第一个皇后放到第一行第一列

        （1）把第二个皇后放到第二行第一列，进行判断，如果不行，放在第二列，进行判断，如果不行，放在 第三列，进行判断，一次把所有列进行尝试，直至找到合适位置

        （2）把第三个皇后放到第三行第一列，同步骤2

        （3）........

        （4）直至第8个皇后也能放到合适位置，此时第一个符合要求摆法便找到。

        （5）当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯。把第一个皇后在第一行第一列的所 有解都找到

        （6）继续把第一个皇后放到第一行第二列，继续执行上述步骤

结果表示：用一个数组来表示摆法，比如arr[8]={0，4，5，7，6，1，2，3}，下标对应的是第几行， 数值对应的是第几列。

arr[i]=j 第i+1个皇后，放在了第i+1行第j+1列

代码实现：

public class Queen {
    //定义一个max，表示一下共有多少个皇后，同理可求n个皇后
    int max = 8;
    //定义一个数组，报错皇后放置的位置
    int[] array = new int[max];
    //定义一个变量，保存共有多少中摆法
    static int count = 0;

    public static void main(String[] args) {
        Queen queen=new Queen();
        queen.queen8(0);
        System.out.println("共有"+count+"种摆法");
    }
    //放置n个皇后，递归
    private void queen8(int n) {
        //递归终止条件
        if (n == max) {//8个皇后放好了
            print();
            return;
        }
        //依次放入皇后，判断是否冲突
        for (int i = 0; i < max; i++) {
            //把当前这个皇后，放到该行的第1列
            array[n] = i;
            if (judge(n)) {
                //如果不冲突，放下一个皇后
                queen8(n + 1);
            }
            //如果冲突，放下一列
        }
    }
    private void print(){
        count++;
        for (int i = 0; i <array.length ; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    //判断是否冲突
    private boolean judge(int n) {
        //判断当前皇后与前面的n-1个是否冲突
        for (int i = 0; i < n; i++) {
            //任意两个皇后都不能处于同一行，同一列或者同一写线上
            //判断是否在同一行  没有必要n++
            //判断是否同一列 array[i]==array[n]
            //是否同一斜线 Math.abs(n-i)==Math.abs(array[n]-array[i]
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return false;
            }
        }
        return true;
    }
}

八皇后问题

问题描述

时间退回到1848年，国际西洋棋棋手马克斯·贝瑟尔提出了这样的一个问题：

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
后面陆续有不同的学者提出自己的见解。大数学家高斯认为一共有76种摆法，1854年在柏林的象棋杂志上不同的作者发表了共计40种不同的见解，后来还有人利用图论的方法得出共有92种摆法.。

在数据结构与算法中，八皇后问题是一个经典使用回溯思想解决问题的案例。

回溯思路

我们发现在一个8*8的棋盘上，要放置8个皇后那么肯定是每一行都只会放置一个皇后，所以我们再放置皇后的过程中，我们每次都从这一行的第一个位置放置 ，查看是否与之前的发生冲突，冲突就这一行的下一个，如果这一行的都无法放置，那么回溯至上一个皇后的位置，重新在一行放置下一个位置试试，，，放置这个皇后成功后我们重新放置下一个皇后。。。

代码实现

通过上面的回溯分析，我们发现除了一个放置皇后位置的方法还需要一个检查该皇后位置时候冲突的方法 ，便于我们每次递归到下一个位置的时候检查是否冲突。

/** @Author: 云萧YYY @DateTime: 2021/08/14 @Description: 回溯法解决八皇后问题 */
public class Queen {

  private int max = 8;
  /** array 是这样子的一个数组 {0，4，7，5，2，6，1，3} ，此时这个数组的i表示棋盘的行 */
  private int[] array = new int[max];

  public static void main(String[] args) {
    //
    Queen queen = new Queen();
    // 从第一个皇后开始寻找
    queen.check(0);
  }

  /**
   * *
   *
   * @param n 1.第几个皇后表示，当前的皇后是第几个
   */
  public void check(int n) {

    // 如果是第九个皇后那么我就结束
    if (n == 8) {
      printArray();
      return;
    }
    /** 循环棋盘的每一行 */
    for (int i = 0; i < 8; i++) {
      /** 将第n个皇后的位置记录下来，放入数组，看看是否发生冲突 */
      array[n] = i;
      /** 如果这一个皇后放着不会产生冲突 ，那么看下一皇后 */
      if (judge(n)) {
        check(n + 1);
      }
    }
  }

  /**
   * * 判断这个皇后是否可以放在这个棋盘上的这个位置
   *
   * @param n 第几个皇后
   * @return
   */
  public boolean judge(int n) {
    // 由于每个皇后在棋盘上的每一行只能放一个，
    for (int i = 0; i < n; i++) {
      // 判断 是否在同一列上 和对角线上
      if (array[i] == array[n] || Math.abs(i - n) == Math.abs(array[i] - array[n])) {
        return false;
      }
    }
    return true;
  }

  public void printArray() {
    for (int i = 0; i < array.length; i++) {
      //
      System.out.print(array[i] + ",");
    }
    System.out.println();
  }
}

代码说明

1. 我们定义了一个数组，来存放八个皇后的位置，使用array[i],表示当前在第几列上，i表示第几行。
2. 由于我们使用一维数组来表示这个棋盘的位置，以及皇后的位置信息，那么我们在判断位置是否冲突的方法也变得简单和不同。
3. 我们需要遍历放置这个皇后之前位置的数组，如果又相同的那么说 在同一列上， Math.abs(i - n) == Math.abs(array[i] - array[n] 这个如果学过数学的都知道 对角线位置 x的变化量 与y的变化量时一致 所以 在这里借鉴了数学上的正比例函数斜率为1 ，即表示 行数的变化量 等于列数的变化量时 说明在同一斜线上。

问题说明：

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：

在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。

1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。在计算机问世后有更多的方法。

问题分析：

对于一个8 x 8的棋盘来说，我们很容易想象到使用二维数组来解决这个问题，但实际上我们只需要使用一个一维数组。

我们通过一维数组arr[8]来解决，首先我们可以利用下标 i 用来代表行数-1，arr[i]中的值代表列数-1，这样我们就很好的完成了对于一个棋盘的设计。

步骤：

1. 将第一个王后放在第一行的第一列。

2. 将第二个皇后放置第二行的第一列，然后进行判断是否满足条件，如果不满足则放置在第二列、第三列...，直到满足条件。

3. 继续第三个皇后放置第三行的第一列，然后继续判断是否满足，如果不满足则放置第二列、第三列... 。

4. 当得到一个正确的解后，我们可以将其打印出来，然后进行回溯，重新回到第一步，然后重复2、3、4步，直到所有的情况都结束，完成程序。

代码实现如下:

public class Queue02{
     static int Max=8;
     static int a[]=new int[Max]; 
     static int count=0;
	public static void main(String[] args){
		put(0);
		System.out.println("最多有"+count+"种排序");

	}
	public static void print(){
		count++;
		for(int i=0;i<Max;i++){
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}

	public static boolean judge(int n){
		for(int i=0;i<n;i++){
			if(a[n]==a[i] || n-i==Math.abs(a[n]-a[i])){
				return false;
			}
		}
		return true;
	}

	public static void put(int n){
            //打印完结束
		if(n == Max){
			print();
			return;
		}

		for(int i=0;i<Max;i++){
			a[n]=i;
			if(judge(n)){
				put(n+1);
			}
		}
	}
}

 就此实现八皇后问题。