遞迴的基本規則

• 遞迴中的方法的區域性變數都是獨立的
• 如果方法的形參是參照型別, 由於傳遞的是指標遞迴方法之間是共用的
• 遞迴必須向退出的條件逼近, 否則就是無限遞迴

迷宮問題

1. map[i][j]: 0表示未走過, 可以嘗試; 1表示牆; 2表示該路, 可以走通; 3表示該路, 已走過, 但走不通
2. 當 map[6][5] == 2, 則已到達目的地(最右下角), 結束遞迴

public class MazeApp {
    public static void main(String[] args) {
        /** 通過二維陣列, 模擬8行7列的迷宮地圖*/
        int horizontalNum = 8;
        int verticalNum = 7;
        int[][] map = new int[horizontalNum][verticalNum];
        /** 第1行和8行, 使用1填牆*/
        for (int v = 0; v < verticalNum; v++) {
            /** 從1(0)列開始, 橫向只將給1-8(0-7)行填1*/
            map[0][v] = 1;
            map[7][v] = 1;
        }
        /** 第1列和7行, 使用1填牆*/
        for (int h = 1; h < horizontalNum - 1; h++) {
            /** 從2(1)行開始到7行(6), 迴圈只給每行首元素(0)和尾元素(6)填1*/
            map[h][0] = 1;
            map[h][6] = 1;
        }
        /** 內部設定擋板*/
        map[3][1] = 1;
        map[3][2] = 1;
//		map[1][2] = 1;
//		map[2][2] = 1;

        /** 列印地圖*/
        System.out.println("地圖:");
        for (int h = 0; h < horizontalNum; h++) {
            for (int v = 0; v < verticalNum; v++) {
                System.out.print(map[h][v] + " ");
            }
            System.out.println();
        }

        /** 策略1: 從第2行&第2列開始起步*/
        setStrategy1(map, 1, 1);
        /** 策略2*/
        //setStrategy2(map, 1, 1);

        System.out.println("走過的路線:");
        for (int h = 0; h < horizontalNum; h++) {
            for (int v = 0; v < verticalNum; v++) {
                System.out.print(map[h][v] + " ");
            }
            System.out.println();
        }
    }

    /** 嘗試方向策略: 下->右->上->左*/
    public static boolean setStrategy1(int[][] map, int h, int v) {
        /** 已到達目的地(最右下角), 結束遞迴*/
        if(map[6][5] == 2) {
            return true;
        } else {
            /** 0表示未走過, 可以嘗試*/
            if(map[h][v] == 0) {
                /** 假定當前點是可以走通*/
                map[h][v] = 2;
                if(setStrategy1(map, h + 1, v)) { /** 向下走*/
                    return true;
                } else if (setStrategy1(map, h, v + 1)) { /** 向右走*/
                    return true;
                } else if (setStrategy1(map, h - 1, v)) { /** 向上走*/
                    return true;
                } else if (setStrategy1(map, h, v - 1)){ /** 向左走*/
                    return true;
                } else { /** 已走過, 但走不通的點*/
                    map[h][v] = 3;
                    return false;
                }
            } else {
                return false;
            }
        }
    }

    /** 嘗試方向策略: 上->右->下->左*/
    public static boolean setStrategy2(int[][] map, int h, int v) {
        /** 已到達目的地(最右下角), 結束遞迴*/
        if(map[6][5] == 2) {
            return true;
        } else {
            /** 0表示未走過, 可以嘗試*/
            if(map[h][v] == 0) {
                /** 假定當前點是可以走通*/
                map[h][v] = 2;
                if(setStrategy2(map, h - 1, v)) { /** 向上走*/
                    return true;
                } else if (setStrategy2(map, h, v + 1)) { /** 向右走*/
                    return true;
                } else if (setStrategy2(map, h + 1, v)) { /** 向下走*/
                    return true;
                } else if (setStrategy2(map, h, v - 1)){ /** 向左走*/
                    return true;
                } else { /** 已走過, 但走不通的點*/
                    map[h][v] = 3;
                    return false;
                }
            } else {
                return false;
            }
        }
    }
}

> 地圖:
> 1 1 1 1 1 1 1
> 1 0 0 0 0 0 1
> 1 0 0 0 0 0 1
> 1 1 1 0 0 0 1
> 1 0 0 0 0 0 1
> 1 0 0 0 0 0 1
> 1 0 0 0 0 0 1
> 1 1 1 1 1 1 1

> 走過的路線(策略1):
> 1 1 1 1 1 1 1
> 1 2 0 0 0 0 1
> 1 2 2 2 0 0 1
> 1 1 1 2 0 0 1
> 1 0 0 2 0 0 1
> 1 0 0 2 0 0 1
> 1 0 0 2 2 2 1
> 1 1 1 1 1 1 1

> 走過的路線(策略2):
> 1 1 1 1 1 1 1
> 1 2 2 2 2 2 1
> 1 0 0 0 0 2 1
> 1 1 1 0 0 2 1
> 1 0 0 0 0 2 1
> 1 0 0 0 0 2 1
> 1 0 0 0 0 2 1
> 1 1 1 1 1 1 1

# 當內部設定擋板
map[3][1] = 1;
map[3][2] = 1;
map[1][2] = 1;
map[2][2] = 1;

## 執行過程(回溯):
* 1. (1, 1)
* 2. (2, 1) return true;
1 1 1 1 1 1 1
1 2 1 0 0 0 1
1 2 1 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
* 3. (3, 1) return false; map[3][1] != 0
* 4. (2, 2) return false; map[2][2] != 0
* 5. (1, 1) return false; map[1][1] != 0
* 6. (2, 0) return false; map[2][0] = 3
1 1 1 1 1 1 1
1 2 1 0 0 0 1
1 3 1 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
* 7. (1, 2) return false; map[1][2] != 0
* 8. (0, 1) return false; map[0][1] != 0
* 9. (1, 0) return false; map[1][0] = 3
* 最後輸出:
1 1 1 1 1 1 1
1 3 1 0 0 0 1
1 3 1 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1

八皇后問題

public class EightQueensApp {
    /** 定義皇后數*/
    static int max = 8;
    static int[] queens = new int[max];
    /** 解決方式的總數*/
    static int count = 0;
    /** 判斷衝突的總數*/
    static int conflictedCount = 0;
    public static void main(String[] args) {
        setPosition(0);
        System.out.println("解決方式的總數為 " + count);
        System.out.println("判斷衝突的總數為 " + conflictedCount);
    }

    /**
     * 1) num是第 num個皇后(第幾行的皇后)
     * 2) 經過 for(int pos = 0; pos < max; pos++)依次放好8皇后
     * 3) 迴圈遞迴呼叫 setPosition(num + 1), 直到8位元皇后放好完成了一個解決方式後列印
     * */
    private static void setPosition(int num) {
        /** 8位元皇后已放好, 完成了一個解決方式*/
        if(num == max) {
            print();
            return;
        }

        /** 迴圈依次放好8皇后*/
        for(int pos = 0; pos < max; pos++) {
            /** 第 num的皇后放到 pos位置上後*/
            queens[num] = pos;
            /** 放好第 num皇后到 pos位置後, 判斷是否衝突*/
            if(judge(num)) {
                /** 如果不衝突, 接著放下一個皇后*/
                setPosition(num + 1);
            }
            /** 如果衝突, 就會將第 num的皇后, 向右移一位 array[num] = pos, 再繼續判斷*/
        }
    }

    /** 判斷規則: 棋盤上放置8個棋子(皇后), 且相互不衝突(皇后在同一行, 同一列和同一斜線上都屬衝突)*/
    private static boolean judge(int num) {
        conflictedCount++;
        for(int pos = 0; pos < num; pos++) {
            /**
             * 1) queens[num] == queens[pos]判斷第 num個的皇后是否與 pos位置的皇后在同一個列上?
             * 2) Math.abs(num - pos) == Math.abs(queens[num] - queens[pos])判斷第 num個的皇后是否與 pos位置的皇后在同一個斜線上?
             * 3) 無需判斷行, 因為 num每次都在遞增的
             * */
            if(queens[num] == queens[pos] ||
                    Math.abs(num - pos) == Math.abs(queens[num] - queens[pos])) {
                return false;
            }
        }
        return true;
    }

    /** 列印解決方式(每次列印一種)*/
    private static void print() {
        count++;
        for (int i = 0; i < queens.length; i++) {
            System.out.print(queens[i] + " ");
        }
        System.out.println("第 " + count + "次");
    }

}

輸出:
> 0 4 7 5 2 6 1 3 第 1次
> 0 5 7 2 6 3 1 4 第 2次
> 0 6 3 5 7 1 4 2 第 3次
> 0 6 4 7 1 3 5 2 第 4次
> 1 3 5 7 2 0 6 4 第 5次
> 1 4 6 0 2 7 5 3 第 6次
> 1 4 6 3 0 7 5 2 第 7次
...
...
> 解決方式的總數為 92
> 判斷衝突的總數為 15720

如果您覺得有幫助，歡迎點贊哦 ~ 謝謝!!