【数据结构与算法】基于回溯算法实现八皇后问题

悠悠 2023-09-30 23:26 92阅读 0赞

**八皇后问题**是一个经典的计算机科学问题，它的目标是将8个皇后放置在一个大小为8×8的棋盘上，使得每个皇后都不会攻击到其他的皇后。皇后可以攻击同一行、同一列和同一对角线上的棋子。

--------------------

#### 一、八皇后问题介绍 ####

八皇后问题最早由国际西洋棋大师马克斯·贝瑟尔在1848年提出，但当时他并不知道如何解决这个问题。后来，在1960年代，计算机科学家们开始研究八皇后问题，并提出了多种解决方法。

![6a2ad9de4c5346dfa5ba1447f24e2068.png][]

#### 二、八皇后问题算法思路分析 ####

解决八皇后问题的算法有很多，其中最常见的是回溯算法。

**回溯算法**通过尝试所有可能的解来找到正确的解，因此在处理八皇后问题时也可以使用回溯算法来求解。另外，还有其他的一些算法，如位运算和启发式搜索等方法，也可以用来解决八皇后问题。

八皇后问题是一个重要的算法问题，它具有较高的难度和复杂性，同时也有着广泛的应用。在现代的计算机科学领域中，八皇后问题被视为一项基础性的问题，对于提高程序员的算法能力和解决实际问题都有着重要的意义。

八皇后问题算法的核心思路是通过回溯法来找到所有可能的解，并判断是否符合题目要求。

**具体地步骤如下：**

1.  定义一个棋盘，用二维数组表示，其中0表示空白位置，1表示皇后的位置。
2.  从第一行开始尝试将皇后放置在每一列上，并判断是否和前面的皇后冲突（即同一行、同一列或同一对角线）。
3.  如果当前位置没有冲突，则将皇后放置在该位置，并递归处理下一行。
4.  如果当前位置有冲突，则尝试下一列。
5.  如果无法在当前行中找到合适的位置，则回溯到上一行并尝试其它列。
6.  当处理完所有行时，输出解决方案。

在这个过程中，**我们需要定义一些辅助函数来检查某个位置是否可以放置皇后、打印棋盘以及递归函数等。**具体实现方式会根据不同的算法思路而有所不同，但以上的基本思路是通用的。

#### 三、八皇后问题的回溯算法代码实现 ####

package com.biyu.demo;
    
    public class EightQueens {
    
        //有多少个皇后
        int max = 8;
        //定义数组array, 保存皇后放置位置的结果
        int[] array = new int[max];
        //多少种解法
        static int count = 0;
        //冲突次数
        static int judgeCount = 0;
    
        public static void main(String[] args) {
            EightQueens queue8= new EightQueens();
            queue8.check(0);
            System.out.printf("一共有%d解法", count);
            System.out.printf("一共判断冲突的次数%d次", judgeCount);
        }
    
        /**
         * 放置第n个皇后
         *
         * @param n
         */
        private void check(int n) {
            if (n == max) {
                printBoard();
                return;
            }
            //依次放入皇后，并判断是否冲突
            for (int i = 0; i < max; i++) {
                //先把当前这个皇后 n , 放到该行的第1列
                array[n] = i;
                //判断当放置第n个皇后到i列时，是否冲突
                if (judge(n)) { // 不冲突
                    //接着放n+1个皇后,即开始递归
                    check(n + 1); //
                }
                
            }
        }
    
        /**
         * 检测该皇后是否和前面已经摆放的皇后冲突
         *
         * @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  放置第 2列 1 n = 1 array[1] = 1
                // Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
                //3. 判断是否在同一行, 没有必要，n 每次都在递增
                if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                    return false;
                }
            }
            return true;
        }
    
        /**
         * 输出皇后摆放的位置
         */
        private void printBoard() {
            count++;
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println();
        }
    
    }

![8670ce4c98ec47e9831376ccad1d0778.png][]

*  **需要注意的是，八皇后问题的解不止一个，因此我们需要找到所有的解才能得到正确的结果。同时，在实现算法时应该尽量避免重复计算，以提高效率。**

[6a2ad9de4c5346dfa5ba1447f24e2068.png]: https://img-blog.csdnimg.cn/6a2ad9de4c5346dfa5ba1447f24e2068.png
[8670ce4c98ec47e9831376ccad1d0778.png]: https://img-blog.csdnimg.cn/8670ce4c98ec47e9831376ccad1d0778.png