n皇后问题的最优解及优化

本文主要是介绍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皇后问题的最优解及优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---