问题描述
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 == 乙
情况二: 共对角线的情况,即 (甲-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;
}