==重点在于位运算版本的递归解法上面==
题目描述：
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。这里的不能相互攻击是两个 n 皇后之间不可处于同一行同一列，同一对角线。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1
**输入：**n = 4
**输出：**2
**解释：**如上图所示，4 皇后问题存在两个不同的解法。
**示例 2：**
**输入：**n = 1
**输出：**1
**提示：**
- `1 <= n <= 9`
思路：
1、普通递归版本：
- 利用一个路径数组记录前面行占的是那一列
- 判断是否处于同一对角线的方法：行之差的绝对值== 列之差的绝对值-->在同一对角线上
- 从第 0 行开始，对其中的每一列有多少中可能的的加和值
2、位运算的递归版本
测试链接：https://leetcode.cn/problems/n-queens-ii/description/
代码
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName NQueens
* @description: TODO N皇后问题
* @author: zs宝
* @create: 2025-03-26 09:19
* @Version 1.0
**/
package main.java.class040;
public class NQueens {
//第一种解法，普通递归的方式
public int totalNQueens(int n) {
if(n<1){
return 0;
}
return findN1(0,new int[n],n);
}
/**
i:表示第i行
path：表示路径数组
n:表示几皇后
返回从i行开始的N皇后摆法
*/
public int findN1(int i,int[] path,int n){
//若前n-1行已经填完，则说明每行都找到了一个对应位置，n皇后问题找到一种方案
if(i==n){
return 1;
}
//从当前行开始还有几种摆法
//假设前面的行已经固定
int ans=0;
for(int k=0;k<n;k++){
if(check(i,k,path)){
path[i]=k;
ans+=findN1(i+1,path,n);
}
}
return ans;
}
/**
检查在第i行的j列能否摆放
要求：摆放位置不能同行，同列，同对角线 */
public boolean check(int i,int j,int[] path){
//由于每次递归都是直接调用的下一行，因此同行不需要在此考虑
for(int k=0;k<i;k++){
//这里有一个判断是否在对角线上的方式：若在同一对角线上则 行位置的差值的绝对值==列值上的差值的绝对值
if(j==path[k] || Math.abs(k-i)==Math.abs(j-path[k])){
return false;
}
}
return true;
}
//解法二：基于位运算的优化解法
public int totalNQueens2(int n) {
if(n<1){
return 0;
}
//这个表示当前是n皇后问题，则最后的结果应该为
//假设为5皇后：0....011111
int limit=(1<<n)-1;
//每个列的当前占位
int colum=0;
//对角线：左上到右下
int right=0;
//对角线：右上到左下
int left=0;
return findN2(limit,colum,right,left);
}
/**
limit:这个表示当前是n皇后问题，则最后的结果应该为,假设为5皇后：0....011111
colum:每个列的当前占位
right:对角线：左上到右下
left:对角线：右上到左下
*/
public int findN2(int limit,int colum,int right,int left){
if(limit==colum){
return 1;
}
//现在对于colum,left,right的有1的位置上，在本行中都不能占位
//这个结果表示：某个位上若位1：则不可占，为0可占
int ban=colum | left |right;
//取反：让1为可占，0不可占，同时将第n位以后的数字全部变为0(n皇后)
int candidate=limit &(~ban);
//在当前行去尝试每个可以尝试的列位置
int place=0;
int ans=0;
while(candidate!=0){
//利用Brian Kernighan算法去取出最右侧的1
place=candidate &(-candidate);
//更新column，left，right所记录的位置信息
//不要忘记left和right在下一行中的对角位置
//只能在下一次递归函数中更新，不要再这个循环内更新，影响下一轮循环的位置
ans+=findN2(limit,colum | place,(right | place)<<1,(left | place)>>1);
//尝试完一个位置，candidate从中去除掉这个位置，防止重复尝试
candidate^=place;
}
return ans;
}
}