【数据结构与算法】使用递归Recursion解决迷宫问题、和八皇后问题

1. 使用递归解决迷宫问题

小球得到的路径，和设置的找路策略有关，即按下右上左顺序，和按上右下左顺序得到的路径不一样

示例如下：

public class MiGong {

    public static void main(String[] args) {

        // 创建一个二维数组，模拟迷宫
        int[][] map = new int[8][7];
        // 使用1表示不能走的区域
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 1; i < 7; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;

        // 输出地图
        System.out.println("初始化的地图的：");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

        // 使用递归回溯给小球找路
        findWay(map, 1, 1);

        // 输出新的地图, 小球走过并标识过的
        System.out.println("小球走过，并标识过的地图：");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

    }

    // i和j表示开始出发的位置，如果小球能找到map[6][5]位置，说明找到
    // 如果找到，就返回true，否则返回false
    // map[i][j]为0表示该点没有走过, 为1表示不能走，为2表示通路可以走，为3表示该点已经走过，但走不通
    public static boolean findWay(int[][] map, int i, int j) {
        // 如果能找到map[6][5]位置，说明找到
        if (map[6][5] == 2) {
            return true;
        } else {
            //如果当前点还没有走过
            if (map[i][j] == 0) {
                // 先假设该点可以走
                map[i][j] = 2;
                // 先向下走，如果可以走，则返回true。否则向其它方向走
                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 {
                // 如果是1、2、3，表示走不通
                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 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. 使用递归解决八皇后问题(回溯算法)

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

八皇后问题算法思路分析：

1. 第一个皇后先放第一行第一列
2. 第二个皇后放在第二行第一列、然后判断是否OK。如果OK，则跳转到第3步；如果不OK，继续放在第二列，再进行判断是否OK，不断的遍历每列直到OK为止
3. 第三个皇后放在第三行第一列，也是不断的遍历直到OK为止。直到第八个皇后OK，则得到一个正确解
4. 如果第八个皇后还有列未遍历完，则继续遍历，看是否还有其它正确解
5. 第八个皇后的所有列遍历完成，则回溯遍历第七个皇后的未遍历的列，如果OK，则第八个皇后放在第八行第一列，继续进行遍历
6. 依次类推，直到第一个皇后的所有列遍历完成，则找到所有正确解

用一维数组表示棋盘：理论上应该创建一个二维数组来表示棋盘，但是可以通过算法，用一个一维数组表示棋盘。例如元素个数为8的arr = {0, 4, 7, 5, 2, 6, 1, 3}。数组的index表示二维数组的行，即第几个皇后；arr[index]的值value表示该皇后位于第value + 1列

程序如下：

public class Queue8 {

    static int maxQueue = 8;
    static int[] array = new int[maxQueue];
    static int solutionCount = 0;
    static int judgeCount = 0;


    public static void main(String[] args) {
        // 从第一个皇后开始摆放，即index = 0
        put(0);
        System.out.printf("一共有%d种解法\n", solutionCount);
        System.out.printf("一共判断冲突的次数为%d次\n", judgeCount);
    }

    public static void put(int index) {
        // 如果index等于maxQueue，则表示已经得到一个正确解
        if (index == maxQueue) {
            showSolution();
            return;
        }

        // 遍历一个皇后的每列，直到OK为止，则放下一个皇后
        for (int i = 0; i < maxQueue; i++) {
            // 先给该皇后的列进行赋值
            array[index] = i;
            // 判断该皇后的该列，是否和前面的皇后冲突
            if (judge(index)) {
                put(index + 1);
            }
        }
    }


    // 判断第index + 1个皇后的为止，是否和前面的皇后的为止冲突
    public static boolean judge(int index) {
        judgeCount++;
        for (int i = 0; i < index; i++) {
            // 因为每个皇后都在不同行，所有没有必要对行进行判断
            // 如果两个皇后的index对应的value一样，则表示位于同一列
            // 如果两个皇后的index相减的绝对值，和两个皇后的index对应的value相减的绝对值一样，则表示位于同一斜线
            if (array[i] == array[index] || Math.abs(index - i) == Math.abs(array[index] - array[i])) {
                return false;
            }
        }
        return true;
    }

    // 将一个正确解进行输出
    public static void showSolution() {
        solutionCount++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

}

运行程序，结果如下：

0 4 7 5 2 6 1 3 
0 5 7 2 6 3 1 4 
0 6 3 5 7 1 4 2 
0 6 4 7 1 3 5 2 
1 3 5 7 2 0 6 4 
......省略部分......
7 3 0 2 5 1 6 4 
一共有92种解法
一共判断冲突的次数为15720次