利用递归解决八皇后问题

1.什么是八皇后问题？

在这里插入图片描述

游戏的一种，感兴趣的小伙伴可以去玩一下。规则如下：
在 8 * 8 的棋盘上，任何两个皇后都不能处于同一行同一列或同一个斜线上。

2.什么是递归？
关于递归的简单描述

3.解决方式

package xmht.datastructuresandalgorithms.datastructure;

/**
 * @author shengjk1
 * @date 2020/3/4
 */
/*
8皇后问题，在 8 * 8 的棋盘上，任何两个皇后都不能处于同一行同一列或同一个斜线上。

1.第一个皇后先放第一行第一列
2.第二个皇后放在第二行第一列，然后判断是否ok，如果不 ok，继续放在第二列、第三列，依次把所有列都放完，找到一个合适的
3.继续第三个皇后，还是第一列、第二列......直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确的解。
4.当得到第一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解全部找到。
5.然后回头继续第一个皇后放第二列，后面继续循环执行1234步骤。


理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题。arr[8]={0,1,2,3,4,5,6,7} 对应的 arr 下标
表示第几行，即第几个皇后，arr[i]=val,val表示第i+1个皇后，放在第i+1行的第val+1列。
 */
public class Queue8 {
    //定义一个有多少个皇后
    int max = 8;
    //定义数组 arrya,保存皇后存放位置的结果。
    int[] array = new int[max];
//  int[] array = {-1, -1, -1, -1, -1, -1, -1, -1};
    
    static int count = 0;
    
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        // 从第 0 行开始
        queue8.check(0);
        System.out.println(count);
    }
    
    
    //这一块会有递归会有回溯，其实还是挺巧妙的，很值得细细体会。
    private void check(int n) {
        //相当于该放第 9 个皇后了
        if (n == max) {
            count++;
            print();
            return;
        }
        
        //依次放入皇后，并判断是否冲突
        //这个的max 其实是列数
        for (int i = 0; i < max; i++) {
            //先把皇后 n 放到该行的第一列
            array[n] = i;
            //判断当放置第 n 个皇后置第 i列时，是否与之前的n-1个皇后冲突
            if (judge(n)) {
                //不冲突，就接着放下一个皇后。
                check(n + 1);
            }
        }
    }
    
    
    /*
     1.arrya[i]==arrya[n]表示判断第n个皇后是否与前面 n-1 个皇后在同一列
     2.Math.abs(n - i) == Math.abs(array[n] - array[i])表示判断第 n 个皇后是否与第 i 个皇后在同一个斜线上。(列差等于行差，肯定在同一个斜线上)
     3.没有必要判断是否在同一行，因为 n 就是表示的第几行，而 n 是形参，是不断变化的
     */
    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return false;
            }
        }
        return true;
    }
    
    //输出皇后的位置
    private void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

4.其他
现在有点体会到，递归解决迷宫问题的巧妙之处了。