基于回溯法解决八皇后问题+以位运算方法优化n皇后问题（算法与数据结构期末设计）

文章目录

基于回溯法解决八皇后问题+以位运算方法优化n皇后问题1. 八皇后问题问题描述2.回溯法求八皇后（n皇后）问题①由四皇后问题引入②皇后的占位问题③皇后的放置过程④放置过程中的问题⑤回溯算法核心⑥回溯算法的求解过程⑦验证算法和代码实现LeetCode51.N皇后LeetCode52.N皇后II

3.位运算求八皇后（n皇后）问题（最优解）用位信息表示列限制用位信息表示对角线限制从右上往左下的限制 如何用位信息表示从左上往右下的限制 如何用位信息表示

如何整合在一起

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

总结

基于回溯法解决八皇后问题+以位运算方法优化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> solveNQueens(int n) {

// 传入参数n，表示n皇后问题

// 函数返回一个二维的vector

// 内部的vector是string类型

// 保存n皇后的全部解法

vector queen;

// 保存皇后位置

vector> attack;

// 保存皇后攻击位置

vector> solve;

// 保存最终结果

// 初始化attack和queen数组

for(int i=0;i

attack.push_back((std::vector()));

// 1、向量（Vector）。

// 2、它是一个动态数组，可以根据需要自动调整大小。

// 3、向量提供了一些方便的方法来管理元素，比如添加、删除和访问元素。

// 4、向量提供了一些内置功能，比如 push_back()（在末尾添加元素）、pop_back()（删除末尾元素）、size()（获取元素数量）等。

// 5、std::vector 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

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> &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是动态数组，所有以这种形式获得，长度。

// 对于八皇后问题，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=0&&ny

attack[nx][ny]=1;

// 将他标记为1

}

}

}

}

// 回溯法求解n皇后的递归函数

// k表示当前正处理的行

// n表示皇后数量

// queen存储皇后的位置

// attack标记皇后的攻击位置

// solve存储n皇后的全部解法

void backtrack(int k,int n,vector &queen,vector> &attack,vector> &solve){

// 在 backtrack 函数中，你传递了 attack 数组的副本给 put_queen，但 put_queen 函数是按值传递的，

// 这意味着对 attack 的修改不会影响递归调用外部的 attack 数组。

// 修正方法：将 put_queen 函数的参数改为引用传递，以便修改能够影响到外部的 attack 数组。

if(k==n){

// 找到了一组解

solve.push_back(queen);

// 将结果queen存储至solve

return;

}

for(int i=0;i

// 遍历每一列==>遍历第k行的第0列到n-1列

// 回溯法试探皇后的可放置的位置

if(attack[k][i]==0){

// =0表示可以放置皇后

vector> 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

#include

#include

using namespace std;

// 在(x,y)位置放置皇后，并更新攻击位置attack数组

void put_queen(int x, int y, vector> &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 &queen, vector> &attack, vector> &solve){

if(k == n){

// 找到了一组解

solve.push_back(queen);

// 将结果queen存储至solve

return;

}

for(int i = 0; i < n; i++){

// 遍历每一列==>遍历第k行的第0列到n-1列

// 回溯法试探皇后的可放置的位置

if(attack[k][i] == 0){

// =0表示可以放置皇后

vector> 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 queen;

// 保存皇后位置

vector> attack;

// 保存皇后攻击位置

vector> solve;

// 保存最终结果

// 初始化attack和queen数组

for(int i = 0; i < n; i++){

attack.push_back(vector()); // 使用 vector() 初始化

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

// 会冲突，无效，返回false

public static boolean check(int[] path, int i, int j) {

// 当前 i

// 当列 j

for (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 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

#include

#include

#include

using namespace std;

// 存储所有解法

vector> allSolutions;

// 检查当前放置是否有效

bool check(const vector& 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& 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& 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 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

// 之前皇后的左上 -> 右下对角线影响：right

public 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 0

place = 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 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) {

// 提取出最右侧的1

int 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

#include

#include

using namespace std;

// 存储所有解法

vector> allSolutions;

// 回溯法求解N皇后问题

void backtrack(int limit, int col, int left, int right, vector& path, int n) {

if (col == limit) {

// 找到一种有效解，将其添加到allSolutions中

allSolutions.push_back(path);

return;

}

// 总限制：col | left | right

int ban = col | left | right;

// 可选位置：limit & (~ban)，1表示可以放置皇后

int candidate = limit & (~ban);

// 尝试放置皇后

while (candidate != 0) {

// 提取最右侧的1

int 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& 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=0b1111

int limit = (1 << n) - 1;

vector 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 j

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]

// 返回会不会冲突，不会冲突，有效！true

// 会冲突，无效，返回false

public static boolean check(int[] path, int i, int j) {

// 当前 i

// 当列 j

for (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

// 之前皇后的左上 -> 右下对角线影响：right

public 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 0

place = 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皇后问题