递归、迷宫回溯、八皇后

发表于 | 更新于 | 分类于

数据结构与算法

递归Recursion、迷宫回溯、八皇后问题、排列组合

对于递归大家应该都不陌生了，我们直接看递归的应用。

迷宫回溯

给定一个二维数组，用1表示墙壁，0表示道路，当使用者指定入口和出口时，程序可以从入口走出迷宫。

如这个二维数组：

1
2
3
4
5
6
1  1  1  1  1
1  1  0  0  1
0  0  0  1  1
1  0  0  0  1
1  0  1  1  1
1  0  1  1  1

因为要求比较低，所以实现起来比较简单：

java实现

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
package Recursion;

import java.io.*;

public class Maze {

    //用二维数组表示迷宫地图，约定1为墙壁，0为通路，2为足迹，3为重复走过的点
    int[][] mazeMap;
    //出口坐标
    int goalI;
    int goalJ;

    //以文件方式构造地图数组,这样好设计地图
    public Maze(File mapFile) throws IOException {
        loadMapFile(mapFile);
    }

    //读取地图文件中的二维数组
    public void loadMapFile(File mapFile) throws IOException {
        /*
         * 拿到文件中二维数组的行数列数
         * */
        Reader reader = new FileReader(mapFile);
        BufferedReader bufferedReader = new BufferedReader(reader);
        //查看数组行数
        int rowI = 0;
        //数组列数
        int rowJ = 0;
        //文件每行数据
        String line;
        while ((line = bufferedReader.readLine()) != null) {
            //得到数组行数
            rowI++;
            //每行以两个空格分割
            String[] splits = line.split(" {2}");
            //得到列数
            rowJ = splits.length;

        }
        System.out.println("该地图的二维数组行数：" + rowI);
        System.out.println("该地图的二维数组列数：" + rowJ);
        //初始化对应行列的数组
        mazeMap = new int[rowI][rowJ];
        System.out.println("地图数组初始化完成");

        /*
         * 载入文件中的数组数据
         * */
        //关闭流
        bufferedReader.close();
        //新建流
        reader = new FileReader(mapFile);
        bufferedReader = new BufferedReader(reader);

        //开始读取每行数据
        //数组第i行
        int i = 0;
        while (i < rowI) {
            //读取每行数据
            line = bufferedReader.readLine();
            //以两个空格分割
            String[] splits = line.split(" {2}");
            //处理当前行的数据
            for (int j = 0; j < splits.length; j++) {
                //[打印]每行数据，不换行
                System.out.print(splits[j] + "\t");
                //把当前值转为int，然后赋给二维数组
                mazeMap[i][j] = Integer.parseInt(splits[j]);
            }
            //行数自增
            i++;
            //[打印]每行打印后换行
            System.out.println();
        }
        System.out.println("地图数组数据载入完成！");
    }

    //读取稀疏数组文件
    /*
     * 暂时不需要，地图文件大的话可以转成稀疏数组存放
     * */

    //打印数组
    public void show(){
        //打印数组
        for (int[] valuex : mazeMap) {
            for (int valuey : valuex) {
                System.out.print(valuey + "\t");
            }
            System.out.println();
        }
    }


    //自动寻找迷宫路线，指定一个入口的坐标(x,y)，再指定一个出口的坐标(goalI,goalJ)
    public void autoFind(int x, int y, int goalI, int goalJ) {
        if (mazeMap == null) {
            System.out.println("地图无数据，请先初始化");
        } else {
            //判断输入值是否越界，是否有效
            if (x >= mazeMap[0].length || y >= mazeMap.length || mazeMap[y][x] == 1) {
                System.out.println("该位置不在地图内，或者该位置不能做为入口");
            } else {
                //指定出口坐标
                this.goalI = goalI;
                this.goalJ = goalJ;
                //开始寻路
                System.out.println("开始寻路");
                startFind(x, y);
                //打印数组
                show();
            }
        }
    }

    //递归寻路
    public boolean startFind(int x, int y) {
        //若到达出口
        if (x == goalI && y == goalJ) {
            System.out.println("找到出口");
            return true;
        }
        //若能走通
        if (mazeMap[y][x] == 0) {
            mazeMap[y][x] = 2;
            System.out.println("找到一个点");
            show();
            //接着向上走
            if (startFind(x, y - 1)) {
                return true;
                //向右走
            } else if (startFind(x + 1, y)) {
                return true;
                //向下走
            } else if (startFind(x, y + 1)) {
                return true;
                //向左走
            } else if (startFind(x - 1, y)) {
                return true;
            } else {
                //都走不通
                System.out.println(" ");
                return false;
            }
        }else if (mazeMap[y][x] == 2){
            System.out.println("回溯");
            mazeMap[y][x] = 3;
            show();
            return false;
        }else {
            System.out.println("碰到墙");
            return false;
        }
    }
}


class mapTest {
    public static void main(String[] args) throws IOException {
        //源文件
        File mapFile = new File("D:\\aria2\\mazeMap.data");
        Maze maze = new Maze(mapFile);
        //起始坐标(0,2)，终点坐标(1,5)
        maze.autoFind(0, 2, 1, 5);
    }
}

输出结果

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
该地图的二维数组行数：6
该地图的二维数组列数：5
地图数组初始化完成
1	1	1	1	1	
1	1	0	0	1	
0	0	0	1	1	
1	0	0	0	1	
1	0	1	1	1	
1	0	1	1	1	
地图数组数据载入完成！
开始寻路
找到一个点
1	1	1	1	1	
1	1	0	0	1	
2	0	0	1	1	
1	0	0	0	1	
1	0	1	1	1	
1	0	1	1	1	
碰到墙
找到一个点
1	1	1	1	1	
1	1	0	0	1	
2	2	0	1	1	
1	0	0	0	1	
1	0	1	1	1	
1	0	1	1	1	
碰到墙
找到一个点
1	1	1	1	1	
1	1	0	0	1	
2	2	2	1	1	
1	0	0	0	1	
1	0	1	1	1	
1	0	1	1	1	
找到一个点
1	1	1	1	1	
1	1	2	0	1	
2	2	2	1	1	
1	0	0	0	1	
1	0	1	1	1	
1	0	1	1	1	
碰到墙
找到一个点
1	1	1	1	1	
1	1	2	2	1	
2	2	2	1	1	
1	0	0	0	1	
1	0	1	1	1	
1	0	1	1	1	
碰到墙
碰到墙
碰到墙
回溯
1	1	1	1	1	
1	1	3	2	1	
2	2	2	1	1	
1	0	0	0	1	
1	0	1	1	1	
1	0	1	1	1	
 
回溯
1	1	1	1	1	
1	1	3	2	1	
2	2	3	1	1	
1	0	0	0	1	
1	0	1	1	1	
1	0	1	1	1	
碰到墙
 
碰到墙
找到一个点
1	1	1	1	1	
1	1	3	2	1	
2	2	3	1	1	
1	0	2	0	1	
1	0	1	1	1	
1	0	1	1	1	
碰到墙
找到一个点
1	1	1	1	1	
1	1	3	2	1	
2	2	3	1	1	
1	0	2	2	1	
1	0	1	1	1	
1	0	1	1	1	
碰到墙
碰到墙
碰到墙
回溯
1	1	1	1	1	
1	1	3	2	1	
2	2	3	1	1	
1	0	3	2	1	
1	0	1	1	1	
1	0	1	1	1	
 
碰到墙
找到一个点
1	1	1	1	1	
1	1	3	2	1	
2	2	3	1	1	
1	2	3	2	1	
1	0	1	1	1	
1	0	1	1	1	
回溯
1	1	1	1	1	
1	1	3	2	1	
2	3	3	1	1	
1	2	3	2	1	
1	0	1	1	1	
1	0	1	1	1	
碰到墙
找到一个点
1	1	1	1	1	
1	1	3	2	1	
2	3	3	1	1	
1	2	3	2	1	
1	2	1	1	1	
1	0	1	1	1	
回溯
1	1	1	1	1	
1	1	3	2	1	
2	3	3	1	1	
1	3	3	2	1	
1	2	1	1	1	
1	0	1	1	1	
碰到墙
找到出口
1	1	1	1	1	
1	1	3	2	1	
2	3	3	1	1	
1	3	3	2	1	
1	2	1	1	1	
1	0	1	1	1	

Process finished with exit code 0

八皇后Eight queens

百度百科：

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

针对这个问题，我们可以把棋盘简化成一个普通数组， 把棋盘行数对应为数组下标即可，而不必使用二维数组来表示棋盘，如：

1
2
3
array[8]={0, 6, 3, 5, 7, 1, 4, 2}
//分别对应棋子从第1行到第8行的位置
//每行的值在0~7之间

  • 判断是否在同一列

    • 只需判断与之前已有的值是否相同，设当前行号为n，之前行号为pastN，若在同一列，则有：
    1
    array[n] == array[pastN]

  • 判断是否在同一斜线

    • 只需判断行号之间的差值，与对应行棋子所在位置的差值，是否相同，需要用绝对值来判断：
    1
    2
    //Math.abs(a)返回a的绝对值
    Math.abs( array[n] - array[pastN] )==Math.abs( n - pastN)

  • 判断是否在同一行

    • 显然一维数组不可能有同一行，所以无需判断

java实现

先看一个比较简单的java实现，以后我们再对它进行优化：

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
package Recursion;

import java.util.Arrays;

public class EightQueens {

    //初始化一个数组
    private int[] array = new int[8];
    //对有效结果进行计数
    private int count = 0;

    //使用n表示棋盘的第n+1行，初始为0，表示棋盘第1行，即array[n]


    /**
     * 往棋盘中放入皇后（给数组赋值）
     * @param n 表示当前行号，范围从0到7
     */
    public void addQueen(int n) {

        //当n==8时，说明一个8*8的棋盘每行都放了，此时是要放第9个了
        if (n == 8) {
            count++;
            System.out.println("第" + count + "次的棋子已经放完："+showArrayString());
            return;
        }

        //在当前行放棋子，从0号位放到7号位
        for (int i = 0; i < array.length; i++) {
            //放入棋子
            array[n] = i;
            //每放一个，判断棋子的位置与放过的棋子是否冲突
            //若不冲突
            if (check(n)) {
                //用递归，换到下一行做重复的事情
                addQueen(n + 1);
            }
            //没进入递归，就说明该棋子位置冲突，不用做什么，继续for循环改变棋子位置即可
        }
    }

    //判断是否冲突的方法
    public boolean check(int n) {
        //遍历棋盘的每一行
        for (int pastN = 0; pastN < n; pastN++) {
            //若与当前行的棋子在同列或同一斜线
            if (isSameColumn(n, pastN) || isSameSlant(n, pastN)) {
                return false;
            }
        }
        //循环完毕后能执行到这里，说明不与以前的棋子在同列同斜线
        return true;
    }


    /**
     * 判断是否在同一列
     *
     * @param n     表示当前行
     * @param pastN 表示n之前的任意行
     */
    public boolean isSameColumn(int n, int pastN) {

        return array[n] == array[pastN];
    }

    //判断是否在同一行
    /*这个无需判断，因为肯定不在同一行*/


    //判断是否在同一斜线，使用绝对值
    public boolean isSameSlant(int n, int pastN) {
        return Math.abs(array[n] - array[pastN]) == Math.abs(n - pastN);
    }

    //返回数组的字符串
    public String showArrayString() {
        return Arrays.toString(array);
    }

    //展示数组
    public void show(){
        System.out.println(showArrayString());
    }


}

class eightQueenTest {
    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        eightQueens.addQueen(0);
    }
}

输出结果

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
第1次的棋子已经放完：[0, 4, 7, 5, 2, 6, 1, 3]
第2次的棋子已经放完：[0, 5, 7, 2, 6, 3, 1, 4]
第3次的棋子已经放完：[0, 6, 3, 5, 7, 1, 4, 2]
第4次的棋子已经放完：[0, 6, 4, 7, 1, 3, 5, 2]
第5次的棋子已经放完：[1, 3, 5, 7, 2, 0, 6, 4]
第6次的棋子已经放完：[1, 4, 6, 0, 2, 7, 5, 3]
第7次的棋子已经放完：[1, 4, 6, 3, 0, 7, 5, 2]
第8次的棋子已经放完：[1, 5, 0, 6, 3, 7, 2, 4]
第9次的棋子已经放完：[1, 5, 7, 2, 0, 3, 6, 4]
第10次的棋子已经放完：[1, 6, 2, 5, 7, 4, 0, 3]
第11次的棋子已经放完：[1, 6, 4, 7, 0, 3, 5, 2]
第12次的棋子已经放完：[1, 7, 5, 0, 2, 4, 6, 3]
第13次的棋子已经放完：[2, 0, 6, 4, 7, 1, 3, 5]
第14次的棋子已经放完：[2, 4, 1, 7, 0, 6, 3, 5]
第15次的棋子已经放完：[2, 4, 1, 7, 5, 3, 6, 0]
第16次的棋子已经放完：[2, 4, 6, 0, 3, 1, 7, 5]
第17次的棋子已经放完：[2, 4, 7, 3, 0, 6, 1, 5]
第18次的棋子已经放完：[2, 5, 1, 4, 7, 0, 6, 3]
第19次的棋子已经放完：[2, 5, 1, 6, 0, 3, 7, 4]
第20次的棋子已经放完：[2, 5, 1, 6, 4, 0, 7, 3]
第21次的棋子已经放完：[2, 5, 3, 0, 7, 4, 6, 1]
第22次的棋子已经放完：[2, 5, 3, 1, 7, 4, 6, 0]
第23次的棋子已经放完：[2, 5, 7, 0, 3, 6, 4, 1]
第24次的棋子已经放完：[2, 5, 7, 0, 4, 6, 1, 3]
第25次的棋子已经放完：[2, 5, 7, 1, 3, 0, 6, 4]
第26次的棋子已经放完：[2, 6, 1, 7, 4, 0, 3, 5]
第27次的棋子已经放完：[2, 6, 1, 7, 5, 3, 0, 4]
第28次的棋子已经放完：[2, 7, 3, 6, 0, 5, 1, 4]
第29次的棋子已经放完：[3, 0, 4, 7, 1, 6, 2, 5]
第30次的棋子已经放完：[3, 0, 4, 7, 5, 2, 6, 1]
第31次的棋子已经放完：[3, 1, 4, 7, 5, 0, 2, 6]
第32次的棋子已经放完：[3, 1, 6, 2, 5, 7, 0, 4]
第33次的棋子已经放完：[3, 1, 6, 2, 5, 7, 4, 0]
第34次的棋子已经放完：[3, 1, 6, 4, 0, 7, 5, 2]
第35次的棋子已经放完：[3, 1, 7, 4, 6, 0, 2, 5]
第36次的棋子已经放完：[3, 1, 7, 5, 0, 2, 4, 6]
第37次的棋子已经放完：[3, 5, 0, 4, 1, 7, 2, 6]
第38次的棋子已经放完：[3, 5, 7, 1, 6, 0, 2, 4]
第39次的棋子已经放完：[3, 5, 7, 2, 0, 6, 4, 1]
第40次的棋子已经放完：[3, 6, 0, 7, 4, 1, 5, 2]
第41次的棋子已经放完：[3, 6, 2, 7, 1, 4, 0, 5]
第42次的棋子已经放完：[3, 6, 4, 1, 5, 0, 2, 7]
第43次的棋子已经放完：[3, 6, 4, 2, 0, 5, 7, 1]
第44次的棋子已经放完：[3, 7, 0, 2, 5, 1, 6, 4]
第45次的棋子已经放完：[3, 7, 0, 4, 6, 1, 5, 2]
第46次的棋子已经放完：[3, 7, 4, 2, 0, 6, 1, 5]
第47次的棋子已经放完：[4, 0, 3, 5, 7, 1, 6, 2]
第48次的棋子已经放完：[4, 0, 7, 3, 1, 6, 2, 5]
第49次的棋子已经放完：[4, 0, 7, 5, 2, 6, 1, 3]
第50次的棋子已经放完：[4, 1, 3, 5, 7, 2, 0, 6]
第51次的棋子已经放完：[4, 1, 3, 6, 2, 7, 5, 0]
第52次的棋子已经放完：[4, 1, 5, 0, 6, 3, 7, 2]
第53次的棋子已经放完：[4, 1, 7, 0, 3, 6, 2, 5]
第54次的棋子已经放完：[4, 2, 0, 5, 7, 1, 3, 6]
第55次的棋子已经放完：[4, 2, 0, 6, 1, 7, 5, 3]
第56次的棋子已经放完：[4, 2, 7, 3, 6, 0, 5, 1]
第57次的棋子已经放完：[4, 6, 0, 2, 7, 5, 3, 1]
第58次的棋子已经放完：[4, 6, 0, 3, 1, 7, 5, 2]
第59次的棋子已经放完：[4, 6, 1, 3, 7, 0, 2, 5]
第60次的棋子已经放完：[4, 6, 1, 5, 2, 0, 3, 7]
第61次的棋子已经放完：[4, 6, 1, 5, 2, 0, 7, 3]
第62次的棋子已经放完：[4, 6, 3, 0, 2, 7, 5, 1]
第63次的棋子已经放完：[4, 7, 3, 0, 2, 5, 1, 6]
第64次的棋子已经放完：[4, 7, 3, 0, 6, 1, 5, 2]
第65次的棋子已经放完：[5, 0, 4, 1, 7, 2, 6, 3]
第66次的棋子已经放完：[5, 1, 6, 0, 2, 4, 7, 3]
第67次的棋子已经放完：[5, 1, 6, 0, 3, 7, 4, 2]
第68次的棋子已经放完：[5, 2, 0, 6, 4, 7, 1, 3]
第69次的棋子已经放完：[5, 2, 0, 7, 3, 1, 6, 4]
第70次的棋子已经放完：[5, 2, 0, 7, 4, 1, 3, 6]
第71次的棋子已经放完：[5, 2, 4, 6, 0, 3, 1, 7]
第72次的棋子已经放完：[5, 2, 4, 7, 0, 3, 1, 6]
第73次的棋子已经放完：[5, 2, 6, 1, 3, 7, 0, 4]
第74次的棋子已经放完：[5, 2, 6, 1, 7, 4, 0, 3]
第75次的棋子已经放完：[5, 2, 6, 3, 0, 7, 1, 4]
第76次的棋子已经放完：[5, 3, 0, 4, 7, 1, 6, 2]
第77次的棋子已经放完：[5, 3, 1, 7, 4, 6, 0, 2]
第78次的棋子已经放完：[5, 3, 6, 0, 2, 4, 1, 7]
第79次的棋子已经放完：[5, 3, 6, 0, 7, 1, 4, 2]
第80次的棋子已经放完：[5, 7, 1, 3, 0, 6, 4, 2]
第81次的棋子已经放完：[6, 0, 2, 7, 5, 3, 1, 4]
第82次的棋子已经放完：[6, 1, 3, 0, 7, 4, 2, 5]
第83次的棋子已经放完：[6, 1, 5, 2, 0, 3, 7, 4]
第84次的棋子已经放完：[6, 2, 0, 5, 7, 4, 1, 3]
第85次的棋子已经放完：[6, 2, 7, 1, 4, 0, 5, 3]
第86次的棋子已经放完：[6, 3, 1, 4, 7, 0, 2, 5]
第87次的棋子已经放完：[6, 3, 1, 7, 5, 0, 2, 4]
第88次的棋子已经放完：[6, 4, 2, 0, 5, 7, 1, 3]
第89次的棋子已经放完：[7, 1, 3, 0, 6, 4, 2, 5]
第90次的棋子已经放完：[7, 1, 4, 2, 0, 6, 3, 5]
第91次的棋子已经放完：[7, 2, 0, 5, 1, 4, 6, 3]
第92次的棋子已经放完：[7, 3, 0, 2, 5, 1, 6, 4]

Process finished with exit code 0

所以我们可以看到，共有92种放法。

排列组合

不多说，如

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
package Recursion;

//排列组合
public class SortTest {
    public static void main(String[] args) {

        char[] array = {'A', 'B', 'C'};
        arrange(array, 0, array.length);
    }

    public static void arrange(char[] array, int start, int len) {
        if (start == len - 1) {
            for (int i = 0; i < array.length; i++)
                System.out.print(array[i]);
            System.out.println();
            return;
        }
       
        for (int i = start; i < len; i++) {
            char temp = array[start];
            array[start] = array[i];
            array[i] = temp;
            arrange(array, start + 1, len);
            temp = array[start];
            array[start] = array[i];
            array[i] = temp;
        }
    }
}