使用位运算优化 N 皇后问题
作者：Grey
原文地址：
问题描述
题目链接：牛客-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 == 乙
情况二： 共对角线的情况，即 (甲-x) 的绝对值等于 (乙-y) 的绝对值相等，即 |甲 - x| == |乙 - y|。
由于我们每行只安排一个皇后，所以不需要判断两个点是否共行，在我们的算法模型下，这两个点天然不共行。
完整代码如下
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 位状态信息来表示，则为
以上信息用一个变量pos来表示，这个变量就用于记录哪个列位置中填了皇后，
还要设置另外三个变量
// 皇后的列限制是什么
int colLim;
// 皇后的左下对角线限制是什么
int leftDiaLim;
// 皇后的右下对角线限制是什么
int rightDiaLim;
比如，5 皇后问题，初始状态下，pos == 0 ，然后在第 4 个位置填了一个皇后，即 pos 二进制的第 4 个位置变为 1，那么其对应的三个变量的变化如下。
接下来定义一个变量
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;
}