n皇后问题的最优解
时间复杂度
package algorithm;
public class NQueen {
public static int num(int n){
if(n < 1){
return 0;
}
int[] record = new int[n];//n皇后的n*n的棋盘，record[i]表示第i行的皇后放在了第几列
return process(0,record,n);
}
/**
*返回n皇后的摆法
* i表示从第几行开始，n表示皇后数
*/
private static int process(int i, int[] record, int n) {
//如果当前的位置在i行，那么即表示i-1及之前的行的皇后一定是满足条件的，在摆第i行的皇后要满足条件不与之前的皇后共行、共列或共线
//如果行数来到n，说明已经来到最后，此时即为出现一种摆法
if(i == n){
return 1;
}
int res = 0;
//遍历列
for (int j = 0; j < n; j++) {
if(isValid(record,i,j)){//判断是否能摆
record[i] = j;//能摆久记录摆下的皇后的列
res += process(i+1,record,n);//递归，摆下一行，在下一行依旧遍历所有列
}
}
return res;
}
//判断是否共行、共列、共斜线
//由于record数组的索引存储的就是行数，因此不需要检查是否共行
private static boolean isValid(int[] record, int i, int j) {
for (int k = 0; k < i; k++) {
//检查是否共列、共斜线（纵坐标之差 == 横坐标之差）
if(j == record[k] || Math.abs(record[k] - j) == Math.abs(i-k)){
return false;
}
}
return true;
}
}
上述最优解在n的值较大的时候跑出来仍是很慢，但无法对此进行结构上的优化，即无法进行时间复杂度的优化，但是可以使用位运算进行常数时间上的优化
优化
条件：不超过32皇后问题，超过32皇后问题需要把int转化为long类型
举个栗子
八皇后问题，n = 8
1位置不能放皇后，0位置可以
| 第1行 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 列限制 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 左斜线限制 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 右斜线限制 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 三个限制求或 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | ||||||||
| 第2行 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 第2行+第1行限制 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
左斜线限制 = 列数 - 行差（左移）
右斜线限制 = 列数 + 行差（右移）
利用位运算的特性，限制哪些列可以放皇后，而不是每一列都遍历，节省时间
int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));第一个数表示前面的数，limit即前面都是0，后面8位都是1
| limit | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 列限制 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 左斜线限制 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 右斜线限制 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 三种限制或 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| ~取反 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| &并limit | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
为什么要有limit？
因为可以和limit求并截去左侧的所有的数，在最终求得的pos数中，1的位置可以放置皇后，0的位置不可以放置皇后
mostRightOne = pos & (~pos + 1);| pos | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| ~pos | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| ~pos+1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| pos&(~pos+1) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
package algorithm;
public class NQueenOptimize {
public static int num(int n) {
//不超过32皇后问题
if (n < 1 || n > 32) {
return 0;
}
//生成一个二进制位数，后n位都是1，前面都是0
//limit数本身的值不重要，只是用它的位信息
int limit = -1;//n == 32
if (n != 32) {
limit = (1 << n) - 1;
}
return process(limit, 0, 0, 0);
}
/**
* 1的位置不可以放皇后，0可以
* colLim: 列的限制
* leftDiaLim: 左斜线的限制
* rightDiaLim: 右斜线的限制
*/
private static int process(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
//列上的限制 == limit，说明全都放满了，此时即为一种摆法
if (colLim == limit) {
return 1;
}
/**
* pos表示所有候选皇后的位置，1的位置可以放皇后，0的位置不可以放皇后
* (colLim | leftDiaLim | rightDiaLim) 三种限制或
* ~ 表示取反，此时在棋盘上1表示可以放皇后，0表示不能放皇后
* & 和limit求与（0和1与为0，1和1与为1）
*/
int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
int res = 0;
int mostRightOne = 0;
//在每个1的位置上尝试皇后的位置，在尝试之后将值修改为0
while (pos != 0) {
mostRightOne = pos & (~pos + 1);
pos = pos - mostRightOne;
//左右限制变化
res += process(limit,
colLim | mostRightOne,
(leftDiaLim | mostRightOne) << 1,
(rightDiaLim | mostRightOne) >> 1);
}
return res;
}
}
