递归应用

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

public class RecursionTest {
    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 =0; i<8 ;i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][3] = 1;
        map[4][1] = 1;
        map[4][3] = 1;
        map[5][1] = 1;
        map[5][2] = 1;
        map[5][3] = 1;
        getWay(map,1,1);
        for (int i=0;i<map.length;i++) {
            for (int j=0;j<map[0].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 使用递归回溯给小球找路
     * @param map 表示迷宫
     * @param i 表示小球的起始位置的横坐标
     * @param j 表示小球的起始位置的纵坐标
     * @return
     *
     * 1.当小球走到迷宫的右下角(本程序中为[6][5]时)，完成
     * 2.约定：当map[i][j]为0时表示还未走过，为1时表示障碍，不能通过，为2时已走过的通路，为3时表示该路为死路不能走
     * 3.小球的走路策略为：下 -> 右 -> 左 -> 上，如果该点走不通，再回朔
     */
    public static boolean getWay(int [][] map,int i, int j) {

        if (map[6][5] == 2) {  // 当走到右下角时，则表示小球已经走完
            return true;
        } else {
            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, j-1)) { //向左
                    return true;
                } else if (getWay(map, i-1, j)){ //向上
                    return true;
                } else {
                    map[i][j] = 3;
                    return false;
                }

            } else { // 当前点的值为1，2，3
                return false;
            }
        }

    }

}

2.递归 - 八皇后问题(回溯算法)

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

解题思路：

​ 1）第一个皇后先放到第一行第一列；

​ 2）第二个皇后放到第二行第一列，然后判断和之前的是否攻击，如果攻击继续放到第二列、第三列、直到找到合适的；

​ 3）继续第三个皇后，还是第一、第二、........直到第8个皇后也能放在一个不攻击的位置，算是找到一个正确解；

​ 4）但得到一个正确解时，在栈回退到上一个栈时，就会后开始回溯（从后向前），即将第一个皇后，放到第一列的所有正解，全部得到；

​ 5）然后回头继续第一个皇后放到第二列，后面继续执行1，2，3，4步骤；

说明： 理论上应该创建一个二位数组来表示棋盘，但实际上可以通过算法，用一个一维数组表示：array[8] = {0, 4, 7, 5, 2, 6, 1, 3};此一维数组下标表示第几行，即第几个皇后(从0开始), 所对应的值表示第几列；如[1] = 4;表示第2个皇后放到第二行第五列；

package com.sratct.recursion;

public class Recuresion8 {
    private static int max = 8;
    // 定义一个存放皇后位置的数组
    int []  array = new int[max];
    static int count = 0;
    public static void main(String[] args) {
        Recuresion8 recuresion8 = new Recuresion8();
        recuresion8.check(0);
        System.out.println(count);
    }

   // 放置第n个皇后
    public void check (int n) {
        if (n == max) { // 如果n == max == 8 则一个放法已经放完，直接输出
            print();
            return;
        } else {
            /**
             *   第n行，从0到max-1的位置试合适的位置
             *   若第{n,i}位置不冲突，则会继续下一行{n+1，i},
             *   若第{n,i}冲突，则会进行{n,i+1} ;
             *   .....直到找到合适的；
             */

            for (int i=0;i<max; i++) {
                array[n] = i; //把当前皇后放到n行的第i列
                if (judge(n)) { // 此位置不冲突；
                    check(n+1); // 继续下一行
                }
            }
        }
    }
    // 判断皇后是否冲突
    private boolean judge(int n) {
        // n与之前的皇后位置进行比较，是否冲突
       for (int i =0; i<n; i++) {
           /**
            * 若array[i] == array[n]，则在同一行
            * 若Math.abs(n-i) == Math.abs(array[n] - array[i]，在同一列，
            * 例：n = 1;第二个皇后放在第二列，则 array[1] = 1;
            * 则  Math.abs(1-0) == Math.abs(1-0);
            */
            if (array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i])) {
                return false;
            }
        }
       return true;
    }
    // 打印数组
    private void print() {
        count++;
        for (int i=0; i<array.length; i++) {

            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}