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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/489761.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Linux - MySQL迁移至一主一从

Linux - MySQL迁移至一主一从 迁移准备安装MySQL ibd文件迁移原服务器操作目标服务器操作 一主一从增量同步异常解决结尾 首先部分单独安装MySQL&#xff0c;请参考Linux - MySQL安装&#xff0c;迁移数据量比较大约400G左右且网络不通故使用文件迁移&#xff0c;需开启一段时间…

PaddleOCR模型ch_PP-OCRv3文本检测模型研究(一)骨干网络

从源码上看&#xff0c;PaddleOCR一共支持四个版本&#xff0c;分别是PP-OCR、PP-OCRv2、PP-OCRv3、PP-OCRv4。本文选择PaddleOCR的v3版本的骨干网络作为研究对象&#xff0c;力图探究网络模型的内部结构。 文章目录 研究起点卷归层压发层残差层骨干网代码实验小结 研究起点 参…

数据结构——栈的模拟实现

大家好&#xff0c;今天我要介绍一下数据结构中的一个经典结构——栈。 一&#xff1a;栈的介绍 与顺序表和单链表不同的是&#xff1a; 顺序表和单链表都可以在头部和尾部插入和删除数据&#xff0c;但是栈的结构就锁死了&#xff08;栈的底部是堵死的&#xff09;栈只能从…

Ubuntu 安装 Samba Server

在 Mac 上如何能够与Ubuntu 服务器共享文件夹&#xff0c;需要在 Ubuntu 上安装 Samba 文件服务器。本文将介绍如何在 Ubuntu 上安装 Samba 服务器从而达到以下目的&#xff1a; Mac 与 Ubuntu 共享文件通过用户名密码访问 安装 Samba 服务 sudo apt install samba修改配置文…

Alan Chhabra:MongoDB AI应用程序计划(MAAP) 为客户提供价值

MongoDB全球合作伙伴执行副总裁 Alan Chhabra 每当有人向我问询MongoDB&#xff0c;我都会说他们很可能在不觉之间已经与MongoDB有过交集。事实上&#xff0c;包括70%财富百强在内的许多世界领先企业公司都在使用MongoDB。我们在MongoDB所做的一切都是为了服务客户&#xff0c…

计算机组成原理与系统结构——微程序控制

笔记内容及图片整理自XJTUSE “计算机组成原理与系统结构” 课程ppt&#xff0c;仅供学习交流使用&#xff0c;谢谢。 基本概念 微指令 将控制单元实现为基本逻辑单元之间的互连并非易事&#xff0c;且设计相对呆板&#xff0c;难以灵活地改变&#xff0c;因此实现微程序控制…

CUDA算子手撕与面试指南

引言 最近秋招落幕&#xff0c;期间一直在找高性能计算&#xff08;HPC&#xff09;相关岗位&#xff0c;整理了一些CUDA算子手撕的代码和知识点分享给大家。 项目地址&#xff1a;https://github.com/Tongkaio/CUDA_Kernel_Samples 如果觉得本项目对你有帮助&#xff0c;欢…

IIS部署程序https是访问出现403或ERR_HTTP2_PROTOCOL_ERROR

一、说明 在windows server 2016中的IIS程序池里部署一套系统&#xff0c;通过https访问站点&#xff0c;同时考虑到安全问题以及防攻击等行为&#xff0c;就用上了WAF云盾功能&#xff0c;能有效的抵挡部分攻击&#xff0c;加强网站的安全性和健壮性。 应用系统一直能够正常…

【EthIf-05】 Ethernet Interface main function

Ethernet Interface main function函数有以下功能和要点&#xff1a; 要实现支持轮询模式下帧传输确认和帧接收的以太网接口轮询机制&#xff1a;实现轮询功能&#xff0c;定期检查传入的帧。帧传输确认&#xff1a;包括确认帧已成功传输的机制。可配置轮询周期&#xff1a;允…

康耐视智能相机(Insight)通过ModbusTCP发送字符串到倍福(BECKHOFF)PLC中

文章目录 1.背景2.分析3.实现3.1.PLC的ModbusTCP_Server3.1.1.安装TF6250-Modbus-TCP3.1.2.PLC设置 3.2.智能相机的ModbusTCP_Client3.2.1.了解ModbusTCP的协议3.2.2.根据协议写代码3.2.2.1.纯函数代码3.2.2.2.脚本代码 3.2.3.非脚本处理时的代码逻辑图3.2.4.关于代码的问题及解…

ruoyi Cannot find module ‘@/views/system/user/index‘

Cannot find module /views/system/user/index 删除node_module 后打包成功

如何将你的 Ruby 应用程序从 OpenSearch 迁移到 Elasticsearch

作者&#xff1a;来自 Elastic Fernando Briano 将 Ruby 代码库从 OpenSearch 客户端迁移到 Elasticsearch 客户端的指南。 OpenSearch Ruby 客户端是从 7.x 版 Elasticsearch Ruby 客户端分叉而来的&#xff0c;因此代码库相对相似。这意味着当将 Ruby 代码库从 OpenSearch 迁…

spring cloud contract http实例

微服务很多时&#xff0c;服务之前相互调用&#xff0c;接口参数的一致性要变得很难维护。 spring cloud contract 提供了测试接口一致性的方法。 一 项目配置 plugins {id "groovy"id "org.springframework.cloud.contract" version "4.0.5"i…

帆软的无数据展示方案

文章目录 需求描述第一步、设置控件第二步、设置数据集优化改进 在日常工作中&#xff0c;使用到帆软报表工具&#xff0c;以下记录日常使用的过程&#xff0c; 需求描述 用帆软报表展示销量的信息&#xff0c;选择不同的订单状态&#xff0c;展示其订单数和总金额。 第一步、…

【操作系统】实验九:设备驱动程序

实验9 设备驱动程序 在钻研Linux内核的人当中&#xff0c;大多数人都是在写设备驱动程序。尽管由于设备的特殊性&#xff0c;使得每个驱动程序都不一样。但是编写设备驱动程序的许多原则和基本技巧都是一样的&#xff0c;甚至Windows下的设备驱动程序从原理上讲也与之相通。在…

文件上传—阿里云OSS对象存储

目录 一、OSS简介 二、OSS基本使用 1. 注册账号 2. 基本配置 (1) 开通OSS (2) 创建存储空间 (3) 修改权限 (4) 配置完成&#xff0c;上传一张图片&#xff0c;检验是否成功。 (5) 创建AccessKey 三、Java项目集成OSS 1. 导入依赖 2. Result.java代码&#xff1a; …

极米投影仪-看电视

文章目录 前言操作步骤1.进入GitHub下载软件2.修改后缀3.粘贴到U盘 前言 使用网络提供的电视接口免费看电视。 操作步骤 1.进入GitHub下载软件 地址&#xff1a;https://github.com/andandroidor/ourtv 也可以直接下载我已保存的apk&#xff0c;地址&#xff1a;https://d…

重生之我在异世界学编程之C语言:深入文件操作篇(下)

大家好&#xff0c;这里是小编的博客频道 小编的博客&#xff1a;就爱学编程 很高兴在CSDN这个大家庭与大家相识&#xff0c;希望能在这里与大家共同进步&#xff0c;共同收获更好的自己&#xff01;&#xff01;&#xff01; 函数递归与迭代 引言正文一、文件的基本操作&#…

Rust HTTP请求库

GITHUB 地址 LTPP-GIT 地址 接口文档 说明 http-request 是一个轻量级、高效的库&#xff0c;用于在 Rust 应用程序中构建、发送和处理 HTTP/HTTPS 请求。它提供了一个简单直观的 API&#xff0c;使开发人员可以轻松地与使用 “HTTP” 或 “HTTPS” 协议的 Web 服务进行交互…

ERC论文阅读(03)--instructERC论文阅读笔记(2024-12-14)

instructERC论文阅读笔记 2024-12-14 论文题目&#xff1a;InstructERC: Reforming Emotion Recognition in Conversation with Multi-task Retrieval-Augmented Large Language Models 说明&#xff1a;以下内容纯属本人看论文及复现代码的记录&#xff0c;如想了解论文细节&…