【算法】用回溯法(backtracking algorithm)求解N皇后问题(N-Queens puzzle)

2023-10-08 00:38
文章标签 算法 问题 皇后 求解 回溯 algorithm backtracking queens puzzle

本文主要是介绍【算法】用回溯法(backtracking algorithm)求解N皇后问题(N-Queens puzzle)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

什么是N-皇后问题?

说到这个N-皇后问题，就不得不先提一下这个历史上著名的8皇后问题啦。

八皇后问题，是一个古老而著名的问题.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法?

那么，我们将8皇后问题推广一下，就可以得到我们的N皇后问题了。N皇后问题是一个经典的问题，在一个NxN的棋盘上放置N个皇后，使其不能互相攻击 (同一行、同一列、同一斜线上的皇后都会自动攻击) 那么问，有多少种摆法？

回溯算法(backtracking algorithm)

N皇后问题其实就是回溯算法中的一个典型应用。为此，在这里先介绍一下回溯算法。

定义(参考至百度百科)

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

基本思想

回溯算法的基本思想是：**从一条路往前走，能进则进，不能进则退回来，换一条路再试。**在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。

  • 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
  • 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
什么是深度优先搜索？
  • 深度优先搜索(DFS即Depth First Search)其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
解决问题的一般步骤
  • 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
  • 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
  • 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。**此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。**回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

解空间和解空间树
  • 解空间
    一个复杂问题的解决往往由多部分构成，那么，一个大的解决方案就可以看成是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来，解任何问题都有一个目标，在约束条件下使目标值达到最大（或最小）的可行解称为该问题的最优解。在解空间中，前k项决策已经取定的所有决策序列之集，称为k定子解空间。0定子解空间即是该问题的解空间。这个空间必须至少包含一个解（可能是最优的）。
  • 解空间树
    因为回溯方法的基本思想是通过搜索解空间来找到问题所要求的解，所以如何组织解空间的结构会直接影响对问题的求解效率。一般地，我们可以用一棵树来描述解空间，并称之为解空间树。
算法框架
  • 针对N叉树的递归回溯方法
//针对N叉树的递归回溯方法  
void backtrack (int t)
{if (t>n){output(x); //叶子节点，输出结果，x是可行解}else{for i = 1 to k//当前节点的所有子节点{x[t]=value(i); //每个子节点的值赋值给x//满足约束条件和限界条件if (constraint(t)&&bound(t))backtrack(t+1); //递归下一层}}
}
  • 针对N叉树的迭代回溯方法
//针对N叉树的迭代回溯方法
void iterativeBacktrack ()  
{  int t=1;  while (t>0){  if(ExistSubNode(t)) //当前节点的存在子节点  {  for i = 1 to k  //遍历当前节点的所有子节点  {  x[t]=value(i);//每个子节点的值赋值给x  if (constraint(t)&&bound(t))//满足约束条件和限界条件   {  //solution表示在节点t处得到了一个解  if (solution(t))output(x);//得到问题的一个可行解，输出  elset++;//没有得到解，继续向下搜索  }  }  }  else //不存在子节点，返回上一层  t--;  }  
}

N皇后问题的solve

算法伪代码描述

下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘：

  1. 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列

  2. 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步

  3. 在当前位置上满足条件的情形：

    • 在当前位置放一个皇后，若当前行是最后一行，记录一个解；
    • 若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；
    • 若当前行是最后一行，当前列不是最后一列，当前列设为下一列；
    • 若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置。
    • 以上返回到第2步

  4. 在当前位置上不满足条件的情形：

  • 若当前列不是最后一列，当前列设为下一列，返回到第2步;
  • 若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步;
图解问题过程

为了让大家更好理解，这里画了一张图。

coding time

我们之前说过N皇后问题是回溯算法的经典应用。因此我们可以使用回溯法来解决该问题，具体实现也有两个途径，递归和非递归。

  • 递归法
    其实递归法算是比较简单的了。我们使用一个一维数组来存储棋盘。具体细节如下：把棋盘存储为一个一维数组a[N]，数组中第i个元素的值代表第i行的皇后位置。在判断是否冲突时也很简单：
    • 首先每行只有一个皇后，且在数组中只占据一个元素的位置，行冲突就不存在了。
    • 其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。
    • 至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有规律。即它们所在的行列互减的绝对值相等，即| row – i | = | col – a[i] | 。
#include <stdio.h>
#include <stdlib.h>const int N=20;   //最多放皇后的个数
int q[N];         //i表示皇后所在的行号，//q[i]表示皇后所在的列号
int cont = 0;     //统计解的个数
//输出一个解
void print(int n)
{int i,j;cont++;printf("第%d个解：",cont);for(i=1;i<=n;i++)printf("(%d,%d) ",i,q[i]);printf("\n");for(i=1;i<=n;i++)        //行{for(j=1;j<=n;j++)    //列{if(q[i]!=j)printf("x ");elseprintf("Q ");}printf("\n");}
}
//检验第i行的k列上是否可以摆放皇后
int find(int i,int k)
{int j=1;while(j<i)  //j=1~i-1是已经放置了皇后的行{//第j行的皇后是否在k列或(j,q[j])与(i,k)是否在斜线上if(q[j]==k || abs(j-i)==abs(q[j]-k))return 0;j++;}return 1;
}
//放置皇后到棋盘上
void place(int k,int n)
{int j;if(k>n)print(n); //递归出口else{for(j=1;j<=n;j++)   //试探第k行的每一个列{if(find(k,j)){q[k] = j;   //保存位置place(k+1,n);  //接着下一行}}}
}
int main1111(void)
{int n;printf("请输入皇后的个数(n<=20),n=:");scanf("%d",&n);if(n>20)printf("n值太大，不能求解!\n");else{printf("%d皇后问题求解如下(每列的皇后所在的行数):\n",n);place(1,n);        //问题从最初状态解起printf("\n");}system("pause");return 0;
}
  • 迭代法
    为什么还要迭代呢？因为递归效率有时候并不是那么的高。具体思路：首先对N行中的每一行进行探测，查找该行中可以放皇后的位置。具体怎么做呢？
    • 首先对该行的逐列进行探测，看是否可以放置皇后，如果可以，则在该列放置一个皇后，然后继续探测下一行的皇后位置。
    • 如果已经探测完所有的列都没有找到可以放置皇后的列，这时候就应该回溯了，把上一行皇后的位置往后移一列。
    • 如果上一行皇后移动后也找不到位置，则继续回溯直至某一行找到皇后的位置或回溯到第一行，如果第一行皇后也无法找到可以放置皇后的位置，则说明已经找到所有的解，程序终止。
    • 如果该行已经是最后一行，则探测完该行后，如果找到放置皇后的位置，则说明找到一个结果，打印出来。
    • 但是此时并不能在此处结束程序，因为我们要找的是所有N皇后问题所有的解，此时应该清除该行的皇后，从当前放置皇后列数的下一列继续探测。

由此可见，非递归方法的一个重要问题时何时回溯及如何回溯的问题。

具体代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define QUEEN 8     //皇后的数目
#define INITIAL -10000 //棋盘的初始值int a[QUEEN];    //一维数组表示棋盘void init()  //对棋盘进行初始化
{int *p;for (p = a; p < a + QUEEN; ++p){*p = INITIAL;}
}int valid(int row, int col)    //判断第row行第col列是否可以放置皇后
{int i;for (i = 0; i < QUEEN; ++i)  //对棋盘进行扫描{   //判断列冲突与斜线上的冲突if (a[i] == col || abs(i - row) == abs(a[i] - col))return 0;}return 1;
}void print()    //打印输出N皇后的一组解
{int i, j;for (i = 0; i < QUEEN; ++i){for (j = 0; j < QUEEN; ++j){if (a[i] != j)      //a[i]为初始值printf("%c ", '.');else                //a[i]表示在第i行的第a[i]列可以放置皇后printf("%c ", '#');}printf("\n");}for (i = 0; i < QUEEN; ++i)printf("%d ", a[i]);printf("\n");printf("--------------------------------\n");
}void queen()      //N皇后程序
{int n = 0;int i = 0, j = 0;while (i < QUEEN){while (j < QUEEN)        //对i行的每一列进行探测，看是否可以放置皇后{if(valid(i, j))      //该位置可以放置皇后{a[i] = j;        //第i行放置皇后j = 0;           //第i行放置皇后以后，需要继续探测下一行的皇后位置，//所以此处将j清零，从下一行的第0列开始逐列探测break;}else{++j;             //继续探测下一列}}if(a[i] == INITIAL)         //第i行没有找到可以放置皇后的位置{if (i == 0)             //回溯到第一行，仍然无法找到可以放置皇后的位置，//则说明已经找到所有的解，程序终止break;else                    //没有找到可以放置皇后的列，此时就应该回溯{--i;j = a[i] + 1;        //把上一行皇后的位置往后移一列a[i] = INITIAL;      //把上一行皇后的位置清除，重新探测continue;}}if (i == QUEEN - 1)          //最后一行找到了一个皇后位置，//说明找到一个结果，打印出来{printf("answer %d : \n", ++n);print();//不能在此处结束程序，因为我们要找的是N皇后问题的所有解，//此时应该清除该行的皇后，从当前放置皇后列数的下一列继续探测。j = a[i] + 1;             //从最后一行放置皇后列数的下一列继续探测a[i] = INITIAL;           //清除最后一行的皇后位置continue;}++i;              //继续探测下一行的皇后位置}
}int main(void)
{init();queen();system("pause");return 0;
}

注：资料整合自网络。
请关注我们的微信公众号【程序猿声】。

微信公众号

这篇关于【算法】用回溯法(backtracking algorithm)求解N皇后问题(N-Queens puzzle)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/161515。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
缓存雪崩问题

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库，瞬间耗尽数据库资源，导致数据库无法使用。 解决方案： 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内，大量缓存数据同时失效，导致所有请求直接涌向数据库，瞬间增加数据库的负载压力，可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2