package com.tk.recursion;

/**
 * @author taoke
 * @desc 8皇后问题
 * @email 1504806660@qq.com
 * @date 2022/1/2 15:39
 */
public class Queue8 {

    /**
     * 最多8个皇后
     */
    public static int max = 8;

    /**
     * 数组棋盘
     */
    public static int[] array = new int[max];

    /**
     * 最多多少种情况
     */
    public static int count;

    public static void main(String[] args) {
        handleData(0);
        System.out.printf("一共%d种情况\n", count);
    }

    /**
     * 处理数据
     *
     * @param n 当前第n个皇后
     */
    public static void handleData(int n) {
        //n==8，退出推归
        if (n == max) {
            print();
            return;
        }
        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //获取第n个皇后放的位置，根据judge方法来确定
            array[n] = i;
            if (judge(n)) {//不冲突继续放置皇后，否则依次放入皇后，i++
                handleData(n + 1);
            }
        }
    }

    /**
     * 判断当前这个皇后和前面n个皇后位置是否冲突
     * 当两个皇后在同一行/同一列/同一斜线为冲突
     *
     * @param n 当前第n个皇后 1<=n<=8
     * @return 位置是否冲突
     */
    public static boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            //array[i] == array[n] 代表为同一列,n一直是累加的，所以不可能为同一行，
            // 斜率k=(y1-y2)/(x1-x2),k=1 代表为直角,说明在同一直线，即 y1-y2=x1-x2
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return false;
            }
        }
        return true;

    }

    /**
     * 打印8皇后所在位置
     */
    public static void print() {
        count++;
        for (int i = 0; i < max; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
    }
}