N 皇后问题是指在 N ∗ N N * N N∗N 的棋盘上要摆 N N N 个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。
给定一个整数 n，返回 n 皇后的摆法有多少种。
Leetcode 题源：N 皇后II
例：
n = 1
返回 1
n = 2 或 3
2 皇后和3皇后无论怎么摆都不行，返回0
n = 8
返回 92
只能用暴力。
规定皇后按行放，即每行只能放一个皇后，则免去了皇后是否共行的判断。
准备轨迹信息记录（一维数组record），每放置一个皇后，就在轨迹信息中记录，放置下一个皇后的时候，判断和轨迹信息中的位置是否冲突。
若之前的某个皇后在 (x,y) 位置，需要判断当前位置 (m,n) 能否放置皇后，就需要判断该位置是否和 (x,y) 冲突，即判断 y == n || |m - x| == |n - y|，当前位置需要和之前所有已经放置的皇后位置进行冲突判断，才能确定是否可以放皇后。
//时间复杂度 O(n^n)，每一行都要进行n次尝试
public class NQueens {
public static int num(int n) {
if (n < 1) return 0;
int[] record = new int[n];
return process(0, record, n);
}
//当前来到第i行，一共是0 ~ n - 1行
//在i行上放皇后，所有列都尝试
//必须保证和之前所有的皇后不冲突
//int[] record中保存之前的皇后存放的位置，之所以可以用一维，可以用下标表示行，数组中的数即表示所在的列
//record[x] = y 之前的第x行的皇后，放在了y列
//返回：不关心 i 以上发生了什么，i....后续有多少合法的方法数
public static int process(int i, int[] record, int n) {
if (i == n) { //所有皇后填完了，那么说明找到了1种有效方法
return 1;
}
int res = 0;
//i行的皇后，放哪列呢？逐列试
for (int j = 0; j < n; j++) {
if (isValid(record, i, j)) {
record[i] = j;
res += process(i + 1, record, n);
//record数组只关心前面的数据，所以当回溯回去的时候，当前的脏数据是用不到的
//record数组不需要恢复前一个状态，即不需要擦，数据脏了就脏了，不影响计算
}
}
return res;
}
public static boolean isValid(int[] record, int i, int j) {
for (int k = 0; k < i; k++) { //讨论与之前的0~i-1行放置的所有皇后是否冲突，从第0行的皇后开始讨论
//共列或者共斜线则冲突
if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
return false;
}
}
return true;
}
}
该方案的时间复杂度和暴力递归版本是一致的，只是优化了常数时间。
优化思路：用 int 状态位来替换 record 数组。
public class NQueens {
// 请不要超过32皇后问题
public static int num(int n) {
if (n < 1 || n > 32) {
return 0;
}
// 如果你是13皇后问题，limit 最右13个1，其他都是0
// limit 使用其位信息，而非其数值：
// 如果是4皇后，则00000000 00000000 00000000 00001111；
// 如果是k皇后，则从右往左数k位为1，其它位为0 , 实现方式： (1 << n) - 1
int limit = n == 32 ? -1 : (1 << n) - 1;
return process(limit, 0, 0, 0);
}
// 7皇后问题，则limit : 00000000 00000000 00000000 01111111 (固定不变)
// 之前皇后的列影响：colLim
// 之前皇后的左下对角线影响：leftDiaLim
// 之前皇后的右下对角线影响：rightDiaLim
// 所有参数都只用状态，不用原始数值
// 无需关心放置到第几个皇后了，只要某个时刻 "列限制 = limit" 就找到了一种方法
public static int process(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
if (colLim == limit) { //列限制 = limit,说明所有皇后都填满了，发现了一种方法
return 1;
}
//假设：
//列的限制:0001000 （1位置表示该位置不能放皇后)
//左下限制:0010000
//右下限制:0000100
//“列 | 左下 | 右下”或运算后的结果是总限制：0011100, 在总限制中，是1的位置不能放皇后，是0的位置可以放
//该结果取反是 1... 1100011 （之所以取反，是因为可以加工出所有可以放皇后的位置）
//取反结果与limit进行 与运算：0... 1100011, 该值就是pos的值
// pos中所有是1的位置，是你可以去尝试皇后的位置
int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
int mostRightOne = 0;
int res = 0;
while (pos != 0) { //尝试可能的1，将方法数累加返回
mostRightOne = pos & (~pos + 1); //提取出最右侧的1，即提取出一个可以放置皇后的位置。上面的例子，mostRightOne = 0000001
pos = pos - mostRightOne; //将该位置减掉，说明提取过了
res += process(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1,
(rightDiaLim | mostRightOne) >>> 1); //实参就是在调整列、左下和右下的限制
}
return res;
}
public static void main(String[] args) {
int n = 15;
long start = System.currentTimeMillis();
System.out.println(num2(n));
long end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
start = System.currentTimeMillis();
System.out.println(num1(n));
end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
}
}