n皇后问题-回溯法求解1 .算法在nn格国际象棋中排列n个皇后，使其不能相互攻击。 也就是说，让任何两个皇后都不能在同一行、同一列或同一条对角线上，并询问有多少种摆动方式。
n皇后是从八皇后问题发展起来的。 这个问题是国际象棋棋手内向的鸡翅在1848年在88格国际象棋上安排8个皇后，使其不能相互攻击，也就是说，任何两个皇后不能在同一行、同一列或同一条斜线上。 cxdhl认为有76种方案。 1854年柏林将棋杂志发表了40种不同的解，后来用图论的方法得出了92种结果。
2 .算法分析随着计算机的普及和发展，计算机可以很容易地计算出以前人们无法解决的问题。 而且，思路很清晰。 那就是暴力解决，遍历所有情况，计算解的数量。
2.1回溯法基于选择条件向前搜索以实现目标。 但是，在探索某一步时，如果发现原来的选择不优秀或者没有达到目标，就后退一步重新选择。 在这样不顺利的情况下，返回的技术就是回溯法
2.2回溯思路模拟棋盘排列，从第一行开始依次选择位置，当前位置满足条件时下移位置，不满足条件时下移当前位置一个。
最后一个不满意，追溯到前一行，选择下一个位置，继续探索。
其实不需要n*n的排列。 存储位置所需的只是n的长度数组。
显示方式： arr[i]=k； 显示：皇后位于第I行第k个位置。 因此arr[n]的阵列可以表示可行的解，并且可以通过回溯来获得所有的解。
2.3 n皇后上溯解开。 八皇后不能同行，同列、斜线一样。
通过在一行安置一位皇后，解决了不同行的问题。 在第I行中，遍历n列来寻找位置。 与以前所有行的位置进行比较。 比较列：当前列的col不等于前面所有列。 也就是说col！=arr[i] .比较斜线。 因为斜率为1或-1的斜线不再相同。 (row - i )/)/(col - arr[i]！=1或-1
能熟练使用绝对值函数：ABS(row-I )！=可以提取=ABS(col-arr[I] )比较方法。
publicbooleancomp(introw，int col )//当前行和列的for ) intI=0； i row； I//比较前为row -1列。 {if(col==arr[I]|ABS(row-I )！=ABS(col-arr[I] )//如果在同一列中，则为同一正斜杠返回假； }返回真； )编写比较函数后，只剩下回溯的过程。 递归追溯的话很容易理解。
//当前层rowfor(intI=0； i n； I ) if (comp (原始，原始) ) { arr [原始]=I； //同样地遍历下一层。 row 1 }} 2.4小时复杂度最差时：每行可有n种，有n行，因此时间复杂度为o(n ) n )。
但是，回溯法会事先判断一些情况并舍弃，所以时间的复杂性并不像想象的那么高。 但是，说O(N )！ )也不太正确，具体怎么计算，暂时也不太清楚。 (之前当然想了，这里有修改。 感谢您在评论中的注意。 ）
2.5空间复杂度只使用了arr[n]的排列，也就是o[n]。
3 .代码实现公共类n队列{ private int n； 私密长计数； 隐私int [ ] arr； //private int nn； Publicnqueen(intn ) { this.n=n； //nn=(1n )- 1； 计数=0； arr=new int[n]； }/* * * rowcoliarr [ I ] * @ param row * @ param col * @ return */publicbooleancheck (introw，int col ) ) for(intI=0； i row； I ) if(col==ARR[I]|math.ABS(row-I )==math.ABS ) col-ARR[I] ) /位于同一列中或位于同一斜线中。 一定不在同一行的返回假； }返回真； ) publicvoidfindnqueen(intk ) if ) k==n )//求一个解，count 1 count； 返回； }for(intI=0； i n； I () if (check ) k，I ) ) /检查是否满足条件
arr[k] = i; //记录 FindNQueen(k + 1); //递归查找 } } } public static void main(String args[]){ NQueen nQueen = new NQueen(13); nQueen.FindNQueen(0); System.out.println(nQueen.count); }} 4. 拓展，位运算+回溯法实现虽然计算机算的很快，但是上诉方法实在是太慢了， java就更慢了。如何网上就有大佬给出了位运算求解。精妙的不行。
4.1 算法思路我们不再用数组来存储位置，而是用一个整数k，k一开始等于0. 不是普通的0.我们也不比较了，直接用两个整数l和r 记录在斜线在当前行不能走的位置。如果是n皇后， 那么用一个整数
nn = 1 << n 表示结束。
举个栗子吧： 8皇后问题。
初始化 那么我们就变成二进制的角度来看这些初始化的数据吧。
k = 00000000, l = 00000000, r = 00000000; nn = 11111111; (<- 8个0 8个1)
k: 每个位置i的0表示没有皇后，1表示在第i个位置放了一个皇后。l: 0表示之前所有的列中放的皇后斜率为-1的线上没有涉及这个位置， 1 表示涉及到了，不能放皇后r: 同l， 所有斜率为1的线涉及的位置。l和r的实现：
比如k = 00110001. 我要在第4个为位置放一个皇后， 假设l和r都没有涉及这个位置。
那么这个位置x= 00001000.
k = (k & x) = 00111001.l = (l & x) << 1.r = (r & x) >> 1.假设l = 00110001， r = 00100010.下一行，l表示斜率为-1不能放的位置， 那么第i+1行 l 中所有为1的数字都需要向左移动一位，r需要向右移动一位。 l & x 也就是加上当前选中的位置一起移动。
4.2代码实现 //k 当前已走了多少个位置。 l 左斜线不能走的位置， r 右斜线不能走的位置。 public void FindNQueen(int k, int l, int r){ if(k == nn){ count++; return; } int z = nn & (~(k | l | r)); //能走的位置， 和nn取并可以去掉前面多余的1 while(z != 0){ int index = z & (~z+1); //最右边的一个1， 即要放皇后的位置。 z -= index; //去掉这个位置。 FindNQueen(k | index, (l|index)<<1, (r|index)>>1); //查找下一个。 } } 4.3 算法分析 时间复杂度，应该同上分析一致，去掉但是少了检查的for循环，应该是O(n!)空间复杂度，只用了几个变量， O(1). 5. 展望其实还有其他方式和更快的方式求解，比如位运算+多线程， 还有号称时间复杂度为O(1)，利用数学公式的构造法求解。扶我起来，我要继续学。