本文主要是介绍n皇后问题的最优解及优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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 == 32if (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的位置上尝试皇后的位置，在尝试之后将值修改为0while (pos != 0) {mostRightOne = pos & (~pos + 1);pos = pos - mostRightOne;//左右限制变化res += process(limit,colLim | mostRightOne,(leftDiaLim | mostRightOne) << 1,(rightDiaLim | mostRightOne) >> 1);}return res;}}
这篇关于n皇后问题的最优解及优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
