八皇后

ゝ一世哀愁。 2022-12-24 12:57 110阅读 0赞

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

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都

不能处于同一行、同一列或同一斜线上，问有多少种摆法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70][]

[游戏链接][Link 1]

八皇后问题思路分析

1、第一个皇后先放第一行第一列

2、第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适

3、继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解

4、当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.

5、然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤

首先，将第一个皇后放在第一行第一列

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 1][]

然后拿着第二个皇后去遍历第二行的每一列，判断是否合法（蓝色为不合法的位置）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 2][]

后面依次拿着第n个皇后在第n行的每一列进行遍历

（如图，遍历到第6行时，发现第六行的每一列都不能放置皇后，此时递归回溯，回到上一行，重新进行遍历）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 3][]

此时第六行的每一列仍然不能放置皇后

第五行也已经遍历完了，继续递归回溯

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 4][]

第四行重新摆放

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 5][]

依次类推，就得出了八皇后问题的第一种解法

1,5,7,6,3,7,2,4

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 6][]

得出第一个结果后，继续遍历第一行的第二列、第三列、第四列.........

每遍历到第八行，成功后，打印一次结果

代码实现：

代码实现之前，先对代码进行一下优化，以上过程很容易看出，理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr\[8\] = \{0 , 4, 7, 5, 2, 6, 1, 3\} //对

应arr 下标 表示第几行，即第几个皇后，arr\[i\] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列。

1、写一个遍历结果的方法

/**
         * 打印皇后的摆放位置
         * @param array
         */
        private void print(int[]array){
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println();
        }

2、写一个方法判断第n行的皇后是否合法

- 不能与n行之前的皇后在同一列

-不能与n行之前的皇后在同一斜线（考虑使用斜率）

/**
         * 判断第n行的皇后位置是否合法
         * @param n 表示第n个皇后
         * @return
         */
        private boolean judge(int n){
            judgeCount++;
            for (int i = 0; i < n; i++) {
                //array[i] == array[n]  不在同一列
                //Math.abs(array[n] - array[i]) == Math.abs(n - i)  不在同一斜线
                if (array[i] == array[n] || Math.abs(array[n] - array[i]) == Math.abs(n - i)){
                    return false;
                }
            }
            return true;
        }

3、写一个方法从第n行的第一列开始遍历的放置皇后

每成功放置一个皇后让n + 1，去放置下一行(递归)

/**
         * 放置第n个皇后
         * @param n
         */
        private void check(int n){
            if (n == 8){
                count++;
                print(array);
                return;
            }
            for (int i = 0; i < max; i++) {
                array[n] = i;
                if (judge(n)){ // 第n行的皇后是否合法
                    check(n + 1);
                }
            }
        }

4、创建主方法，调用方法

使用count统计一共有多少种方法

使用judgeCount统计一共进行了多少次比较

//定义一共有多少个皇后
        int max = 8;
        //使用一个数组保存皇后的放置位置
        int[] array = new int[max];
        static int count = 0;
        static int judgeCount = 0;
        public static void main(String[] args) {
            Queen8 queen8 = new Queen8();
            Long startTime = System.currentTimeMillis();
            queen8.check(0);
            System.out.println("一共有" + count + "解法");
            System.out.println("一共有" + judgeCount + "次冲突");
            Long endTime = System.currentTimeMillis();
            System.out.println(endTime - startTime + "ms");
        }

总结：

一共有92解法  
一共有15720次冲突

所有代码

public class Queen8 {
        //定义一共有多少个皇后
        int max = 8;
        //使用一个数组保存皇后的放置位置
        int[] array = new int[max];
        static int count = 0;
        static int judgeCount = 0;
        public static void main(String[] args) {
            Queen8 queen8 = new Queen8();
            Long startTime = System.currentTimeMillis();
            queen8.check(0);
            System.out.println("一共有" + count + "解法");
            System.out.println("一共有" + judgeCount + "次冲突");
            Long endTime = System.currentTimeMillis();
            System.out.println(endTime - startTime + "ms");
        }
    
        /**
         * 放置第n个皇后
         * @param n
         */
        private void check(int n){
            if (n == 8){
                count++;
                print(array);
                return;
            }
            for (int i = 0; i < max; i++) {
                array[n] = i;
                if (judge(n)){ // 第n行的皇后是否合法
                    check(n + 1);
                }
            }
        }
    
        /**
         * 判断第n行的皇后位置是否合法
         * @param n 表示第n个皇后
         * @return
         */
        private boolean judge(int n){
            judgeCount++;
            for (int i = 0; i < n; i++) {
                //array[i] == array[n]  不在同一列
                //Math.abs(array[n] - array[i]) == Math.abs(n - i)  不在同一斜线
                if (array[i] == array[n] || Math.abs(array[n] - array[i]) == Math.abs(n - i)){
                    return false;
                }
            }
            return true;
        }
        /**
         * 打印皇后的摆放位置
         * @param array
         */
        private void print(int[]array){
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println();
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70]: /images/20221120/9c1d9def8442457b96902b54b4d72c35.png
[Link 1]: http://www.4399.com/flash/42643_1.htm
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 1]: /images/20221120/c194eac194054b3d92a72b422fd42f5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201128142942802.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201128143344628.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201128143529464.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201128143821841.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201128144121145.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70