15.八皇后问题

1.八皇后问题介绍

image.png

2.思路分析

1.将第一个皇后放在第一行第一列
2.将第二个皇后放在第二行第一列，判断与第一个皇后是否冲突，如果冲突，将它放在第二列、第三列......直到找到不冲突的位置
3.将第三个皇后放在第三行第一列，判断是否冲突，如果冲突，将它放在第二列、第三列......直到找到不冲突的位置
4.之后几列和2，3步骤相同，寻找一个正确解，如果找不到就将前一个皇后向后移一位，重复1，2，3步骤

5. 找到一个正确解后，从栈顶元素开始，在这一行找其它位置不冲突的正确解，到栈底时就会找到第一个皇后放在第一行第一列的所有正确解

6.将第一个皇后放在第一行第二列，重复2，3，4，5步

注：这里我们用一个一维数组来存储，数组中第一个元素表示第一个皇后放在第一行的第arr[0]+1列，第二个皇后放在第二行的第arr[1]+1列.......,第i个皇后放在第i行的第arr[i]+1列.arr[i] = val表示第i+1个皇后放在第i+1行第val+1列。

3.代码实现

package com.yc.day03.recursion;

public class Queue8 {
    //定义皇后个数及数组
    int max = 8;
    int arr[] = new int[8];
    static int count = 0;
    static int judgeCount = 0;
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("共有%d种摆法\n",count);
        System.out.printf("共判断了%d次",judgeCount);
    }
    /**
     *摆放皇后
     * */
    public void check(int n){

        if(n==max){//当n==max时，是第九个皇后了，表示前八个皇后已经摆放完成
            print();
            count++;
            return;
        }
        for (int i = 0; i < max; i++) {
            //将第n+1个皇后摆放在第n+1行第i+1列
            arr[n] = i;
            if(judge(n)){//如果不冲突，摆放下一个皇后
                check(n+1);
            }
            //如果冲突了，将第n+1个皇后往后移arr[n]=i+1,由于这里i++，所以不用做操作直接进入下次循环
        }
    }
    /**
     * 摆放第n+1个元素时判断是否与前面所有元素冲突
     * */
    public boolean judge(int n){
        judgeCount++;
        for (int i = 0; i < n; i++) {
            /**
             * 说明：
             * 1.arr[i]==arr[n]用于判断第n+1个皇后是否与第i+1个皇后在同一列
             * 2.Math.abs(n-i)==Math.abs(arr[n]-arr[i])用于判断第n+1个皇后是否与第i+1个皇后在斜线上
             * */
            if(arr[i]==arr[n]||Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
                return false;
            }
        }
        return true;
    }
    /**
     * 打印数组
     * */
    public  void print(){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
}