数据结构（6）栈和队列->栈的应用之八皇后问题
整理数据结构学习笔记基于C++文章目录一、八皇后问题二、回溯法三、一个小例子1、问题2、求解方法3、递归图示四、八皇后问题的求解1、数据结构设计2、判断条件3、程序代码五、N皇后问题一、八皇后问题经典的八皇后问题，即在一个8*8的棋盘上放8个皇后任意2个皇后不能处于同一行任意2个皇后不能处于同一列任意2个皇后不能处于同一对角线上输出所有可能的摆放情况此问题也可推广为N...
·
- 整理数据结构学习笔记
- 基于C++
一、八皇后问题
经典的八皇后问题，即
- 在一个8*8的棋盘上放8个皇后
- 任意2个皇后不能处于同一行
- 任意2个皇后不能处于同一列
- 任意2个皇后不能处于同一对角线上
- 输出所有可能的摆放情况
此问题也可推广为N*N大小棋盘上的N皇后问题
二、回溯法
回溯法是解八皇后问题的一个常用算法，和深度优先搜索很类似，摘录其定义如下：
- 回溯法（探索与回溯法）：
是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 - 基本思想：
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束
根据以上描述，可以看出回溯法适合用递归实现
三、一个小例子
下面看一个递归回溯法的例子，理解了这个之后八皇后问题就很简单了。
1、问题
输入正整数n，输出1到n的全排列
2、求解方法
- 设全局标记flag数组，flag[i]标记数值（i+1）有没有被计入当前全排列
- 递归函数定义为void dfs(int num)，num记录当前计入全排列的数个数，递归边界条件为num==n。在递归函数中遍历1到n，判断其对应的flag标志，若其没有加入全排列则加入并修改flag值，调用dfs(num+1)。调用后紧接着恢复num和flag值，以保证回溯到这里时各变量情况和第一次到达此处时一样
- 若递归到边界条件，输出当前全排列，然后直接return
3、递归图示
以输出3的全排列为例，递归流程如下
输出如下
代码如下，请结合流程图仔细分析递归流程
//输出1 2 3 ... n的全排列
#include<iostream>
#include<cstdlib>
using namespace std;
int *a; //a[]用来存排列
int *flag; //flag[0]~flag[n-1]表示1~n有没有被排进a[]
int n;
//可以看做回溯，也可看做深度优先搜索
void dfs(int num)
{
//达到边界状态（填满），递归结束
if(num==n)
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
return;
}
else
{
for(int i=0;i<n;i++)
{
if(flag[i])
{
a[num++]=i+1,flag[i]=0; //遍历搜索没有排入a[]的加入a[]中
dfs(num); //找下一个数
num--,flag[i]=1; //回溯时还原标记，这样才能把i+1填入后面的位
}
}
}
}
int main()
{
cin>>n;
a=(int*)malloc(n*sizeof(int));
flag=(int*)malloc(n*sizeof(int));
//标志初始化
for(int i=0;i<n;i++)
flag[i]=1;
//递归开始
dfs(0);
}
四、八皇后问题的求解
1、数据结构设计
用栈的结构来存储棋盘，可以进行如下转换：
将每一行中皇后位置存入栈中，棋盘第一行对应栈顶，第八行对应栈底
把栈中元素看做一个排列，问题转换为：在1~8的全排列中，选择符合八皇后要求的排列，这一转换十分重要
//栈结构
typedef struct
{
int *base;//指向最下面元素
int *top;//指向真正顶部再上一个
int stacksize;
}SqStack;
2、判断条件
每往栈中压入一个新数（代表当前最上一行皇后位置）使其成为栈顶元素后，进行如下判断：
- 在同一行：
根据上述栈的建立方式，不可能在同一行出现两个皇后 - 在同一列：
从栈底遍历至栈顶 for(int i=0;i<StackLength-1;i++)，判断*(s.base+i)==top，或者利用上面全排列例子中的方法，设全局flag数组标记 - 在同一主对角线：
从栈底遍历至栈顶 for(int i=0;i<StackLength-1;i++)，判断*(s.base+i)+i+1==top+L（棋盘中表现为行号+列号相等） - 在同一副对角线：
从栈底遍历至栈顶 for(int i=0;i<StackLength-1;i++)，判断*(s.base+i)-i-1==top-L（棋盘中表现为行号-列号相等）
若上述任意情况出现，判断为当前行皇后位置不可行，需进行回溯
3、程序代码
//避免同列错误，可以给每个列设标志，也可在错误判断时一并拒绝
//此程序中两种都写了，注释掉一种也可正常工作
#include<iostream>
#include<cstdlib>
using namespace std;
#define STACK_INIT_SIZE 10
#define OK true
#define ERROR false
#define OVERFLOW -1
int flag[8]={0};
int cnt=0;
typedef struct
{
int *base;//指向最下面元素
int *top;//指向真正顶部再上一个
int stacksize;
}SqStack;
bool InitStack(SqStack &s)
{
s.base = (int *)malloc(STACK_INIT_SIZE*sizeof(int));
if(!s.base)
exit(OVERFLOW);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return OK;
}
bool StackEmpty(SqStack s)
{
if(s.top==s.base)
return true;
else
return false;
}
int StackLength(SqStack s)
{
return s.top-s.base;
}
bool GetTop(SqStack s,int &e)
{
if(StackEmpty(s))
return ERROR;
e=*(s.top-1);
return OK;
}
bool push(SqStack &s,int e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(int *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(int));
if(!s.base)
exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e;
return OK;
}
bool pop(SqStack &s,int &e)
{
if(s.top==s.base)
return ERROR;
e=*(s.top-1);
s.top--;
return OK;
}
//----------------------------------------------
void ShowElem(SqStack s)
{
int *p=s.base;
while(p<s.top)
cout<<*(p++)<<" ";
cout<<endl;
}
void ShowStack(SqStack s)
{
if(StackEmpty(s))
cout<<"空栈,长度"<<StackLength(s)<<endl;
else
cout<<"皇后列位置(第8行到第1行)：", ShowElem(s);
cout<<endl;
}
bool avalible(SqStack s)
{
int L=StackLength(s);
int top;
GetTop(s,top);
for(int i=0;i<L-1;i++)
if(*(s.base+i)+i+1==top+L || *(s.base+i)-i-1==top-L || *(s.base+i)==top )//最后一个是通过用栈存储棋盘的特性来避免同列错误
return ERROR;
return OK;
}
void insert(SqStack &s,int PuttedNum)
{
int p;
if(PuttedNum==8)
{
cnt++;
ShowStack(s);
return;
}
else
{
for(int j=0;j<8;j++)
{
if(flag[j]!=0)//用标记避免同列错误
continue;
else
{
push(s,j+1);
if(avalible(s))
{
PuttedNum++;
flag[j]=1;
insert(s,PuttedNum);
flag[j]=0;
pop(s,p);
PuttedNum--;
}
else
pop(s,p);
}
}
}
}
int main()
{
int num=0;
SqStack Stack;
//初始化
InitStack(Stack);
//输出提示语
cout<<"从前往后表示第8行到第1行中每行皇后所在列"<<endl;
//递归开始
insert(Stack,num);
cout<<"共"<<cnt<<"种"<<endl;
return 0;
}
五、N皇后问题
算法思想和八皇后完全类似，把所有长度可能变的数组之类都改动态申请就行了
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
//#define STACK_INIT_SIZE 10
#define STACKINCREMENT 10
#define OK true
#define ERROR false
#define OVERFLOW -1
int NumOfQueen;
int cnt=0;
typedef struct
{
int *base;//指向最下面元素
int *top;//指向真正顶部再上一个
int stacksize;
}SqStack;
//1
bool InitStack(SqStack &s)
{
s.base = (int *)malloc(NumOfQueen*sizeof(int));
if(!s.base)
exit(OVERFLOW);
s.top=s.base;
s.stacksize=NumOfQueen;
return OK;
}
//4
bool StackEmpty(SqStack s)
{
if(s.top==s.base)
return true;
else
return false;
}
//5
int StackLength(SqStack s)
{
return s.top-s.base;
}
//6
bool GetTop(SqStack s,int &e)
{
if(StackEmpty(s))
return ERROR;
e=*(s.top-1);
return OK;
}
//7
bool push(SqStack &s,int e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(int *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(int));
if(!s.base)
exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e;
return OK;
}
//8
bool pop(SqStack &s,int &e)
{
if(s.top==s.base)
return ERROR;
e=*(s.top-1);
s.top--;
return OK;
}
//----------------------------------------------
void ShowElem(SqStack s)
{
int *p=s.base;
while(p<s.top)
cout<<*(p++)<<" ";
cout<<endl;
}
void ShowStack(SqStack s)
{
if(StackEmpty(s))
cout<<"空栈,长度"<<StackLength(s)<<endl;
else
cout<<"皇后列位置(最后行到第1行)：", ShowElem(s);
cout<<endl;
}
bool avalible(SqStack s)
{
int L=StackLength(s);
int top;
GetTop(s,top);
for(int i=0;i<L-1;i++)
if(*(s.base+i)+i+1==top+L || *(s.base+i)-i-1==top-L || *(s.base+i)==top )
return ERROR;
return OK;
}
void insert(SqStack &s,int PuttedNum,int flag[])
{
int p;
if(PuttedNum==NumOfQueen)
{
cnt++;
ShowStack(s);
return;
}
else
{
for(int j=0;j<NumOfQueen;j++)
{
if(flag[j]!=0)
continue;
else
{
push(s,j+1);
if(avalible(s))
{
PuttedNum++;
flag[j]=1;
insert(s,PuttedNum,flag);
flag[j]=0;
pop(s,p);
PuttedNum--;
}
else
pop(s,p);
}
}
}
}
int main()
{
int num=0;
SqStack Stack;
//初始化
InitStack(Stack);
cout<<"皇后个数："<<endl;
cin>>NumOfQueen;
int *flag;
flag=(int *)malloc(NumOfQueen*sizeof(int));
for(int i=0;i<NumOfQueen;i++)
flag[i]=0;
cout<<"从前往后表示最后一行到第一行中每行皇后所在列"<<endl;
insert(Stack,num,flag);
cout<<"共"<<cnt<<"种"<<endl;
return 0;
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
4
0- 0
已为社区贡献37条内容
所有评论(0)