資料結構 - 遞歸 回溯算法（八皇後問題）

遊戲位址自己寫完了可以根據結果去測試一下。

算法分析

八皇後問題算法思路分析

1）第一個皇後先放第一行第一列

2）第二個皇後放在第二行第一列、然後判斷是否OK， 如果不OK，繼續放在.第二列、第三列、依次把所有列都放完，找到一個合适

3）繼續第三個皇後，還是第一列、第二列……直到第8個皇後也能放在一個不沖突的位置，算是找到了一個正确解

4)當得到一個正确解時，在棧回退到上一個棧時，就會開始回溯，即将第一個皇後，放到第一列的所有正确解，全部得到.

然後回頭繼續第一個皇後放第二列，後面繼續循環執行 1,2,3,4的步驟 【示意圖】

說明：理論上應該建立一個二維數組來表示棋盤，但是實際上可以通過算法，用一個一維數組即可解決問題. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //對應arr 下标 表示第幾行，即第幾個皇後，arr[i] = val , val 表示第i+1個皇後，放在第i+1行的第val+1列

實作代碼

1）判斷是否沖突

//檢視當我們放置第n個皇後，就去檢測該皇後和前置的皇後是否沖突
    public static boolean judge(int n){
        for (int i = 0; i < n; i++){
            //下面判斷是，在同一列 或者 在同一斜線上，abs是取絕對值
            if (array[n] == array[i] || Math.abs(array[n] - array[i]) == Math.abs(n - i)){
                return false;
            }
        }
        return true;
    }
           

2）主要邏輯（遞歸與回溯）

// n 代表第幾行
    public static void check(int n) {

        if (n == max) {//也就是0-7八個皇後都放置好了
            //輸出目前的 一個解
            for (int i = 0; i < max; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println("");
            count ++;
            return;
        }

        //開始放置循環每行的位置
        for (int i = 1;i < max+1; i++){
            //指派，也就是賦縱坐标位置
            array[n] = i;
            //判斷是否沖突
            if (judge(n)){ //如果不沖突
                check(n+1); //就放置下一個位置
            }

        }
    }
    
           

全部代碼

package DataStructures.sparsearray;

/**
 * 簡單的實作八皇後問題（沒有貪心算法優化）
 */
public class queue8 {
    static int max = 8;
    static int[] array = new int[max];
    static int count = 0;
    public static void main(String[] args) {
        //定義一個max表示一共有多少個皇後

        //定義一位數組，用下标+1來表示行，用值來表示縱坐标,比如array{1,5,8,6,3,7,2,4}
        //測試
        check(0);
        System.out.println("總共有："+ count+"次解");
    }

//1.第一個皇後先放第一行第一列
//2.第二個皇後放在第二行第一列、然後判斷是否OK， 如果不OK，繼續放在第二列、第三列、依次把所有列都放完，找到一個合适
//3.繼續第三個皇後，還是第一列、第二列……直到第8個皇後也能放在一個不沖突的位置，算是找到了一個正确解
//4.當得到一個正确解時，在棧回退到上一個棧時，就會開始回溯，即将第一個皇後，放到第一列的所有正确解，全部得到.
//5.然後回頭繼續第一個皇後放第二列，後面繼續循環執行 1,2,3,4的步驟

//編寫一個方法

    //n 代表第幾行
    public static void check(int n) {

        if (n == max) {//也就是0-7八個皇後都放置好了
            //輸出目前的 一個解
            for (int i = 0; i < max; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println("");
            count ++;
            return;
        }

        //開始放置循環每行的位置
        for (int i = 1;i < max+1; i++){//這裡循環就把一行的每個位置都判斷一次，在回溯回來後進行判斷在執行check
            //指派，也就是賦縱坐标位置
            array[n] = i;
            //判斷是否沖突
            if (judge(n)){ //如果不沖突
                check(n+1); //就放置下一個位置
            }

        }
    }

    //檢視當我們放置第n個皇後，就去檢測該皇後和前置的皇後是否沖突
    public static boolean judge(int n){
        for (int i = 0; i < n; i++){
            //下面判斷是，在同一列 或者 在同一斜線上，abs是取絕對值
            if (array[n] == array[i] || Math.abs(array[n] - array[i]) == Math.abs(n - i)){
                return false;
            }
        }
        return true;
    }


}
           

最後結果是92種