[数据结构与算法]数据结构-递归，迷宫回溯，八皇后(Java实现)

递归，迷宫回溯，八皇后

1.迷宫回溯

注意理解回溯,简单来说就是如果下一个位置走不通后,会返回到上一个地方在对其他情况进行判断,会循环所有的情况
递归可以理解为一个程序反复调用自己本身,像一个有终止条件的循环

package datastructure.recursion;

/*
    @CreateTime 2021/9/11 16:40
    @CreateBy cfk
    
    创建一个迷宫
*/

public class Maze {

    public static void main(String[] args) {

        //创建迷宫的大小
        int[][] maze = new int[8][7];
        
        //创建迷宫地图迷宫的墙壁 无法走 默认为1
        for (int i = 0; i < 7; i++) {
            maze[0][i] = 1;
            maze[7][i] = 1;
        }
        for (int i = 0; i < 8; i++) {
            maze[i][0] = 1;
            maze[i][6] = 1;
        }
        maze[3][1] = 1;
        maze[3][2] = 1;


        // //打印迷宫显示
        // for (int i = 0; i < 8; i++) {
        //     for (int j = 0; j < 7; j++) {
        //         System.out.print(maze[i][j]+" ");
        //     }
        //     System.out.println();
        // }

        getMazeWay(1,1,maze);


        //打印迷宫显示
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(maze[i][j]+" ");
            }
            System.out.println();
        }
    }




    //创建一个走迷宫方法
    //设置迷宫墙壁为1 走过的地方置为2 走过但是无法走通的路置为3
    //迷宫按照 下 右 上 左 的顺序进行走
    /**
     *
     * @param x 起点的x轴
     * @param y 起点的y轴
     * @param maze 传入的迷宫数组
     * @return 返回值判断是否找到了出路
     */
    public static boolean getMazeWay(int x, int y, int[][] maze){

        //如果迷宫还没被走通就开始以下操作
        if (maze[6][5] == 2){
            return true;
        }else {
            //如果当前点还没有走过 则标记当前点 假设这个点是可以通的
            if (maze[x][y] == 0) {
                maze[x][y] = 2;
                //依次向下 向右 向上 向左 行走
                if (getMazeWay(x+1,y,maze)){
                    return true;
                }else if (getMazeWay(x,y+1,maze)){
                    return true;
                }else if (getMazeWay(x-1,y,maze)){
                    return true;
                }else if (getMazeWay(x,y-1,maze)){
                    return true;
                }else {
                    //如果都走不通
                    maze[x][y] = 3;
                    return false;
                }
            }else {
                return false;
            }

        }



    }
}

2.八皇后算法

package datastructure.recursion;

/*
    @CreateTime 2021/9/11 20:29
    @CreateBy cfk
*/

public class EightQueen {
    //创建八个皇后
    static int max = 8;
    //创建存储的集合
    static int[] queens = new int[max];

    //统计一共有多少种方法
    static int count;

    //统计总共进行了多少次的判断
    static int checkCount;

    public static void main(String[] args) {
            check(0);

            System.out.printf("一共有%d种方法",count);

            System.out.printf("一共判断了%d次",checkCount);



    }

    /*
        主要理解这个思想

        八皇后算法(注意:八皇后互相不能在同一行,同一列,以及同一对角线上)
        算法逻辑:
        1. 开始把第一个皇后直接放在第一行的第一个
        2. 然后开始第二行皇后位置的遍历从第一个开始,如果不满足条件则进行右移直到满足条件
        3. 依次循环到最后,得到一组正确的解法
        4. 然后从后往后依次回溯
        5. 最后回到开头,然后依次对后面的元素进行遍历

        本题使用一个一位数组来存储皇后的位置 方便后面的判断
        如 :  [0,4,7,5,2,6,1,3]  代表着第(0+1)一位皇后在第(0+1)一个位置 以此类推
     */

    //创建一个方法放置第n个皇后
    public static void check(int n){
        //如果当前已经放了八个皇后 则直接退出循环
        if (n == max){
            showQueen();
            return;
        }

        //从第一个开始判断
        //因为每一个层的每一个位置都要进行这个循环遍历 所以形成了回溯
        for (int i = 0; i < max; i++) {
            //确定皇后的位置这里
            queens[n] = i;
            if (judge(n)){
                //如果判断当前的皇后与前面的冲突 就进行遍历 把皇后移动到下一位
                check(n+1);
            }


        }
    }


    //查看我们放置的第n个皇后是否与前面的冲突
    public static boolean judge(int n){
        checkCount++;

        for (int i = 0; i < n; i++) {
            //如果此皇后与其他皇后在同一列 或着 在同一对角线
            //Math.abs(n-i) == Math.abs(queens[n] - queens[i]) 用来判断它们的对角线是否相同
            //因为如果相同的话,它们对应的长和宽是相等的
            if (queens[n] == queens[i] || Math.abs(n-i) == Math.abs(queens[n] - queens[i])){
                return false;
            }
        }
        //如果没有找到冲突的返回true
        return true;
    }


    //编写一个方法显示皇后拜访的位置  遍历数组
    public static void showQueen(){
        count++;
        for (int queen : queens) {
            System.out.print(queen + "");
        }
        System.out.println();
    }



}