Java递归实现迷宫问题和八皇后

递归

1.概念

简单来说：递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁

2.规则

• 每当方法被调用，就会开辟一个独立空间

• 方法的变量是独立的，不会相互影响的

• 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据

• 递归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError

• 当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

迷宫问题

1.思路分析

1、如果小球能到map[6][5]那么就代表通关的路找到了
2、规则：
- 当map[i][j] = 0 表示这个点没走过
- 当map[i][j] = 1 表示这个点不能走被挡住了
- 当map[i][j] = 2 表示可以走
- 当map[i][j] = 3 表示该位置已经走过，但是走不通
3、走的时候需要一个策略，下->右->上->左

2.代码实现

package com.sky.recursion;

/**
 * @author 尹稳健~
 * @version 1.0
 * @time 2022/8/30
 */
public class MiGong {
    public static void main(String[] args) {
        //初始化地图
        int row = 8;
        int column = 7;
        int[][] map = getMap(row, column);

        // 设置挡板
        map[3][1] = 1;
        map[3][2] = 1;
        map[1][2] = 1;
        map[2][2] = 1;

        System.out.println("===========开始跑图===========");
        getWay(map,1,1);

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }


    }

    /**
     * 初始化地图 , 二维数组中为 1 说明被挡住了
     * @param row   有多少行
     * @param column    有多少列
     * @return
     */
    public static int[][] getMap(Integer row,Integer column){
        int[][] map = new int[row][column];
        for (int i = 0; i< row; i++){
            map[i][0] = 1;
            map[i][6] = 1;
        }
        for (int i = 0; i < column; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        return map;
    }

    /**
     * 找到出迷宫的路
     * 说明：
     *  1、如果小球能到map[6][5]那么就代表通关的路找到了
     *  2、规则：当map[i][j] = 0 表示这个点没走过
     *          当map[i][j] = 1 表示这个点不能走被挡住了
     *          当map[i][j] = 2 表示可以走
     *          当map[i][j] = 3 表示该位置已经走过，但是走不通
     * 3、走的时候需要一个策略，下->右->上->左
     * @param map  地图
     * @param i 坐标起点
     * @param j 坐标起点
     * @return true代表找到了，false代表没找到
     */
    public static boolean getWay(int[][] map,int i, int j){
        // 到达终点
        if (map[6][5] == 2){
            return true;
        }else{
            // 当该点等于0时，说明这个点还没走过，我们可以假设他走的通
            if (map[i][j] == 0){
                // 假设当前点可以走
                map[i][j] = 2;
                // 先向下走
                if (getWay(map,i+1,j)){
                    return true;
                    // 向右走
                }else if (getWay(map,i,j+1)){
                    return true;
                    // 向上走
                }else if (getWay(map,i-1,j)){
                    return true;
                    // 向左走
                }else if (getWay(map,i,j-1)){
                    return true;
                }else{
                    // 上下左右都走不通
                    map[i][j] = 3;
                    return false;
                }
            }else{
                // 当判断到达这里时，说明该点是 1 或 2 或 3
                return false;
            }
        }
    }
}

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

3.运行结果

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 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 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

八皇后问题

1.概念

八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。

2.思路分析

• 将第一个皇后放在第一行第一列
• 将第二个皇后放在第二行第一列，判断是否会和其他皇后在同一行或同一列或在同一斜线，如若在，那么将其放在第二列、第三列依次。。。直到不相互攻击
• 将第三个皇后放在第三行第一列，判断是否会和其他皇后相互攻击，如果相互攻击，将其放在第二列，第三列、第四列等等，以此类推，在摆放的过程中，有可能会改动前面所放皇后的为止（回溯）
• 当得到一个正确的解时，就会回溯到上一行，由此来找出第一个皇后在第一行第一列的所有解
• 再将抵押给皇后放在第一行第二列，并重复以上步骤
• 注意：
  • 棋盘本身应该时二维数组组成，但因为皇后所在的行数时固定的，那么可以简化为一个一维数组，其中的值表示皇后所在的列
  • 数组下表代表皇后所在行数+1，所以判断是否时，只需要判断是否在同一列和同一斜线即可
    • 是否同列：值是否相同
    • 是否同一斜线： 行号 - 行号 是否等于 列号 - 列号 ，且列号相减要取绝对值

3.代码实现

package com.sky.recursion;

/**
 * @author 尹稳健~
 * @version 1.0
 * @time 2022/8/30
 */
public class Queue8 {
    /** 统计有多少种摆法 */
    static int num = 0;

    /** 一共八个皇后 */
    static int max = 8;
    /** 摆放位置 索引下标 + 1 代表 第几行   索引值代表  第几列 */
    static int[] arr = new int[max];

    public static void main(String[] args) {
        check(0);
        System.out.println("一共有"+num+"种");
    }

    /** 打印 */
    public static void print(){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"");
        }
        System.out.println();
        num ++;
    }

    /** 判断当前皇后是否会和之前按的皇后相互攻击 */
    public static boolean judge(int position){
        for (int i = 0; i < position; i++) {
            /**
             * 如果两个皇后在同一列就冲突
             * 同一斜线也冲突，索引下标代表行
             * 行号 - 行号 == 列号 - 列号  那么就是在同一斜线上
             */
            if (arr[i] == arr[position] || position-i == Math.abs(arr[position] - arr[i])){
                return false;
            }
        }
        return true;
    }

    /** 检查皇后应放的位置 */
    public static void check(int queue){
        // 如果达到8那么就代表已经填满了
        if (queue == max){
            print();
            return;
        }
        // 把皇后放在每一列上，判断是否会和之前放置的起冲突
        for (int i = 0; i < max; i++) {
            // 每次都是从第queue行第一列开始
            arr[queue] = i;
            if (judge(queue)){
                // 不冲突，放下一个皇后
                check(queue+1);
            }
            // 如果冲突了，那么就会往后移一位，就相当于列+1，如果后面的行都冲突就会回溯
        }
    }
}

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

4.结果

一共92种
1