企业简介宣传片视频_网站内容有哪些_网上宣传方法有哪些_中国 日本 韩国

---

基于回溯法解决八皇后问题+以位运算方法优化n皇后问题

---

1. 八皇后问题问题描述

问题描述：八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

要求：求解并输出八皇后问题的全部92个解。

2.回溯法求八皇后（n皇后）问题

（有多少种摆放方式）+（每种方式的具体摆法）


保证所有皇后互相不可互相攻击

①由四皇后问题引入

先使问题简化，让n=4，以四皇后问题进行引入。

对于四皇后，有这两种摆放形式。

②皇后的占位问题

如果在棋盘上放置一个皇后，它实际上占据了哪些位置呢？

上，下，左，右，左上，左下，右上，右下。八个方向的位置会被占据，此时，橙色区域就不能再放置其他的皇后了。

③皇后的放置过程

放置第一个皇后，用橙色标记它的攻击位置
在第二行白色格子处，放置第二个皇后 ，用蓝色标记攻击位置

在第三行白色格子处，放第三个皇后，用绿色标记攻击位置
在第四行白色格子处，放第四个皇后，用紫色标记攻击位置

④放置过程中的问题

如果在放置过程中，发现皇后没有空白位置放置了，这是就说明之前某个皇后的摆放方式有问题，我们需要回到之前的某一时刻，重新选择该皇后放置方法，从而使后面的皇后可以正常摆放。
这里的：回到之前的某一时刻重新放置，就是回溯。

⑤回溯算法核心

回溯算法核心，就是发现哪一步出现了问题，就回到之前的时刻，重新尝试。

⑥回溯算法的求解过程

（以四皇后为例）
在过程中，需要定义两个二维数组。
attack[][]：用于标记皇后的攻击位置，攻击位置标为1，其余为0。
queen[][]：用于保存放置结果，标记皇后所在的位置，放置皇后位置为Q，其余为.。

问题的核心在于，递归的放置皇后，从一个空白的棋盘开始，每一行都要放置一个皇后，然后递归到下一行。
完成皇后的放置后，需要更新attack和queen数组。然后再进行下一行的皇后设置。
如果当前行没有任何一列可以放置皇后=》需要回溯。

以上图片及解释的参考视频：
回溯法求八皇后问题

⑦验证算法和代码实现

LeetCode51.N皇后

N皇后

可直接提交的代码，附注释及错误改正（c++实现）

class Solution {
public:vector<vector<string>> solveNQueens(int n) {// 传入参数n，表示n皇后问题// 函数返回一个二维的vector// 内部的vector是string类型// 保存n皇后的全部解法vector<string> queen; // 保存皇后位置vector<vector<int>> attack;// 保存皇后攻击位置vector<vector<string>> solve;// 保存最终结果// 初始化attack和queen数组for(int i=0;i<n;i++){attack.push_back((std::vector<int>()));// 1、向量（Vector）。// 2、它是一个动态数组，可以根据需要自动调整大小。// 3、向量提供了一些方便的方法来管理元素，比如添加、删除和访问元素。// 4、向量提供了一些内置功能，比如 push_back()（在末尾添加元素）、pop_back()（删除末尾元素）、size()（获取元素数量）等。// 5、std::vector<int> numbers;  创建一个空的整数向量。// 6、numbers.push_back(10); 在向量末尾添加元素10// 初始状态：// 刚创建时，numbers 是一个空的向量，不包含任何元素。// 它的初始大小为 0，但它可以动态增长。// 你可以使用 push_back() 方法向向量末尾添加元素：// numbers.push_back(10); // 向向量末尾添加元素 10// numbers.push_back(20); // 向向量末尾添加元素 20// 对于每一行，创建一个新的空列向量，并将其添加到 attack 向量中。// 这样，attack 成为一个 n x n 的二维向量，初始时所有元素都是空的。for(int j=0;j<n;j++){attack[i].push_back(0);}queen.push_back("");// queen.push_back("")：为 queen 向量添加一个新的空字符串，表示当前行的状态。// queen[i].append(n,".");queen[i] = std::string(n, '.'); // 使用 std::string 构造函数初始化// 主函数 solveNQueens 中 queen 数组初始化错误：// 在初始化 queen 数组时，你使用了 queen[i].push_back('.');，// 这会将每个 queen[i] 初始化为 "."，而不是 n 个 "."。// 就是会变成".""."".""."而不是"...."这样的。// 这会导致后续操作中 queen[k][i] 访问越界。// 修正方法：使用 queen[i].append(n, '.'); 来初始化每个 queen[i] 为 n 个 "."// queen[i].push_back('.'); // 添加一个字符// 将当前行的字符串扩展为 n 个 '.' 字符。'.' 通常表示该位置尚未放置皇后。}backtrack(0,n,queen,attack,solve);return solve;}//在(x,y)位置放置皇后，并更新攻击位置attack数组 void put_queen(int x,int y,vector<vector<int>> &attack){// 定义常量方向数组，用于对8个方向的更新static const int dx[]={-1,1,0,0,-1,-1,1,1};static const int dy[]={0,0,-1,1,-1,1,-1,1};attack[x][y]=1;        // 将皇后位置标为1// 通过两层循环，对该皇后可能攻击到的位置，进行标记// 外层for循环，表示从皇后位置向外延伸 // “从皇后位置向外延伸” 指的是从皇后所在的 (x, y) 位置出发，沿着八个方向逐步向外扩展，标记所有可能被攻击的位置。// 外层循环 for(int i = 1; i < attack.size(); i++) 控制延伸的步数，内层循环 for(int j = 0; j < 8; j++) 遍历八个方向。// 这种方法确保了皇后在所有方向上的攻击路径都被正确标记。// 外层循环 (for(int i = 1; i < attack.size(); i++)):// i 表示从皇后位置向外延伸的步数。// 当 i = 1 时，表示从皇后位置向外延伸1步，标记距离皇后1步的位置。// 当 i = 2 时，表示从皇后位置向外延伸2步，标记距离皇后2步的位置。// 依此类推，直到 i 达到棋盘的大小 attack.size()。for(int i=1;i<attack.size();i++){// 因为attack是动态数组，所有以这种形式获得，长度。// 对于八皇后问题，attack.size()就是8。// 内层便利8个方向，生成新的位置for(int j=0;j<8;j++){int nx=x+i*dx[j];int ny=y+i*dy[j];// 如果新位置在棋盘范围内if(nx>=0&&nx<attack.size()&&ny>=0&&ny<attack.size()){attack[nx][ny]=1;// 将他标记为1}}}}// 回溯法求解n皇后的递归函数// k表示当前正处理的行// n表示皇后数量// queen存储皇后的位置// attack标记皇后的攻击位置// solve存储n皇后的全部解法void backtrack(int k,int n,vector<string> &queen,vector<vector<int>> &attack,vector<vector<string>> &solve){// 在 backtrack 函数中，你传递了 attack 数组的副本给 put_queen，但 put_queen 函数是按值传递的，// 这意味着对 attack 的修改不会影响递归调用外部的 attack 数组。// 修正方法：将 put_queen 函数的参数改为引用传递，以便修改能够影响到外部的 attack 数组。if(k==n){// 找到了一组解solve.push_back(queen);// 将结果queen存储至solvereturn;}for(int i=0;i<n;i++){// 遍历每一列==>遍历第k行的第0列到n-1列// 回溯法试探皇后的可放置的位置if(attack[k][i]==0){// =0表示可以放置皇后vector<vector<int>> temp=attack;// 备份attack数组queen[k][i]='Q';put_queen(k,i,attack);// 更新attack数组backtrack(k+1,n,queen,attack,solve);// 继续探索k+1行皇后放置// 当递归完成后，将attack和queen数组恢复为递归前的状态attack=temp;queen[k][i]='.';}// 继续下一列的尝试}// for循环结束，就完成了k行所有可能的尝试。}}; 

可在编译器里运行 并出图案的 代码版本（c++实现）

#include <iostream>
#include <vector>
#include <string>
using namespace std; // 在(x,y)位置放置皇后，并更新攻击位置attack数组 
void put_queen(int x, int y, vector<vector<int>> &attack){// 定义常量方向数组，用于对8个方向的更新static const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};static const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};attack[x][y] = 1;        // 将皇后位置标为1// 通过两层循环，对该皇后可能攻击到的位置，进行标记for(int i = 1; i < attack.size(); i++){for(int j = 0; j < 8; j++){int nx = x + i * dx[j];int ny = y + i * dy[j];// 如果新位置在棋盘范围内if(nx >= 0 && nx < attack.size() && ny >= 0 && ny < attack.size()){attack[nx][ny] = 1;// 将他标记为1}}}
}// 回溯法求解n皇后的递归函数
// k表示当前正处理的行
// n表示皇后数量
// queen存储皇后的位置
// attack标记皇后的攻击位置
// solve存储n皇后的全部解法
void backtrack(int k, int n, vector<string> &queen, vector<vector<int>> &attack, vector<vector<string>> &solve){if(k == n){// 找到了一组解solve.push_back(queen);// 将结果queen存储至solvereturn;}for(int i = 0; i < n; i++){// 遍历每一列==>遍历第k行的第0列到n-1列// 回溯法试探皇后的可放置的位置if(attack[k][i] == 0){// =0表示可以放置皇后vector<vector<int>> temp = attack;// 备份attack数组queen[k][i] = 'Q';put_queen(k, i, attack);// 更新attack数组backtrack(k + 1, n, queen, attack, solve);// 继续探索k+1行皇后放置// 当递归完成后，将attack和queen数组恢复为递归前的状态attack = temp;queen[k][i] = '.';}// 继续下一列的尝试}// for循环结束，就完成了k行所有可能的尝试。
}// 主函数
int main(){int n;cout << "请输入皇后的数量 n: ";cin >> n;// 传入参数n，表示n皇后问题// 函数返回一个二维的vector// 内部的vector是string类型// 保存n皇后的全部解法vector<string> queen; // 保存皇后位置vector<vector<int>> attack;// 保存皇后攻击位置vector<vector<string>> solve;// 保存最终结果// 初始化attack和queen数组for(int i = 0; i < n; i++){attack.push_back(vector<int>()); // 使用 vector<int>() 初始化for(int j = 0; j < n; j++){attack[i].push_back(0); // 初始化所有位置为0}queen.push_back(string(n, '.')); // 初始化为n个'.' }backtrack(0, n, queen, attack, solve);// 输出结果if(solve.size() == 0){cout << "没有方案。" << endl;}else{for(int i = 0; i < solve.size(); i++){cout << "第 " << i + 1 << " 个解：" << endl;for(int j = 0; j < solve[i].size(); j++){cout << solve[i][j] << endl;}cout << endl;}cout << "总共有 " << solve.size() << " 个解。" << endl;}return 0;
}

LeetCode52.N皇后II

n皇后II

可直接提交的代码，附注释（java实现）（与上面的方法不同）

（用数组表示路径实现的N皇后问题）

class Solution {// 用数组表示路径实现的N皇后问题public static int totalNQueens(int n) {if (n < 1) {return 0;}return f1(0, new int[n], n);}// i : 当前来到的行（当前的行）// path : 0...i-1行的皇后，都摆在了哪些列（之前的行）// n : 是几皇后问题// 返回 : 0...i-1行已经摆完了，i....n-1行可以去尝试的情况下还能找到几种有效的方法public static int f1(int i, int[] path, int n) {if (i == n) {// 如果能到最后一行这个终止位置，// 就找到了一种有效方法。return 1;}int ans = 0;// ans有多少种有效的方法//      0 1 2 3 .. n-1（列数）// i    j             （i表示来到第i行）（j从0到n-1列依次试）for (int j = 0; j < n; j++) {if (check(path, i, j)) {path[i] = j;ans += f1(i + 1, path, n);}}return ans;}// 当前在i行、j列的位置，摆了一个皇后// 0...i-1行的皇后状况，path[0...i-1]====》// path : 0...i-1行的皇后，都摆在了哪些列（之前的行）// 返回会不会冲突，不会冲突，有效！true// 会冲突，无效，返回falsepublic static boolean check(int[] path, int i, int j) {// 当前 i// 当列 jfor (int k = 0; k < i; k++) {// 0...i-1// 之前行 : k// 之前列 : path[k]if (j == path[k] || Math.abs(i - k) == Math.abs(j - path[k])) {// 当前的列不能和之前的列一样// Math.abs(i - k) == Math.abs(j - path[k])这句话可以表示在对角线方向// 之前的行-当前的行 的绝对值=之前的列-当前的列 的绝对值// 则两个数在对角线方向。return false;}}return true;}}

以上代码参考视频如下

参考视频

可在编译器里面运行 出图案的 代码（java实现）

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {// 存储所有解法public static List<int[]> allSolutions = new ArrayList<>();// 用数组表示路径实现的N皇后问题，不推荐public static int totalNQueens(int n) {if (n < 1) {return 0;}backtrack(0, new int[n], n);return allSolutions.size();}// 回溯法求解N皇后问题public static void backtrack(int i, int[] path, int n) {if (i == n) {// 找到一种有效解，将其添加到allSolutions中allSolutions.add(path.clone());return;}for (int j = 0; j < n; j++) {if (check(path, i, j)) {path[i] = j;backtrack(i + 1, path, n);}}}// 检查当前放置是否有效public static boolean check(int[] path, int i, int j) {for (int k = 0; k < i; k++) {if (j == path[k] || Math.abs(i - k) == Math.abs(j - path[k])) {return false;}}return true;}// 辅助方法：根据path数组生成棋盘的图形表示public static void printBoard(int[] path) {int n = path.length;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (path[i] == j) {System.out.print("Q ");} else {System.out.print(". ");}}System.out.println();}System.out.println();}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.print("请输入皇后的数量n: ");int n = scanner.nextInt();int total = totalNQueens(n);if (total == 0) {System.out.println("没有找到有效的解法。");} else {for (int i = 0; i < allSolutions.size(); i++) {System.out.println("解法 " + (i + 1) + ":");printBoard(allSolutions.get(i));}System.out.println("总共有 " + total + " 种解法。");}scanner.close();}
}

输出结果如图所示

可在编译器里面运行 出图案的 代码（c++实现）

#include <iostream>
#include <vector>
#include <string>
#include <cmath>using namespace std;// 存储所有解法
vector<vector<int>> allSolutions;// 检查当前放置是否有效
bool check(const vector<int>& path, int i, int j, int n) {for (int k = 0; k < i; k++) {if (j == path[k] || abs(i - k) == abs(j - path[k])) {return false;}}return true;
}// 回溯法求解N皇后问题
void backtrack(int i, vector<int>& path, int n) {if (i == n) {// 找到一种有效解，将其添加到allSolutions中allSolutions.push_back(path);return;}for (int j = 0; j < n; j++) {if (check(path, i, j, n)) {path[i] = j;backtrack(i + 1, path, n);}}
}// 辅助方法：根据path数组生成棋盘的图形表示
void printBoard(const vector<int>& path) {int n = path.size();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (path[i] == j) {cout << "Q ";} else {cout << ". ";}}cout << endl;}cout << endl;
}int main() {int n;cout << "请输入皇后的数量n: ";cin >> n;if (n < 1) {cout << "没有找到有效的解法。" << endl;return 0;}vector<int> path(n, -1); // 初始化路径数组backtrack(0, path, n);if (allSolutions.empty()) {cout << "没有找到有效的解法。" << endl;} else {for (size_t i = 0; i < allSolutions.size(); i++) {cout << "解法 " << (i + 1) << ":" << endl;printBoard(allSolutions[i]);}cout << "总共有 " << allSolutions.size() << " 种解法。" << endl;}return 0;
}

3.位运算求八皇后（n皇后）问题（最优解）

参考视频
（以下拿五皇后问题为例）

用位信息表示列限制

用位信息来表示皇后放置的位置。
一个整型int变量有32位，表示现在哪些列已经摆放了皇后，不是用整型的值，而是用整数的位信息状态来表示哪些列已经摆放了皇后。

如图，如果是要摆放5*5的棋盘，5皇后问题。
在0到4行，0到4列的格子种，皇后摆放到了0行1列，那位信息就是这样的。第一位的位信息为1，其余为0，表示第一列有皇后放置。

如果在第1行，第3列，又摆放了一个皇后。则位信息变为上图。

整体过程如上图。

用位信息表示对角线限制

从右上往左下的限制 如何用位信息表示

如果此时的摆放如图，那么下一行是在第一列的位置无法摆放皇后的。
用left表示限制
此时的数组left为

下一行的left数组为

也就是把第一个状态的位信息右移，就可以得到第二个状态的位信息。
如果此时，在第四列再放置一个皇后，那此时的位信息变为

那如何表达此时的整体状态对下面的影响：将整体的位信息右移

如果位信息在右移过程中出现了，溢出现象，也没有关系，说明“影响”已经出格子了，没有限制了。

从左上往右下的限制 如何用位信息表示

以right表示
左移
同理
过程如图：

如何整合在一起

列限制：col：1不可以放，0可以放皇后
右上到左下限制：left：1不可以放，0可以放皇后
左上到右下限制：right：1不可以放，0可以放皇后
三个限制都是int类型的整数
共同限制：一个或在一起
col || left || right 1不可以放，0可以放皇后
~（共同的限制）：共同的限制取反：0不可以放，1可以放皇后
所以放皇后的时候尝试所有1的位置就可以了。并且注意不能超出0~4的范围（对于5皇后问题）

n皇后II

可直接提交的代码（java实现）（位信息方法）

class Solution {// 用位信息表示路径实现的N皇后问题，推荐public static int totalNQueens(int n) {if (n < 1) {return 0;}// n = 5（如果是五皇后问题）// 1 << 5 = 0...100000 - 1（1向左移动5个状态得到limit）// limit  = 0...011111; （limit是规定范围用的）// n = 7// limit  = 0...01111111; int limit = (1 << n) - 1;//用状态来限制几皇后的问题return f2(limit, 0, 0, 0);}// limit : 当前是几皇后问题（低位上有几个1就是几皇后问题）// 之前皇后的列影响：col// 之前皇后的右上 -> 左下对角线影响：left// 之前皇后的左上 -> 右下对角线影响：rightpublic static int f2(int limit, int col, int left, int right) {if (col == limit) {// 所有皇后放完了！return 1;}// 总限制int ban = col | left | right;// ~ban :（总限制取反后代表） 1可放皇后，0不能放int candidate = limit & (~ban);//并且希望在有效的范围内表示出来// 放置皇后的尝试！int place = 0;// 一共有多少有效的方法int ans = 0;while (candidate != 0) {// （注释后的第一句的意思就是）提取出最右侧的1// 0 0 1 1 1 0// 5 4 3 2 1 0// place : // 0 0 0 0 1 0（这个状态就是提取出来的最右侧的1）// candidate : // 0 0 1 1 0 0// 5 4 3 2 1 0// place : // 0 0 0 1 0 0// candidate : // 0 0 1 0 0 0// 5 4 3 2 1 0// place : // 0 0 1 0 0 0// candidate : // 0 0 0 0 0 0// 5 4 3 2 1 0place = candidate & (-candidate);candidate ^= place;//异或ans += f2(limit, col | place, (left | place) >> 1, (right | place) << 1);}return ans;}}

可在编译器运行 出图案的代码 （Java实现）

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {// 存储所有解法public static List<int[]> allSolutions = new ArrayList<>();// 用位信息表示路径实现的N皇后问题，推荐public static int totalNQueens(int n) {if (n < 1) {return 0;}// n = 5（如果是五皇后问题）// 1 << 5 = 0...100000 - 1（1向左移动5个状态得到limit）// limit  = 0...011111; （limit是规定范围用的）// n = 7// limit  = 0...01111111;int limit = (1 << n) - 1;//用状态来限制几皇后的问题backtrack(limit, 0, 0, 0, new int[n]);return allSolutions.size();}// 回溯法求解N皇后问题public static void backtrack(int limit, int col, int left, int right, int[] path) {if (col == limit) {// 找到一种有效解，将其添加到allSolutions中allSolutions.add(path.clone());return;}// 总限制int ban = col | left | right;// ~ban :（总限制取反后代表） 1可放皇后，0不能放int candidate = limit & (~ban);//并且希望在有效的范围内表示出来// 放置皇后的尝试！while (candidate != 0) {// 提取出最右侧的1int place = candidate & (-candidate);candidate ^= place;//异或// 计算新的路径int row = Integer.bitCount(col);path[row] = Integer.numberOfTrailingZeros(place);// 递归调用backtrack(limit, col | place, (left | place) >> 1, (right | place) << 1, path);}}// 辅助方法：根据path数组生成棋盘的图形表示public static void printBoard(int[] path) {int n = path.length;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (path[i] == j) {System.out.print("Q ");} else {System.out.print(". ");}}System.out.println();}System.out.println();}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.print("请输入皇后的数量n: ");int n = scanner.nextInt();int total = totalNQueens(n);if (total == 0) {System.out.println("没有找到有效的解法。");} else {System.out.println("总共有 " + total + " 种解法。");for (int i = 0; i < allSolutions.size(); i++) {System.out.println("解法 " + (i + 1) + ":");printBoard(allSolutions.get(i));}}scanner.close();}
}

可在编译器运行 出图案的代码 （c++实现）

#include <iostream>
#include <vector>
#include <string>using namespace std;// 存储所有解法
vector<vector<int>> allSolutions;// 回溯法求解N皇后问题
void backtrack(int limit, int col, int left, int right, vector<int>& path, int n) {if (col == limit) {// 找到一种有效解，将其添加到allSolutions中allSolutions.push_back(path);return;}// 总限制：col | left | rightint ban = col | left | right;// 可选位置：limit & (~ban)，1表示可以放置皇后int candidate = limit & (~ban);// 尝试放置皇后while (candidate != 0) {// 提取最右侧的1int place = candidate & (-candidate);candidate ^= place; // 移除已放置的位置// 计算当前行的索引int row = __builtin_popcount(col);path[row] = __builtin_ctz(place);// 递归调用，更新限制backtrack(limit, col | place, (left | place) << 1, (right | place) >> 1, path, n);}
}// 辅助方法：根据path数组生成棋盘的图形表示
void printBoard(const vector<int>& path) {int n = path.size();for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {if (path[i] == j) {cout << "Q ";} else {cout << ". ";}}cout << endl;}cout << endl;
}int main() {int n;cout << "请输入皇后的数量n: ";cin >> n;if (n < 1) {cout << "没有找到有效的解法。" << endl;return 0;}// 初始化limit为(1 << n) - 1，例如n=4时，limit=0b1111int limit = (1 << n) - 1;vector<int> path(n, -1); // 初始化路径数组backtrack(limit, 0, 0, 0, path, n);if (allSolutions.empty()) {cout << "没有找到有效的解法。" << endl;} else {for (size_t i = 0; i < allSolutions.size(); ++i) {cout << "解法 " << (i + 1) << ":" << endl;printBoard(allSolutions[i]);}cout << "总共有 " << allSolutions.size() << " 种解法。" << endl;}return 0;
}

4.数组方法存皇后限制（回溯）与位运算方法的时间对比

public class Main {// 用数组表示路径实现的N皇后问题，不推荐public static int totalNQueens1(int n) {if (n < 1) {return 0;}return f1(0, new int[n], n);}// i : 当前来到的行// path : 0...i-1行的皇后，都摆在了哪些列// n : 是几皇后问题// 返回 : 0...i-1行已经摆完了，i....n-1行可以去尝试的情况下还能找到几种有效的方法public static int f1(int i, int[] path, int n) {if (i == n) {return 1;}int ans = 0;// 0 1 2 3 .. n-1// i jfor (int j = 0; j < n; j++) {if (check(path, i, j)) {path[i] = j;ans += f1(i + 1, path, n);}}return ans;}// 当前在i行、j列的位置，摆了一个皇后// 0...i-1行的皇后状况，path[0...i-1]// 返回会不会冲突，不会冲突，有效！true// 会冲突，无效，返回falsepublic static boolean check(int[] path, int i, int j) {// 当前 i// 当列 jfor (int k = 0; k < i; k++) {// 0...i-1// 之前行 : k// 之前列 : path[k]if (j == path[k] || Math.abs(i - k) == Math.abs(j - path[k])) {return false;}}return true;}// 用位信息表示路径实现的N皇后问题，推荐public static int totalNQueens2(int n) {if (n < 1) {return 0;}// n = 5// 1 << 5 = 0...100000 - 1// limit  = 0...011111;// n = 7// limit  = 0...01111111;int limit = (1 << n) - 1;return f2(limit, 0, 0, 0);}// limit : 当前是几皇后问题// 之前皇后的列影响：col// 之前皇后的右上 -> 左下对角线影响：left// 之前皇后的左上 -> 右下对角线影响：rightpublic static int f2(int limit, int col, int left, int right) {if (col == limit) {// 所有皇后放完了！return 1;}// 总限制int ban = col | left | right;// ~ban : 1可放皇后，0不能放int candidate = limit & (~ban);// 放置皇后的尝试！int place = 0;// 一共有多少有效的方法int ans = 0;while (candidate != 0) {// 提取出最右侧的1// 0 0 1 1 1 0// 5 4 3 2 1 0// place :// 0 0 0 0 1 0// candidate :// 0 0 1 1 0 0// 5 4 3 2 1 0// place :// 0 0 0 1 0 0// candidate :// 0 0 1 0 0 0// 5 4 3 2 1 0// place :// 0 0 1 0 0 0// candidate :// 0 0 0 0 0 0// 5 4 3 2 1 0place = candidate & (-candidate);candidate ^= place;ans += f2(limit, col | place, (left | place) >> 1, (right | place) << 1);}return ans;}public static void main(String[] args) {int n = 14;long start, end;System.out.println("测试开始");System.out.println("解决" + n + "皇后问题");start = System.currentTimeMillis();System.out.println("方法1答案 : " + totalNQueens1(n));end = System.currentTimeMillis();System.out.println("方法1运行时间 : " + (end - start) + " 毫秒");start = System.currentTimeMillis();System.out.println("方法2答案 : " + totalNQueens2(n));end = System.currentTimeMillis();System.out.println("方法2运行时间 : " + (end - start) + " 毫秒");System.out.println("测试结束");System.out.println("=======");System.out.println("只有位运算的版本，才能10秒内跑完16皇后问题的求解过程");start = System.currentTimeMillis();int ans = totalNQueens2(16);end = System.currentTimeMillis();System.out.println("16皇后问题的答案 : " + ans);System.out.println("运行时间 : " + (end - start) + " 毫秒");}}

总结

基于回溯法解决n皇后问题+以位运算方法优化n皇后问题