1.什么是八皇后問題？

在這里插入圖片描述

游戲的一種，感興趣的小伙伴可以去玩一下。規(guī)則如下：
在 8 * 8 的棋盤上，任何兩個皇后都不能處于同一行同一列或同一個斜線上。

2.什么是遞歸？
關(guān)于遞歸的簡單描述

3.解決方式

package xmht.datastructuresandalgorithms.datastructure;

/**
 * @author shengjk1
 * @date 2020/3/4
 */
/*
8皇后問題，在 8 * 8 的棋盤上，任何兩個皇后都不能處于同一行同一列或同一個斜線上。

1.第一個皇后先放第一行第一列
2.第二個皇后放在第二行第一列，然后判斷是否ok，如果不 ok，繼續(xù)放在第二列、第三列，依次把所有列都放完，找到一個合適的
3.繼續(xù)第三個皇后，還是第一列、第二列......直到第8個皇后也能放在一個不沖突的位置，算是找到了一個正確的解。
4.當(dāng)?shù)玫降谝粋€正確解時，在棧回退到上一個棧時，就會開始回溯，即將第一個皇后，放到第一列的所有正確解全部找到。
5.然后回頭繼續(xù)第一個皇后放第二列，后面繼續(xù)循環(huán)執(zhí)行1234步驟。


理論上應(yīng)該創(chuàng)建一個二維數(shù)組來表示棋盤，但是實際上可以通過算法，用一個一維數(shù)組即可解決問題。arr[8]={0,1,2,3,4,5,6,7} 對應(yīng)的 arr 下標(biāo)
表示第幾行，即第幾個皇后，arr[i]=val,val表示第i+1個皇后，放在第i+1行的第val+1列。
 */
public class Queue8 {
    //定義一個有多少個皇后
    int max = 8;
    //定義數(shù)組 arrya,保存皇后存放位置的結(jié)果。
    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);
    }
    
    
    //這一塊會有遞歸會有回溯，其實還是挺巧妙的，很值得細(xì)細(xì)體會。
    private void check(int n) {
        //相當(dāng)于該放第 9 個皇后了
        if (n == max) {
            count++;
            print();
            return;
        }
        
        //依次放入皇后，并判斷是否沖突
        //這個的max 其實是列數(shù)
        for (int i = 0; i < max; i++) {
            //先把皇后 n 放到該行的第一列
            array[n] = i;
            //判斷當(dāng)放置第 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.其他
現(xiàn)在有點體會到，遞歸解決迷宮問題的巧妙之處了。