8皇后问题-递归-回溯（Java）

忘是亡心i 2024-04-08 12:21 87阅读 0赞

#### 目录 ####

*   *   *  5.6 递归-八皇后问题（回溯算法）
         *   *  5.6.1 解题思路
             *  5.6.2 代码实现
     *  第一遍的是跟着老师做的，所以添加了我自己大量的注解。
     *   *  本次n皇后问题出自韩顺平的数据结构和算法

#### 5.6 递归-八皇后问题（回溯算法） ####

**八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际象棋棋手马克斯*贝瑟斯于1848年提出：在8*8格的国际象棋上摆放八个皇后，使其不能处于同一行、同一列或同一斜线，问有多少种摆法**

##### 5.6.1 解题思路 #####

1）第一个皇后放在第一行、第一列  
2）第二个皇后放在第二行第一列，然后判断是否可以这样摆放，如果不可以，就继续放在第二行第二列、第三列、依次把所有的列放完，找到一个合适的  
3）继续放第三个皇后，还是第一列、第二列。。。。直到第8个皇后也放  
在一个不冲突的位置，这时，视为找到一个正确解  
4）当得到一个正确解时，在栈回退到上一个栈，就会开始回溯，即将第一个皇后，放在第一列的所有正确解全部得到。  
5）然后回头继续放第一个皇后放在第二列，后面继续循环执行1、2、3、4的步骤

![在这里插入图片描述][620e88339b144c9cbb9913d7e53cc8f0.png]

##### 5.6.2 代码实现 #####

package com.ldm.recursion;
    
    /**
     * @author 梁东明
     * 2022/8/25
     * 86139
     * 8皇后递归
     * 人生小建议，看不懂的方法或者类记得CTRL + 点击 看看注解
     */
    public class Queue8 {
        
        //定义一个max表示有多少个皇后
        int max = 8;
        //定义数组array，保存皇后放置位置的结果，比如 arr = { 0 , 4, 7, 5, 2, 6, 1, 3}
        int[] arr = new int[max];
        static int count = 0;//这个变量是统计有多少种解法
        static int judgeCount; //这个变量是统计回溯了多少次的
        public static void main(String[] args) {
        
            //测试代码
            Queue8 queue8 = new Queue8();
            //这里的0，是从第一个皇后放起，不影响你有多少个皇后，因为一开始就定义了max = 8；
            queue8.check(0);
            System.out.println("一共有 = " + count+"解法");
            System.out.println("一共有判断冲突的 = " + judgeCount+" 次回溯次数");
        }
        /**
         * 编写一个方法，放置第n个皇后
         * 特别注意：check 是每一次递归时，就会进入check中都有 for（int i = 0; i < max ;i++),因此会有回溯
         * 回溯就是把上一层没走完的for循环走下去，不是把本次的for循环走完，很重要的知识点！！！！，家人们一定要记住
         * @param n 表示第几个皇后
         */
        private void check(int n){
        
            if (n == max){
          //如果n是第八个皇后，说明已经放完全部的皇后
                print();
                return;
            }
            /*
            //依次放入皇后，并判断是否冲突
            //for循环的快捷键就是fori，
            //可以直接写max.fori就可以迅速打印for循环啦！
            //无聊的小知识又增加了
            */
            for (int i = 0; i < max; i++) {
        
                //先把当前的皇后n，放到该行的第一列
                arr[n] = i;
    
                //判断当放置第n个皇后到i列时，是否冲突
                if (judge(n)){
         //不冲突
                    //接着放置n+1个皇后，即开始递归 很重要！！！！！！一定要看懂这行代码
                    check(n+1);
                }
                //如果冲突，就继续执行arr[n] = i;但是i在循环中，下一次循环i=i+1;即 将第n个皇后，放置在本行的后移一个位置
            }
        }
    
    
    
    
        /**
         *  查看当我们放置第n个皇后,就去检测该皇后是否和前面已经摆放的皇后冲突
         * @param n 表示第n个皇后
         * @return
         */
        private boolean judge(int n){
        
            judgeCount++;
            for (int i = 0; i < n; i++) {
        
                if (arr[i] ==arr[n] || Math.abs(n-i) == Math.abs(arr[n]-arr[i])){
        
                    /*
                    //如果两个皇后在同一列会相互攻击，同一斜线也会相互攻击，同一行也会相互攻击，所以要排除
                    ///Math.abs ctrl+点击进去看源码可以知道这是用来求绝对值的
                    //更详细的说法是： 行数的差值不能等于列数的差值，相等就说明在同一斜线上
                    //数学学过吧？ 把y=x在象限画出来就可以很清楚理解了 斜率为1，在同一条斜线上
                    //你可能会说，还有一个是否在同一行没有判断，如果皇后同一行也会相互攻击
                    //但是你有没有想过：n是递增的，它们是不可能在同一行的 ，所以不需要判断在同一行
                     */
                    return false;
                }
            }
            return true;
        }
        /**
         * 写一个方法，可以将皇后摆放的位置打印出来
         */
        private void print(){
        
            count++;
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }

### 第一遍的是跟着老师做的，所以添加了我自己大量的注解。 ###

**理解老师的解题思路之后，我觉得有必要花点时间自己重新写一份，锻炼自己写的代码能力和编程思维，惊奇的发现居然只花了三分钟就完整实现了8皇后问题的代码。**  
所以，我真心建议大家，如果真的看懂了代码，不妨自己找张纸写一下解题思路，再根据思路重新手打一份代码。可能会给你带来一份意想不到的惊喜。  
**代码量真的很少的，核心代码可能就几十行。如果不迎难而上，很难锻炼到自己的编程能力**

package com.ldm.recursion;
    
    /**
     * @author 梁东明
     * 2022/8/26
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     */
    public class MyQueen8 {
        
        int max1 = 8;
        int[] array = new int[max1];
        static int count = 0;
        static int backCount;
    
        public static void main(String[] args) {
        
            //测试我自己写的代码是否正确
            MyQueen8 myQueen8 = new MyQueen8();
            myQueen8.check1(0);
            System.out.println("解法 = " + count);
            System.out.println("回溯次数 = " + backCount);
        }
        /**
         * 插入n皇后
         */
        void check1(int n){
        
            if (n == max1){
        
                print();
                return;
            }
            for (int i = 0; i < max1; i++) {
        
                array[n] = i;
                if (judge1(n)){
        
                    check1(n+1);
                }
    
            }
        }
        /**
         * 判断插入的第n个皇后是否冲突
         */
        private boolean judge1(int n){
        
            backCount++;
            for (int i = 0; i < n; i++) {
        
                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 : array) {
        
                System.out.print(i+" ");
            }
            System.out.println();
    
        }
    }

#### 本次n皇后问题出自韩顺平的数据结构和算法 ####

[数据结构和算法教程][Link 1]，哔哩哔哩详细教程  
在 47-49p，视频共有三个，不到一个小时。二倍速半小时即可看完。

最后，认识一下，我是小白。努力成为一名合格的程序员。期待与你的下次相遇。

[620e88339b144c9cbb9913d7e53cc8f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1d706ef2f8c54640a18e35d590894749.png
[Link 1]: https://www.bilibili.com/video/BV1E4411H73v?p=47&vd_source=027fde985896626031abccc06ce8b031