问题描述

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后,
要求:任何两个皇后不同行,不同列也不在同一条斜线上,
求给一个整数 n ,返回 n 皇后的摆法数。

题目链接:牛客-N皇后问题

常规解法

由于皇后不能共行,所以使用一个一维数组就可以表示整个过程

int[] records = new int[n];

其中 records[i] = j 表示:皇后安排在 i 行的 j 号位置。

在遍历过程中,可以首先给第 0 行安排一个皇后,然后到下一行安排一个皇后,一直安排到最后一行,如果可以顺利走到最后一行,则记录一种有效的摆法。

整体流程代码如下

    public static int num1(int n) {
        if (n < 1 || n == 2 || n == 3) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] records = new int[n];
        return process1(0, records, n);
    }

    public static int process1(int i, int[] records, int n) {
        if (i == n) {
            return 1;
        }
        int ways = 0;
        for (int j = 0; j < n; j++) {
            if (isValid(records, i, j)) {
                records[i] = j;
                ways += process1(i + 1, records, n);
            }
        }
        return ways;
    }

对于上述代码进行说明,首先,我们可以过滤掉一些基本的场景,比如

n < 1 || n == 2 || n == 3

这种情况下,怎么摆都不可能满足条件。

对于n == 1的情况,只能有一种摆法。

接下来就是int process1(int i, int[] records, int n)这个递归函数,这个递归函数的递归含义是:在棋盘中,0 ~ i - 1 行都已经安排好皇后了,要开始安排第 i 行的皇后了,安排完 i 行的皇后以后,继续安排到最后,可以得到的有效填充方案有多少?

base case 为

i == n

即:已经安排完最后一行(i == n - 1)的皇后了,说明之前的决策没问题,可以得到了有效的一种方案,返回 1。

接下来是普遍情况


        int ways = 0;
        for (int j = 0; j < n; j++) {
            if (isValid(records, i, j)) {
                records[i] = j;
                ways += process1(i + 1, records, n);
            }
        }

枚举第 i 行每个位置填皇后的情况,然后去下一行继续安排皇后,但是有个前提,给 i 行的第 j 号位置分配皇后的时候,需要首先校验下 i 行能否填 j 号皇后,即 isValid() 方法要解决的问题。

boolean isValid(int[] records, int i, int j);

这个方法表示: 0 ~ i - 1 行都安排好皇后的情况下,第 i 行的 j 号位置放皇后,是否合法。

这就涉及到一个简单的问题:已知二维矩阵中 [x,y][甲,乙] 两个点,如何判断其位置关系是否合法?

不合法的情况有两个,满足下述任何一种情况,两个点位置关系就不合法。

情况一:共列的情况,即 y == 乙

使用位运算优化 N 皇后问题-小白菜博客

情况二: 共对角线的情况,即 (甲-x) 的绝对值等于 (乙-y) 的绝对值相等,即 |甲 - x| == |乙 - y|

使用位运算优化 N 皇后问题-小白菜博客

由于我们每行只安排一个皇后,所以不需要判断两个点是否共行,在我们的算法模型下,这两个点天然不共行。

完整代码如下

public static boolean isValid(int[] records, int i, int j) {
    for (int s = 0; s < i; s++) {
        if (records[s] == j || Math.abs(records[s] - j) == Math.abs(i - s)) {
            return false;
        }
    }
    return true;
}

这个解法的时间时间复杂度是 O(N^N)

位运算优化解

以上是 N 皇后的常规解法,接下来是使用位运算来优化 N 皇后算法。

注:位运算只是减少了常数项的时间,整体时间复杂度还是 O(N^N),且位运算优化解目前支持处理 32 皇后问题。

可以通过以下例子熟悉一下位运算的用法,比如,打印一个 32 位整数的二进制形式(不用 Java 现成的 API),应该如何实现?

    // 打印一个32位整数的二进制形式
    public static void printBinary(int num) {
        for (int i = 31; i >= 0; i--) {
            System.out.print((num & (1 << i)) == 0 ? "0" : "1");
        }
        System.out.println();
    }

思路就是用这个整数的二进制的每一位和对应位置上的是 1 ,其余位置是 0 的数进行与(&)运算,如果与完以后结果是 0 ,则该位一定是 0 ,否则该位是 1。

再来一个示例,如何获取一个数二进制最右侧的 1?

比如:

7 这个变量,二进制为 00000000000000000000000000000111,最右侧的 1 就是 00000000000000000000000000000001,所以 7 最右侧的 1 的值是 1;

22 这个变量,二进制为 00000000000000000000000000010110,最右侧的 1 就是 00000000000000000000000000000010,所以 22 最右侧的 1 的值是 2。

结论是,一个数 num,其最右侧的 1 的值是 num & (~num + 1) 或者 num & (-num)

有了上述铺垫,

接下来是 N 皇后问题的优化点,在常规方法中,使用 records[] 数组来记录皇后的位置信息,如果用位运算优化解,可以使用一个 32 位整型变量的二进制状态信息来存储皇后的位置信息,

比如,常规解法中 records[x] == 5,表示某一行的 5 号位置有一个皇后,如果用 32 位状态信息来表示,则为

使用位运算优化 N 皇后问题-小白菜博客

以上信息用一个变量pos来表示,这个变量就用于记录哪个列位置中填了皇后,

还要设置另外三个变量

// 皇后的列限制是什么
int colLim;
// 皇后的左下对角线限制是什么
int leftDiaLim;
// 皇后的右下对角线限制是什么
int rightDiaLim;

比如,5 皇后问题,初始状态下,pos == 0 ,然后在第 4 个位置填了一个皇后,即 pos 二进制的第 4 个位置变为 1,那么其对应的三个变量的变化如下。

使用位运算优化 N 皇后问题-小白菜博客

接下来定义一个变量

int limit = n == 32 ? -1 : (1 << n) - 1;

由于用的是 32 位整型变量,所以最大支持 32 皇后问题,

如果是小于 32 的皇后问题,比如 13 皇后问题,那么 limit 会使用其二进制的最右侧的 13 个位置,会将最右侧的 13 个位置设置为 1,即 1 << n - 1

如果正好是 32 皇后问题,则为 -1,即二进制的 32 个位置都是 1。

有了colLim,leftDiaLim,rightDiaLim,limit这四个变量,就可以决策出下一个可以摆放皇后的位置,

int pos = limit & (~(colLim | leftDiaLim | rightDiaLim)) 得到的结果中,pos的二进制状态上是 1 的,就是可以放皇后的位置。

如果colLim == limit,说明每一列都安排好了皇后,直接返回一种有效解法。

得到 pos 变量后,从右往左依次枚举其二进制上为 1 的位置,在该位置放上皇后,把该位置列限制(即:colLim变量),左对角线限制(即:leftDiaLim变量),右对角线限制(即:rightDiaLim变量)进行对应的调整,然后跑后续的递归过程收集所有的有效布局次数。

完整代码如下

    //  请不要超过32皇后问题
    public static int num2(int n) {
        if (n < 1 || n > 32) {
            return 0;
        }
        // 如果你是13皇后问题,limit 最右13个1,其他都是0
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process2(limit, 0, 0, 0);
    }

    // 7皇后问题
    // limit : 0....0 1 1 1 1 1 1 1
    // 之前皇后的列影响:colLim
    // 之前皇后的左下对角线影响:leftDiaLim
    // 之前皇后的右下对角线影响:rightDiaLim
    public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == limit) {
            return 1;
        }
        // pos中所有是1的位置,是你可以去尝试皇后的位置
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        int mostRightOne;
        int res = 0;
        while (pos != 0) {
            // 得到 pos 最右侧的 1
            mostRightOne = pos & (~pos + 1);
            // 在该位置放上皇后,即:把该位置设置为 0
            pos = pos - mostRightOne;
            res += process2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }

更多

算法和数据结构笔记

参考资料

算法和数据结构体系班-左程云