java使用递归实现走出迷宫和八皇后问题

java使用递归实现走出迷宫

废话不多说,直接上代码和运行结果

package com.csw.recursion;

/**
 * @Auther: 行路
 * @Date: Created on 2020/4/17 23:11 星期五
 * @Description: com.csw.recursion 迷宫回溯问题
 * @version: 1.0
 */
public class MiGong {
    public static void main(String[] args) {
        //先创建一个二维数组,模拟迷宫
        //地图
        int[][] map=new int[8][7];
        //使用1表示强
        //上下全部置为1
        for(int i=0;i<7;i++){
            map[0][i]=1;
            map[7][i]=1;
        }
        //左右全部置为1
        for(int i=0;i<8;i++){
            map[i][0]=1;
            map[i][6]=1;
        }
        //设置挡板
        map[3][1]=1;
        map[3][2]=1;
        //map[1][2]=1;
        map[2][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("");
        }
        //使用递归回溯来给小球找路
        //使用递归回溯
        setWay(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("");
        }
    }

    /**
     * 说明 map表示地图,i,j白澳式地图从那个位置开始触发(1,1)
     * 如果小球能到map[6][5] 位置,则说明通路找到
     * 约定:当map[i][j]=0 表示没走过,当为1表示强 2为通路可以走,3表示已经走过
     * 在走迷宫需要确定一个策略(方法)先走下->右->上->左,如果走不通就回溯
     * @param map 表示地图
     * @param i 从按个位置开始找
     * @param j
     * @return  如果找到通路,就返回true 否则返回false
     */
    public static boolean setWay(int[][] map,int i,int j){
        if(map[6][5]==2){
            //通路已经找到
            return true;
        }else{
            if(map[i][j]==0){ //如果当前这个点还没有走过
                //下->右->上->左 按照策略走
                map[i][j]=2; //假定该点是可以走通的.
                if(setWay(map,i+1,j)){
                    //向下走,
                    return true;
                }else if(setWay(map,i,j+1)){
                    //向右走
                    return true;
                }else if(setWay(map,i-1,j)){
                    //向上走
                    return true;
                }else if(setWay(map,i,j-1)) {
                    //向左走
                    return true;
                }else{
                    //说明该点是走不通的
                    map[i][j]=3;
                    return false;
                }

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

运行结果

• 0代表未走过的点
• 1代表迷宫的围墙
• 2代表走出迷宫的路线
• 3代表尝试走过,但走不通的点,进行回溯

java使用递归解决八皇后问题

废话不多说,直接上代码

package com.csw.recursion;

/**
 * @Auther: 行路
 * @Date: Created on 2020/4/18 13:31 星期六
 * @Description: com.csw.recursion 八皇后问题
 * @version: 1.0
 */
public class Queen8 {

    //定义一个max表示有多少皇后
    int max=8;
    //定义数组array 保存皇后放置的位置的结果
    //比如arr={0,4,7,5,2,6,1,3}
    int[] array=new int[max];
    static int count=0;
    static int judgeCount=0;
    public static void main(String[] args) {
        //测试8皇后是否正确
        Queen8 queen8=new Queen8();
        queen8.check(0);
        System.out.println("一共有"+count+"种解法");
        System.out.println("共判断了多少次"+judgeCount);

    }

    //编写一个方法,放置第n个皇后
    //特别注意：check是每一次递归,进入到check中都有for(int i=0;i<max;i++)因此会有回溯
    private void check(int n){
        if(n==max){ //n=8 ,其实8个皇后已然放好了
            print();
            return;
        }
        //依次放入皇后,并判断是否冲突
        for (int i=0;i<max;i++){
            //先把当前这个皇后n,放到该行的1列
            array[n]=i;
            //判断当放置第n个皇后到i列时,是否冲突
            if(judge(n)){
                //不冲突
                //接着放n+1个皇后,即开始递归
                check(n+1); //
            }
            //如果冲突,就继续执行array[n]=i;即将第n个皇后放置在本行的后移一个位置
        }
    }

    /**
     * 查看当我们放置第n个皇后,就去检测该皇后是否和前面已经摆放的皇后冲突
     * @param n 表示第n个皇后
     * @return
     */
    private boolean judge(int n){
        judgeCount++;
        for(int i=0;i<n;i++){
            //1.array[i]==array[n]表示判断第n个皇后是否和前面n-1个皇后在同一列
            //2.表示判断Math.abs(n-i)==Math.abs(array[n]-array[i])第n个皇后和第i个皇后是否在同一斜线
            //n=1 放在第二列 n=1 array[1]=1
            //Math.abs(1-0)==1 Math.abs(1)
            //判断是否在同一行,没有必要,n每次都在递增
            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("");
    }
}