8皇后问题

Love The Way You Lie 2022-09-11 10:20 206阅读 0赞

[8皇后问题][8]的描述见百度百科，这里大概描述下，在如下这种 8 \* 8 的网格里面放入8个皇后，使得放入的这些皇后之间不能相互攻击，即任意两个皇后之间不能处于同一行，不能处于同一列，不能处于同一对角上

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_10_color_FFFFFF_t_70_g_se_x_16][]

如上图所示，在图中的位置放置一个皇后之后，阴影部分都不能再放置皇后了，非阴影位置可以继续放置皇后。题目就大概是这个意思。下面采用两种方法来进行解释

**【方法一】**利用位运算的特性来进行说明，位运算可以参考博文[初识位运算][Link 1]

从题目中我们知道，任意两个皇后之间是不能处于同一行和同一列的，那 8 \* 8 的网格里面想放置8个皇后，那**必定每一行有一个皇后，每一列有一个皇后**。那其实我们可以从**第一行**依次确定每一行可以放置皇后的位置，并且放置一个皇后，然后基于放置的皇后，再依次确定**第二行**，再基于设置好的第一行和第二行，确定第三行的值，依次类推。

现在的问题是：**已知 N - 1行放置皇后的信息，如何确定第N行可以放置皇后的位置**，然后从可以放置皇后的位置中选择一个位置放置皇后。所以现在把这个放置皇后的位置确定了，其实问题也差不多解决了。接下来我们来基于位运算来一步步分析问题。

现在假如第一行和第二行的皇后放置的位置如下

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16][]

如何确定第三行可以放置皇后的信息，第三行能放置皇后的信息显然受第一行和第二行已放置皇后的信息限制，第一行和第二行所放置皇后对应的列不能再放置皇后。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_15_color_FFFFFF_t_70_g_se_x_16][]  
**图1**

与第一行和第二行所在的左斜线的对角上不能放置皇后

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16 1][]  
 **图2**

与第一行和第二行所在的有斜线的对角上不能放置皇后

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_15_color_FFFFFF_t_70_g_se_x_16 1][]  
 **图3**

最终总结下来其实就是如下阴影部分不能放置皇后，也就是 列、左斜线 和 右斜线出现的位置。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16][]  
 **图4**

以column 来记录所有上方行已放置的皇后导致当前行格子不可用的集合，所在列如果放了皇后，则当前行格子对应的位置为 1，否则为 0，同理,以 pie（撇，左斜线） 记录所有已放置的皇后左斜方向导致当前行格子不可用的集合， na（捺，右斜线） 表示所有已放置的皇后右斜方向导致当前行不可用的集合。则对于第三行来说我们有：

column = 10100000 (如图1，第 1，3 列放了皇后，所以 1，3 位置为 1，其他位置为 0）
    pie = 01000000 (如图2，左斜线经过第三行的第二个方格，所以第二位为 1）
    na = 00110000 (如图3，右斜线经过第三行的第三, 四个方格，所以第三,四位为 1）

将这三个变量作或运算得到结果如下

10100000
    |   01000000
    |   00110000
    -----------------------
        11110000

结合 **图4**查看，所有为 1 的位置不就是因为第一行和第二行导致不能放置皇后的位置？那现在通用的习惯，用 1 表示可以放置皇后的位置，用 0 表示不能放置皇后，使用位运算符 **取反（~）**，就可以达到效果嘛

~11110000 = 00001111

但是要注意一点，比如在java中int用4个字节表示，也就是32位，所以取反时要当心

//用到的就后面8位
    00000000 00000000 00000000 11110000
    
    //取反，导致前面位（不相关的位，影响后续判断）也变为了1
    ~(00000000 00000000 00000000 11110000) = 11111111 11111111 11111111 00001111

那其实也挺简单的，使用位运算就可以

// 1<<8
    1<<8 = 00000000 00000000 00000001 00000000
    
    //(1<<8)-1
    (1<<8) - 1 = 00000000 00000000 00000000 11111111

经过上面的分析，第三行可以放置皇后的位置其实就是如下

int position = ~(column | pie | na ) & ((1<<8) -1))

位1的位就表示可以放置皇后，为0的位表示不可以放置皇后。

如果第三行没有可放置皇后的位置，则所有位都是0，自然得出的结果position也是0。

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

**现在有如下两个问题：**

1、如何快速的取出位的值为1的某一个位置  
2、根据当前position的值和当前行选择的值，确定下一行的position（即可以放置皇后的位置）

**取最后一个位为1的值（**以p表示**）：**

比如 position = 0001....10000，如何得出...0000010000，可以使用位运算的技巧，我们知道负数在计算机中是通过补码的形式表示的。

补码的求解（以 -6 为例，仅显示出后8位）：

6 的二进制表示：00000110
    6 的二进制表示求反（1 变 0，0 变 1）：11111001
    6 的二进制表示求反（1 变 0，0 变 1）再加1 得出的值就是-6的表示：11111010

那可以看下 x & (-x) 有什么结果？（以 -6 为例）

6 的二进制表示：00000110
        &
         -6 的二进制表示：11111010
    -------------------------------------
               6 & (-6)：00000010

看上面，得出的结果不就是6的最后一个 1 ？其实是可以证明的。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16][]

**根据当前position和当前行选择的值（p），确定下一行的position（即可以放皇后的位置）**

其实就是根据当前的三个变量 column ，pie 和 na 确定下一行的 column，pie 和 na。

（1）对column，比较好理解，就是 column | p就可以。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16 1][]

（2）对于pie。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16 2][]

由于第三行后导致第四行不能放的（图中的蓝色的框）

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16][]

所以pie = ((pie | p) <<1)

（3）同理，na = ((na | p) >> 1)

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

接下来看下代码

public class NQueue {
        //8皇后问题
        private int N = 8;
        private int count = 0;
    
        public NQueue() {
        }
    
        public NQueue(int queueCount) {
            this.N = queueCount;
        }
    
        /**
         * @param row    当前处理的行
         * @param column 对应分析中的 column
         * @param pie    对应分析中的 pie
         * @param na     对应分析中的na
         * @return
         */
        public int queue(int row, int column, int pie, int na) {
            queueInternal(row, column, pie, na);
            return count;
        }
    
        private void queueInternal(int row, int column, int pie, int na) {
            //如果已经找到最后一行了，则表示找到一种可行的放置方案
            if (row >= N) {
                count++;
                return;
            }
            // 取出当前行可放置皇后的格子
            int bits = (~(column | pie | na)) & ((1 << N) - 1);
    
            //如果有可以放置皇后的位置
            while (bits > 0) {
                //选择一个可以放置皇后的位置
                int p = bits & -bits;
    
                //根据传入的column pie na 和 p 确定下一行的 位置
                queueInternal(row + 1, column | p, (pie | p) << 1, (na | p) >> 1);
    
                //回溯时当前最右的格子已经选择过，所以设置为0，表示已经选择过
                bits = bits & (bits - 1);
            }
        }
    }

调用

public class NQueueTest {
        public static void main(String[] args) {
            NQueue nQueue = new NQueue();
            //起始时row = 0 ,column = 0, column = 0,pie = 0,na = 0
            int count = nQueue.queue(0, 0, 0, 0);
            System.out.println("可摆放的总数：" + count);
        }
    }

**【方法二】**使用回溯算法来解决，回溯算法参见博文 [回溯算法详解][Link 2]

其实思路和位运算是差不多的。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16 2][]

如上图所示，当对第 i 行放置皇后时，首先要确定第 i 行能够放置皇后的位置，第 i 行能够放置皇后的位置其实是与前面的 i - 1 行放置皇后的位置相关的，所以我们在处理的过程中需要知道前面的 i - 1 行放置皇后的位置，判断的方式其实也是比较简单的。需要判断如下三种情况。

（1）是否同一列

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16 1][]

以待判断的位置作为坐标轴的远点，判断是否同一列，其实就是判断是否存在前面的 i - 1 是否处在纵坐标点上。

（2）判断是否处在右斜线上

如果第 i 行 处于第 col\_i 列，则判断 第 j （0<=j<i）行，处在 第 col\_j 列可以看下图

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16][]

如上图如果 **(j - i) = (col\_j - col\_i)** 说明处在同一右斜线上。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16 1][]

如上图如果 **(j - i) ! = (col\_j - col\_i)** 说明不处在同一斜角上。

（3）判断是否处在同一左斜线上

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16 2][]

其实和右斜线是一样的

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

代码分析：

前面分析的时候也说过，确定第 i 行放置皇后的位置时，需要用到前面 i -1 行放置皇后的位置，所以我们得定义一个数组存放皇后的放置位置。

// N 表示皇后的数量，同时也是矩阵的长度，N * N的矩阵
    // 如果 selected[2] = 3，表示第二行的皇后放置在第三列
    // 因为数组是从 0 开始的，所以数组的初始值应该为 -1 ，表示还没有设置皇后
    int[] selected = new int[N];
    
    //初始化数租
    Arrays.fill(selected,-1);

代码的主要框架如下：

/**
         * @param row      为第i行设置皇后
         * @param selected 存放皇后的位置
         */
        private void queueInternal(int row, int[] selected) {
            //表示找到一种合理的放置位置
            if (row >= N) {
                count++;
                return;
            }
    
            //依次判断第 row 行，第 col 列是否可以放置皇后
            for (int col = 0; col < N; col++) {
                if (isValidPosition(row, col, selected) == false) {
                    continue;
                } else {
                    //放置皇后
                    selected[row] = col;
    
                    //继续判断下一行
                    queueInternal(row + 1, selected);
                }
            }
    
            //回溯，把当前行设置为没有选择皇后
            selected[row] = -1;
        }

其实回溯的代码比较简单，就是不停的往前走，直到满足某个条件，达到目标或者是达不到目标，则回溯。

从上面的核心可以看出，其实就是 **isValidPosition** 方法的逻辑，其实代码就是如下的框架，依次判断是否存于同一列，同一左斜线，同一右斜线上

private boolean isValidPosition(int row, int col, int[] selected) {
            //从 row -1 行开始
            for (int i = row - 1; i >= 0; i--) {
                //1、判断 i 行是否与 row 行处于同一列
    
                //2、判断 i 行是否与 row 行处于同一右斜线上
    
                //3、判断 i 行是否与 row 行处于同一左斜线上
            }
            return true;
        }

最终的代码如下：

package com.Ycb.queue;
    
    import java.util.Arrays;
    
    public class NQueue {
        private int N = 8;
        private int count = 0;
    
        public NQueue() {
        }
    
        public NQueue(int N) {
            if (N <= 0) throw new IllegalArgumentException("皇后的数量必须大于0：" + N);
            this.N = N;
        }
    
        public int queue(int row) {
            //定义一个数组存放第i行皇后存放的位置
            int[] selected = new int[N];
    
            //初始化为-1，表示已经放置了皇后
            Arrays.fill(selected, -1);
    
            queueInternal(row, selected);
            return count;
        }
    
        /**
         * @param row      为第i行设置皇后
         * @param selected 存放皇后的位置
         */
        private void queueInternal(int row, int[] selected) {
            //表示找到一种合理的放置位置
            if (row >= N) {
                count++;
                return;
            }
    
            //依次判断第 row 行，第 col 列是否可以放置皇后
            for (int col = 0; col < N; col++) {
                if (isValidPosition(row, col, selected) == false) {
                    continue;
                } else {
                    //放置皇后
                    selected[row] = col;
    
                    //继续判断下一行
                    queueInternal(row + 1, selected);
                }
            }
    
            //回溯，把当前行设置为没有选择皇后
            selected[row] = -1;
        }
    
        private boolean isValidPosition(int row, int col, int[] selected) {
            //从 row -1 行开始
            for (int i = row - 1; i >= 0; i--) {
                //1、判断 i 行是否与 row 行处于同一列
                if (selected[i] == col) return false;
    
                //2、判断 i 行是否与 row 行处于同一右斜线上
                //3、判断 i 行是否与 row 行处于同一左斜线上
                if (Math.abs(i - row) == Math.abs(col - selected[i])) return false;
            }
            return true;
        }
    }

其实如果要打印详细的皇后存放的位置也比较简单

巨人的肩膀：[你说你会位运算，那你用位运算来解下八皇后问题吧][Link 3]

[8]: https://baike.baidu.com/item/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98/11053477?fr=aladdin
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/76fc1dfd81eb434dafdf47b4273751b3.png
[Link 1]: https://blog.csdn.net/ycb1914845451/article/details/120163346
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/0a055c11bd5c43d59b91bb9ea1e59a82.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/fb8075ef21f54e51bed8919ce28dff97.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/9dade1b931be4c7c92832e44da510a9d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_15_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/4edaae08520a432a95171ee74d2e3b81.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/0c9af296b2d34c4b86532c9ab9bd652c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/92cdf860d90c430fbc06d34b0ea305dc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/1ed43f029b4848b4a1f5c4660e54063b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/67ed9f1c7de24efb8bb2f1343749d9ca.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/390ddb3e93374949b930e23390f519f3.png
[Link 2]: https://mp.weixin.qq.com/s/nMUHqvwzG2LmWA9jMIHwQQ
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_14_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/830711b43edf414fb641ebbe3fe8e7c3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/97fac4049f6f4db4b5cd3a24c4fef169.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/4be923f706324f4f980611c07f2b0d7a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/a35f09a15c9e40ce9fa09c5792da406e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_19_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/c30f6502f0df45449dfedad225eeb2da.png
[Link 3]: https://mp.weixin.qq.com/s/45mfS3ciiVt8nghUSjezFg