/**
* N皇后问题
* <p>
* 在N*N的棋盘上摆放N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法
*/
public class NQueens {
public static void main(String[] args) {
int n = 12;
// 第一种方法
int num1 = num1(n);
System.out.println(num1);
// 第二种方法
int num2 = num2(n);
System.out.println(num2);
}
/**
* 第一种方法 暴力递归
*
* @param n 多少阶
* @return 多少种方式
*/
public static int num1(int n) {
if (n < 1) {
return 0;
}
// 已摆放记录，下标代表 行，值代表 列
int[] record = new int[n];
return process(n, record, 0);
}
/**
* N行一共多少摆法
*
* @param n 一共N行
* @param record 已放记录
* @param index 现在应该放第几行
* @return 多少种摆放方法
*/
private static int process(int n, int[] record, int index) {
if (index == n) {
return 1;
}
int res = 0;
for (int i = 0; i < n; i++) {
if (valid(record, i, index)) {
record[index] = i;
res += process(n, record, index + 1);
}
}
return res;
}
/**
* 是否可以摆放皇后
*
* @param record 已摆放记录
* @param i 当前准备摆放第几列
* @param index 当前准备摆放第几行
* @return 是否可摆放
*/
private static boolean valid(int[] record, int i, int index) {
for (int j = 0; j < index; j++) {
if (record[j] == i || Math.abs(index - j) == Math.abs(record[j] - i)) {
return false;
}
}
return true;
}
/**
* 第二种方法：位运算优化方式
*
* @param n 多少阶
* @return 多少种方式
*/
public static int num2(int n) {
if (n < 1 || n > 32) {
return 0;
}
int limit = n == 32 ? -1 : ((1 << n) - 1);
return process2(limit, 0, 0, 0);
}
/**
* N皇后问题一共多少种摆法
*
* @param limit 总限制多少阶
* @param colLimit 列限制
* @param leftDiaLimit 左对角线限制
* @param rightDiaLimit 右对角线限制
* @return 总方法数
*/
private static int process2(int limit, int colLimit, int leftDiaLimit, int rightDiaLimit) {
if (colLimit == limit) {
return 1;
}
int pos = limit & (~(colLimit | leftDiaLimit | rightDiaLimit));
int res = 0;
while (pos != 0) {
int mostRightOne = pos & (~pos + 1);
res += process2(limit,
colLimit | mostRightOne,
(leftDiaLimit | mostRightOne) << 1,
(rightDiaLimit | mostRightOne) >>> 1);
pos ^= mostRightOne;
}
return res;
}
}
/* 如有意见或建议，欢迎评论区留言；如发现代码有误，欢迎批评指正 */