递归入门

简单迷宫问题

判断能否找到出路即可

MiGong

为穷尽所有路线！仅选择了一种迷宫探索的策略（使用if else-if结构-》下右上左策略）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package com.yukinoshita.dataStructure.recursion;

public class MiGong {
    public static void main(String[] args) {
        int[][] map = new int[8][7];
        //1为墙

        for (int j = 0; j < 7; j++) {
            map[0][j] = 1;
            map[7][j] = 1;
        }
        for (int i = 1; i <= 6; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
//        for(int i=0;i<8;i++){
//            for(int j=0;j<7;j++){
//                System.out.print(map[i][j]+" ");
//            }
//            System.out.println();
//        }
        if (findWay(map, 1, 1)) {
            System.out.println("Yes，可找到路：");
            //输出路径
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 7; j++) {
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
        } else {
            System.out.println("No");
        }
    }

    /**
     * 若能走到map[6][5],说明通路找到
     * map[i][j]为0表示没做够，1表示为墙，2表示可以走，3表示已走过
     * 策略：下->右->上->左
     *
     * @param map 传入的地图
     * @param i   从哪个位置开始走
     * @param j
     * @return 若能走通，true；反之为false
     */
    public static boolean findWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) {
            return true;
        } else {
            if (map[i][j] == 0) {
                map[i][j] = 2;//假定该点可以走通
                if (findWay(map, i + 1, j)) {
                    return true;
                } else if (findWay(map, i, j + 1)) {
                    return true;
                } else if (findWay(map, i - 1, j)) {
                    return true;
                } else if (findWay(map, i, j - 1)) {
                    return true;
                } else {//改点走不通，是死路
                    map[i][j] = 3;
                    return false;
                }

            } else {//map[i][j]!=0 可能为1，2，3
                return false;
            }
        }
    }
}


八皇后问题(经典)

问题：在8×8的棋盘上放置8个皇后，任意两个皇后不能位于同一行、同一列、同一斜线，问有多少种摆法？

思路分析

  1. 第一个皇后先放第一行第一列
  2. 第二个皇后放第二行第一列、判断是否ok，不ok再判断第二列、第三列…直到找到一个位置合适
  3. 后续几个皇后的放置同理，直至最后一个皇后也放置成功，找到了一个成功解
  4. 当得到了一个正确解后，在栈回退到上一个栈时，开始回溯…即，将第一个皇后放在第一行第一列的所有正确解全部得到
  5. 然后再将第一个皇后放在第一行第二列，循环执行1234，直至第一个皇后八列均放置过。

说明：理论上应该创建一个二维数组来表示棋盘，但是可以通过算法用一个一维数组解决问题——arr[8]={0,4,7,5,2,6,1,3}，下标对应的是第几个皇后。故，arr[i]=val，表示第i+1个皇后放在第i+1行、第val+1列上

代码实现

Queue8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package com.yukinoshita.dataStructure.recursion;

//八皇后问题
public class Queue8 {
    int max = 8;
    int[] array = new int[max];
    static int count = 0;

    public static void main(String[] args) {
        Queue8 q = new Queue8();
        q.check(0);
        System.out.printf("解法一共有：%d种", count);
    }

    private void check(int n) {
        if (n == max) {//说明已经放置了八个皇后（0-7）
            print();
            return;
        }

        //对于第n个皇后，每一列依次去放到每一列j：
        for (int j = 0; j < 8; j++) {
            array[n] = j;
            if (!isAttack(n)) {
                check(n + 1);
            }
        }
    }

    //检查摆放第n个皇后时位置是否冲突的方法
    private boolean isAttack(int n) {
        for (int i = 0; i < n; i++) {
//            if(array[i]==array[n] || array[i]+n-i==array[n] || array[i]-i+n==array[n]){
//                return true;
//            }
            //分别为判断是否在同一列、同一斜线的条件
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return true;
            }
        }
        return false;
    }

    //将8个皇后位置信息输出的方法
    private void print() {
        for (int i = 0; i < 8; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
        count++;
    }
}