Java递归实现迷宫问题和八皇后

左手的ㄟ右手 2024-04-07 10:29 66阅读 0赞

#### Java递归 ####

*  递归
 *   *  1.概念
     *  2.规则
 *  迷宫问题
 *   *  1.思路分析
     *  2.代码实现
     *  3.运行结果
 *  八皇后问题
 *   *  1.概念
     *  2.思路分析
     *  3.代码实现
     *  4.结果

## 递归 ##

### 1.概念 ###

简单来说：递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁

### 2.规则 ###

*  每当方法被调用，就会开辟一个独立空间
 *  方法的变量是独立的，不会相互影响的
 *  如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据
 *  递归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError
 *  当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

## 迷宫问题 ##

### 1.思路分析 ###

1、如果小球能到map\[6\]\[5\]那么就代表通关的路找到了  
2、规则：  
\- 当map\[i\]\[j\] = 0 表示这个点没走过  
\- 当map\[i\]\[j\] = 1 表示这个点不能走被挡住了  
\- 当map\[i\]\[j\] = 2 表示可以走  
\- 当map\[i\]\[j\] = 3 表示该位置已经走过，但是走不通  
3、走的时候需要一个策略，下->右->上->左

![在这里插入图片描述][53afc3e676914e64b4a0b1eb35b4e880.png]

### 2.代码实现 ###

package com.sky.recursion;
    
    /**
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/8/30
     */
    public class MiGong {
        
        public static void main(String[] args) {
        
            //初始化地图
            int row = 8;
            int column = 7;
            int[][] map = getMap(row, column);
    
            // 设置挡板
            map[3][1] = 1;
            map[3][2] = 1;
            map[1][2] = 1;
            map[2][2] = 1;
    
            System.out.println("===========开始跑图===========");
            getWay(map,1,1);
    
            for (int i = 0; i < map.length; i++) {
        
                for (int j = 0; j < map[i].length; j++) {
        
                    System.out.print(map[i][j]+" ");
                }
                System.out.println();
            }
    
    
        }
    
        /**
         * 初始化地图 , 二维数组中为 1 说明被挡住了
         * @param row   有多少行
         * @param column    有多少列
         * @return
         */
        public static int[][] getMap(Integer row,Integer column){
        
            int[][] map = new int[row][column];
            for (int i = 0; i< row; i++){
        
                map[i][0] = 1;
                map[i][6] = 1;
            }
            for (int i = 0; i < column; i++) {
        
                map[0][i] = 1;
                map[7][i] = 1;
            }
            for (int i = 0; i < map.length; i++) {
        
                for (int j = 0; j < map[i].length; j++) {
        
                    System.out.print(map[i][j]+" ");
                }
                System.out.println();
            }
            return map;
        }
    
        /**
         * 找到出迷宫的路
         * 说明：
         *  1、如果小球能到map[6][5]那么就代表通关的路找到了
         *  2、规则：当map[i][j] = 0 表示这个点没走过
         *          当map[i][j] = 1 表示这个点不能走被挡住了
         *          当map[i][j] = 2 表示可以走
         *          当map[i][j] = 3 表示该位置已经走过，但是走不通
         * 3、走的时候需要一个策略，下->右->上->左
         * @param map  地图
         * @param i 坐标起点
         * @param j 坐标起点
         * @return true代表找到了，false代表没找到
         */
        public static boolean getWay(int[][] map,int i, int j){
        
            // 到达终点
            if (map[6][5] == 2){
        
                return true;
            }else{
        
                // 当该点等于0时，说明这个点还没走过，我们可以假设他走的通
                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-1,j)){
        
                        return true;
                        // 向左走
                    }else if (getWay(map,i,j-1)){
        
                        return true;
                    }else{
        
                        // 上下左右都走不通
                        map[i][j] = 3;
                        return false;
                    }
                }else{
        
                    // 当判断到达这里时，说明该点是 1 或 2 或 3
                    return false;
                }
            }
        }
    }

### 3.运行结果 ###

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

## 八皇后问题 ##

### 1.概念 ###

> 八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。  
> 问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。

### 2.思路分析 ###

*  将第一个皇后放在第一行第一列
 *  将第二个皇后放在第二行第一列，判断是否会和其他皇后在同一行或同一列或在同一斜线，如若在，那么将其放在第二列、第三列依次。。。直到不相互攻击
 *  将第三个皇后放在第三行第一列，判断是否会和其他皇后相互攻击，如果相互攻击，将其放在第二列，第三列、第四列等等，以此类推，在摆放的过程中，有可能会改动前面所放皇后的为止（回溯）
 *  当得到一个正确的解时，就会回溯到上一行，由此来找出第一个皇后在第一行第一列的所有解
 *  再将抵押给皇后放在第一行第二列，并重复以上步骤
 *  注意：
    
     *  棋盘本身应该时二维数组组成，但因为皇后所在的行数时固定的，那么可以简化为一个一维数组，其中的值表示皇后所在的列
     *  数组下表代表皇后所在行数+1，所以判断是否时，只需要判断是否在同一列和同一斜线即可
        
         *  是否同列：值是否相同
         *  是否同一斜线： 行号 - 行号 是否等于 列号 - 列号 ，且**列号相减要取绝对值**

### 3.代码实现 ###

package com.sky.recursion;
    
    /**
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/8/30
     */
    public class Queue8 {
        
        /** 统计有多少种摆法 */
        static int num = 0;
    
        /** 一共八个皇后 */
        static int max = 8;
        /** 摆放位置 索引下标 + 1 代表 第几行   索引值代表  第几列 */
        static int[] arr = new int[max];
    
        public static void main(String[] args) {
        
            check(0);
            System.out.println("一共有"+num+"种");
        }
    
        /** 打印 */
        public static void print(){
        
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i]+"");
            }
            System.out.println();
            num ++;
        }
    
        /** 判断当前皇后是否会和之前按的皇后相互攻击 */
        public static boolean judge(int position){
        
            for (int i = 0; i < position; i++) {
        
                /**
                 * 如果两个皇后在同一列就冲突
                 * 同一斜线也冲突，索引下标代表行
                 * 行号 - 行号 == 列号 - 列号  那么就是在同一斜线上
                 */
                if (arr[i] == arr[position] || position-i == Math.abs(arr[position] - arr[i])){
        
                    return false;
                }
            }
            return true;
        }
    
        /** 检查皇后应放的位置 */
        public static void check(int queue){
        
            // 如果达到8那么就代表已经填满了
            if (queue == max){
        
                print();
                return;
            }
            // 把皇后放在每一列上，判断是否会和之前放置的起冲突
            for (int i = 0; i < max; i++) {
        
                // 每次都是从第queue行第一列开始
                arr[queue] = i;
                if (judge(queue)){
        
                    // 不冲突，放下一个皇后
                    check(queue+1);
                }
                // 如果冲突了，那么就会往后移一位，就相当于列+1，如果后面的行都冲突就会回溯
            }
        }
    }

### 4.结果 ###

一共92种

[53afc3e676914e64b4a0b1eb35b4e880.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/023bc64864b34578b39db750b43cbbeb.png