C++用栈解决八皇后问题

八皇后问题c语言代码讲解八皇后问题是一个经典的回溯算法问题，要求在一个8x8的棋盘上放置8个皇后，使得它们互不攻击，即任意两个皇后都不能在同一行、同一列或同一对角线上。

下面是一个使用C语言实现八皇后问题的代码示例：c.#include <stdio.h>。

#define N 8。

int board[N][N];// 检查当前位置是否安全。

int isSafe(int row, int col) {。

int i, j;// 检查当前列是否有皇后。

for (i = 0; i < row; i++) {。

if (board[i][col] == 1) {。

return 0;}。

}。

// 检查左上对角线是否有皇后。

for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {。

if (board[i][j] == 1) {。

return 0;}。

}。

// 检查右上对角线是否有皇后。

for (i = row, j = col; i >= 0 && j < N; i--, j++) {。

if (board[i][j] == 1) {。

return 0;}。

}。

return 1;}。

// 在当前行放置皇后。

int solve(int row) {。

int col;// 所有行都放置完毕，打印结果。

if (row == N) {。

for (int i = 0; i < N; i++) {。

for (int j = 0; j < N; j++) {。

printf("%d ", board[i][j]); }。

printf("\n");}。

printf("\n");return 1;}。

// 逐列尝试放置皇后。

for (col = 0; col < N; col++) {。

15、蛤蟆的数据结构笔记之十五栈的应用之栈与递归之八皇后问题本篇名言：“人的一生应当这样度过：当回忆往事的时候，他不致于因为虚度年华而痛悔，也不致于因为过去的碌碌无为而羞愧；在临死的时候，他能够说："我的整个生命和全部精力，都已经献给世界上最壮丽的事业--为人类的解放而斗争。

”继续递归问题，本次是经典的八皇后问题：1.八皇后问题八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。

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

高斯认为有76种方案。

1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

计算机发明后，有多种计算机语言可以解决此问题。

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。

当且仅当n = 1 或n ≥ 4 时问题有解。

八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。

诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。

1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。

艾兹格·迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力。

八皇后问题出现在1990年代初期的著名电子游戏第七访客中。

在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。

国际象棋的棋盘如下图1所示：2.基本思路基本思路采用逐步试探的方式，先从一个方向往前走，能进则进，不能进则退，尝试另外的路径,类似迷宫。

八皇后的递归和非递归的解法（C++）八皇后的递归和非递归的解法(C++)//描述：用递归和非递归模拟n皇后问题//输入：问题的规模:n//输出：皇后放置的方法排列和总数#include<iostream>#include<iomanip>#include<cmath>#include<stack>using namespace std;//利用递归求解皇后问题 x[i]表示皇后放在第i行第x[i]列static int count;//判断如果皇后放在第i行，第j列是否与前面的皇后冲突bool place(int i,int j,int* path)//path存放路径{int row;for(row=0;row<i;row++){if(abs(row-i)==abs(path[row]-j))//在同一条斜线上return false;if(j==path[row])//在同一列return false;}return true;}//利用递归来求解，而且当row==0时，即求解全局的解//path[n]用来存放路径void queen(int row,int* path,int n)if(row==n){//输出结果，并将办法数加1for(int i=0;i<n;i++){cout<<setw(5)<<left<<path[i];}cout<<endl;count++;}else{int j;//表示当前列是否可行for(j=0;j<n;j++){//如果可行，则放置并且递归调用处理下一行if(place(row,j,path)){path[row]=j;//这里相当于入栈的过程queen(row+1,path,n);}}}}//利用迭代来求解void queen_another(int n,int* path) {int i=0;for(i=0;i<n;i++){int j=0;for(;j<n;j++){if(place(i,j,path)){path[i]=j;cout<<"row "<<i<<"col "<<j<<endl; break;}}//没有合适的位置，所以要回溯到上一个最合适的节点if(j==n){i--;while(i>=0){int k=path[i]+1;while(k<n&&!(place(i,k,path)))k++;if(k==n)i--;else{path[i]=k;break;}if(i<0){cout<<"there is no way "<<endl;return;}}}if(i==n)for(int j=0;j<n;j++){cout<<setw(5)<<left<<path[j];path[j]=-1000;}}//利用栈来模拟递归，在某个扩展节点出处，将所有符合条件的节点加入到里面struct pos{int row;int col;};//找到当前最合适的节点,如果没有找到则返回-1int find_col(int row,int col,int* path,int n){int j;for(j=col;j<n;j++){if(place(row,j,path))return j;if(j==n)return -1;}//利用栈来模拟八皇后问题void stack_stimu(int n,int* path){stack<struct pos> s;int currow=0;int flag=0;//主要结构分为两部分，第一按照正常顺序寻找节点//然后找出回溯的情况：在八皇后问题中主要有两中：1.到达结尾找出路径 2.当前行没有满足条件的位置while(true){if(currow<n){int col=find_col(currow,0,path,n);if(col!=-1){pos node;node.row=currow;node.col=col;s.push(node);path[currow]=col;currow++;}elseflag=1;}else{for(int i=0;i<n;i++)cout<<setw(5)<<left<<path[i];cout<<endl;count++;flag=1;}// 进行回溯if(flag==1){//描述了回溯的过程while(!s.empty()){pos temp=s.top();if(temp.col!=7){//查找当前最适合的节点，并入栈int j=find_col(temp.row,temp.col+1,path,n); if(j!=-1){pos node;node.row=temp.row;node.col=j;s.pop();s.push(node);path[temp.row]=j;currow=temp.row+1;flag=0;break;}elses.pop();}elses.pop();}if(s.empty())return;//函数的出口处}}//end for while(true)}int main(){cout<<"Queen Place Problem:"<<endl; cout<<"Input the value of n"<<endl; int n;cout<<" n>";cin>>n;int* path=new int[n];//初始化for(int i=0;i<n;i++)path[i]=-1000;//queen_another(n,path);//queen(0,path,n);stack_stimu(n,path);cout<<"the count is: "<<count<<endl; getchar();getchar(); return 0; }。

安徽建筑工业学院数据结构设计报告书院系数理系专业信息与计算科学班级11信息专升本学号11207210138姓名李晓光题目八皇后指导教师王鑫1．程序功能介绍答：这个程序是用于解决八皇后问题的。

八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。

我的程序进入时会让使用者选择程序的功能，选【1】将会通过使用者自己手动输入第一个皇后的坐标后获得答案；选【2】将会让程序自动运算出固定每一个皇后后所有的排列结果。

2．课程设计要求答：（1）增加函数，完成每输入一组解，暂停屏幕，显示“按任意键继续！”。

（2）完善程序，编程计算八皇后问题共有集中排列方案。

（3）增加输入，显示在第一个皇后确定后，共有几组排列。

（4）将每组解的期盼横向排列输出在屏幕上，将五个棋盘并排排列，即一次8行同时输出5个棋盘，同样完成一组解后屏幕暂停，按任意键继续。

（5）求出在什么位置固定一个皇后后，解的数量最多，在什么位置固定皇后后，解的数量最少，最多的解是多少，最少的解是多少，并将最多，最少解的皇后位置及所有的解求出，同样5个一组显示。

3．对课程题目的分析与注释答：众所周知的八皇后问题是一个非常古老的问题，问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击。

按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。

因此，本课程设计的目的也是通过用C++语言平台在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现。

使用递归方法最终将其问题变得一目了然，更加易懂。

首先要用到类，将程序合理化：我编辑了一个盘棋8*8的类：class Board，还有个回溯法的类：class Stack，关键的类好了，然后编辑好类的成员，然后编辑主函数利用好这些类的成员，让其运算出结果。

数据结构实验报告实验名称：实验2 利用栈结构实现八皇后问题学生姓名：廖宁班级：2009211114班内序号：18学号：09210411日期：2010年11月18日1．实验要求八皇后问题是19世纪著名的数学家高斯于1850年提出的。

他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。

请设计算法打印所有可能的摆放方法。

提示：（1）可以使用递归或非递归两种方法实现。

（2）实现一个关键算法，判断任意两个皇后是否在同一行、同一列和同一斜线上。

2. 程序分析程序工程包含一个模板类函数实现定义的源文件forthelove.cpp和测试源文件sbsuowang.cpp。

2.1 存储结构存储结构为栈。

2.2 关键算法分析(1)判断在第row行第column列摆放皇后是否非法,采取定行不定列的方法，列相等的算法为position[i]=colume，对角线相等有两种情况：一是position在上则row-i=colume-position[i];二是position在下，row-i=position[i]-colume.加入能放皇后，列和对角线上值都不能相等。

具体代码如下：int IsIllegal(int row, int column, const int* position){/int i;for (i=1; i < row; ++i){if ((position[i] == column)|| (row - i == column - position[i])|| (row - i == position[i] - column)){return TRUE;}}return FALSE;}（2）我采用定行尝试列的方法来遍历，记录皇后位置的数组可以和栈数组合二为一，而栈顶指针也可以和行坐标合二为一，这样一来栈帧只要一个列坐标就可以了。

1.伪代码：while(栈不空）{if ( 行(即栈顶) <= n && 列<= n ){if ( 当前位置不能放皇后){列++;}else{列入栈(隐含着"行++");列= 1;}}else{if ( 行(即栈顶) > n ){输出位置数组(即栈数组);}列退栈(隐含着"行--");列++;}}//end while具体实现代码：void Queens(int n, void (* Visit)(const int* position)) {//position[n]数组:position[0]为棋盘大小，即n//position[1]~position[n]：下标为行坐标，值为列坐标int* stack = NULL; //栈int top; //栈顶int column; //列stack = (int*)malloc((n + 1) * sizeof(int));stack[0] = n;top = column = 1;while(top > 0){if ((top <= n) && (column <= n)){if (IsIllegal(top, column, stack)){++column;}else{stack[top++] = column;column = 1;}}else{if (top > n){(* Visit)(stack);}column = stack[--top];++column;}}//end whilefree(stack);return;}3. 程序运行结果程序实现八皇后问题：经过测试，程序运行良好，无明显错误。

数据结构实验报告1．实验要求实验目的：利用栈结构实现八皇后问题八皇后问题如下：八皇后问题是19世纪著名的数学家高斯于1850年提出的。

他的问题是，在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行，同一列，同一斜线上。

实验内容：利用所学的栈结构用递归或非递归解决八皇后问题。

2. 程序分析程序使用程序最主要只是在主函数用了一个递归函数Queen。

Queen函数使用了三个参数m,flag[][],chess[][]。

其中m是行数，flag[][]是判断二维数组何处可以放置皇后，chess[][]是存储字符串的二维数组。

主函数中对Queen函数中的形参数组flag[][],chess[][]进行初始化，在Queen函数中再进行各种操作。

Queen函数执行代码，首先行数m为0，当m小于7时，通过if…else…语句，利用Queen(m+1,f,c)重新执行递归函数到下一行。

2.1 存储结构存储结构：数组存储。

flag[][]数组存储数字判断输出和储能放置皇后,chess[][]数组存储字符串即皇后和非皇后的形状。

2.2 关键算法分析1、关键算法：a．for(i=0;i<8;i++)for(j=0;j<8;j++){f[i][j]=0;c[i][j]='*';说明：对棋盘进行初始化未放置皇后的为“*”b．for(i=0;i<8;i++)for(j=0;j<8;j++){c[i][j]=chess[i][j];f[i][j]=flag[i][j];}说明：对c[][]，f[][]进行初始化。

c．for(i=0;i<8;i++)for(j=0;j<8;j++){i f(f[i][j]==0 && (i+j==m+k || m==i || k==j || m-k==i-j))f[i][j]=-1;}c[m][k]='#';说明：已放置皇后的行、列以及对角线都不能再放置皇后。

6 八皇后问题【问题描述】在一个8×8的国际象棋棋盘上放置8个皇后，要求每个皇后两两之间不“冲突”，即没有一个皇后能“吃掉”任何其他一个皇后，简单的说就是没有任何两个皇后占据棋盘上的同一行或同一列或同一对角线，即在每一横列、竖列、斜列都只有一个皇后。

/*file name:Queen.cDescription:利用递归法求出8个皇后问题的解*/#include<stdio.h>#include<conio.h>#define TRUE 1#define FALSE 0#define MAXQUEEN 8#define ABS(x) ((x>0)?(x):-(x)) /*求x的绝对值*//*存放8个皇后的列位置，数组注标为皇后的列位置*/int queen[MAXQUEEN];int total_solution; /*计算共有几组解*//*函数原型声明*/void place(int);int attack(int,int);void output_solution();void main(){place(0); /*从第0个皇后开始摆放至棋盘*/getch();}void place(int q){C语言大学实用教程学习指导·268·int i=0;while(i<MAXQUEEN){if(!attack(i,q)) /*皇后未受攻击*/{queen[q]=i; /*储存皇后所在的列位置*//*判断是否找到一组解*/if(q==MAXQUEEN-1)output_solution(); /*列出此组解*/elseplace(q+1); /*否则继续摆下一个皇后*/}i++;}}/*测试在（row,col）上的皇后是否遭受攻击若遭受攻击则返回值为1，否则返回0*/int attack(int row,int col){int i,atk=FALSE;int offset_row,offset_col;i=0;while(!atk&&i<col){offset_col=ABS(i-col);offset_row=ABS(queen[i]-row);/*判断两皇后是否在同一列，是否在同一对角线*//*若两皇后在同列或同对角线，则产生攻击，atk==TRUE*/atk=(queen[i]==row)||(offset_row==offset_col);i++;}return atk;}/*列出8个皇后的解*/void output_solution()第3章学习指导·269·{int x,y;total_solution+=1;printf("Solution#%3d\n\t",total_solution);for(x=0;x<MAXQUEEN;x++){for(y=0;y<MAXQUEEN;y++)if(x==queen[y])printf("Q"); /*用字母Q表示皇后*/elseprintf("-"); /*用-表示空白*/printf("\n\t");}printf("\n");}。

C语⾔回溯法解⼋皇后问题（⼋皇后算法）⼋皇后问题（N皇后问题）的回溯法求解⼀、问题描述在⼀个国际象棋棋盘上放置⼋个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋⽅法，并推⼴到N皇后情况。

⼆、参考资料啥⽂字都不⽤看，B站上有个⾮常详细的动画视频解说，上链接三、源代码#include<iostream>#include<vector>#include<string>using namespace std;void put_queen(int x, int y, vector<vector<int>>&attack){//实现在(x,y)放置皇后，对attack数组更新，xy表⽰放置皇后的坐标，attack表⽰是否可以放置皇后//⽅向数组，⽅便后⾯对8个⽅向进⾏标记static const int dx[] = { -1,-1,-1,0,0,1,1,1 };static const int dy[] = { -1,0,1,-1,1,-1,0,1 };attack[x][y] = 1;//将皇后位置标记为1//通过两层for循环，将该皇后可能攻击到的位置标记for (int i = 1; i < attack.size(); i++)//从皇后位置向1到n-1个距离延伸{for (int j = 0; j < 8; j++)//遍历8个⽅向{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}}}//回溯算法//k表⽰当前处理的⾏//n表⽰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;}//遍历0⾄n-1列，在循环中，回溯试探皇后可放置的位置for (int i = 0; i < n; i++){if (attack[k][i] == 0)//判断当前k⾏第i列是否可以放置皇后{vector<vector<int>> tmp = attack;//备份attack数组queen[k][i] = 'Q';//标记该位置为Qput_queen(k, i, attack);//更新attack数组backtrack(k + 1, n, queen, attack, solve);//递归试探k+1⾏的皇后的位置attack = tmp;//恢复attack数组queen[k][i] = '.';//恢复queen数组}}}vector<vector<string>>solveNQueens(int n){//string存储具体的摆放位置，<vector<string>>存放⼀种解法，⼆维vector存放全部解法vector<vector<string>>solve;//存储最后结果vector<vector<int>>attack;//标记皇后的攻击位vector<string>queen;//保存皇后位置//使⽤循环初始化attack和queen数组for (int i = 0; i < n; i++){attack.push_back((vector<int>()));for (int j = 0; j < n; j++){attack[i].push_back(0);}queen.push_back("");queen[i].append(n, '.');}backtrack(0, n, queen, attack, solve);return solve;//返回结果数组}int main(){//int num;//cin >> num;//输⼊皇后数初始化attack数组//vector<vector<int>> attack(num,vector<int>(num, 0));初始化queen数组//string s;//for (int i = 0; i < num; i++)s += '.';//vector<string> queen(num, s);int n;cin >> n;vector<vector<string>>result;result = solveNQueens(n);cout << n << "皇后共有" << result.size() << "种解法" << endl;for (int i = 0; i < result.size(); i++){cout << "解法" << i + 1 << ":" << endl;for (int j = 0; j < result[i].size(); j++){cout << result[i][j] << endl;}cout << endl;}system("pause");return 0;}四、测试结果四皇后⼋皇后到此这篇关于C语⾔回溯法解⼋皇后问题的⽂章就介绍到这了。

数据结构实验报告实验名称：实验二——利用栈结构实现八皇后问题学生：班级：班序号：学号：日期：实验要求实验目的：通过选择下面五个题目之一进行实现，掌握如下容：➢进一步掌握指针、模板类、异常处理的使用➢掌握栈的操作的实现方法➢掌握队列的操作的实现方法➢学习使用栈解决实际问题的能力➢学习使用队列解决实际问题的能力实验容：1、利用栈结构实现八皇后问题。

2、八皇后问题19世纪著名的数学家高斯于1850年提出的。

他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。

请设计算法打印所有可能的摆放方法。

3、提示：1.可以使用递归或非递归两种方法实现2. 实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析2.1 存储结构存储结构：栈2.2 关键算法分析2.2.1皇后摆放位置可行性的判断判断任意两个皇后是否在同一行、同一列和同一斜线上for(int i=0;i<top;i++)if(queen[top]==queen[i]||(abs(queen[top]-queen[i]))==(top-i))return false;return true;1. 对于一个坐标，将前面每一行的皇后列标与本行的皇后列标比较，若列标相同或列标想减的绝对值与行标相减的值相同，返回false2. 否则i自增13. 列标i=8，即未发现冲突，循环完毕，返回true2．2．2插入皇后算法void SeqStack<T>::SetQueen(int r) // 设置皇后{for (int i=1;i<=StackSize;i++){Push(i);if (Feasible()){if (r<StackSize-1)SetQueen(r+1);else{Count++;Print();}}Pop();}}算法步骤：（1）判断列标在（0，8）围（2）将列标入栈（3）判断在该行列坐标下，皇后位置是否可行（4）若可行，判断插入列表所在行是否为最后一行，若是，打印列标；否则，开始下一行的皇后位置的选择。