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++) {。

⼋皇后问题（经典算法-回溯法）问题描述：⼋皇后问题（eight queens problem）是⼗九世纪著名的数学家⾼斯于1850年提出的。

问题是：在8×8的棋盘上摆放⼋个皇后，使其不能互相攻击。

即任意两个皇后都不能处于同⼀⾏、同⼀列或同⼀斜线上。

可以把⼋皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能互相攻击。

思路：使⽤回溯法依次假设皇后的位置，当第⼀个皇后确定后，寻找下⼀⾏的皇后位置，当满⾜左上、右上和正上⽅向⽆皇后，即矩阵中对应位置都为0，则可以确定皇后位置，依次判断下⼀⾏的皇后位置。

当到达第8⾏时，说明⼋个皇后安置完毕。

代码如下：#include<iostream>using namespace std;#define N 8int a[N][N];int count=0;//判断是否可放bool search(int r,int c){int i,j;//左上+正上for(i=r,j=c; i>=0 && j>=0; i--,j--){if(a[i][j] || a[i][c]){return false;}}//右上for(i=r,j=c; i>=0 && j<N; i--,j++){if(a[i][j]){return false;}}return true;}//输出void print(){for(int i=0;i<N;i++){for(int j=0;j<N;j++){cout<<a[i][j]<<" ";}cout<<endl;}}//回溯法查找适合的放法void queen(int r){if(r == 8){count++;cout<<"第"<<count<<"种放法\n";print();cout<<endl;return;}int i;for(i=0; i<N; i++){if(search(r,i)){a[r][i] = 1;queen(r+1);a[r][i] = 0;}}}//⼊⼝int main(){queen(0);cout<<"⼀共有"<<count<<"放法\n"; return 0;}。

计算机科学与技术专业数据结构课程设计报告设计题目：八皇后问题目录1需求分析 (2)1.1功能分析 (2)1.2设计平台 (3)2概要设计 (3)2.1算法描述 (4)2.2算法思想 (5)2.3数据类型的定义 (5)3详细设计和实现 (6)3.1算法流程图 (6)3.2 主程序 (6)3.3 回溯算法程序 (7)4调试与操作说明 (9)4.1调试情况 (9)4.2操作说明 (9)5设计总结 (11)参考文献 (12)附录 (12)1需求分析1.1功能分析八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。

高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。

在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。

所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。

现在我们已经知道八皇后问题有92个解答。

1、本演示程序中，利用选择进行。

程序运行后，首先要求用户选择模式，然后进入模式。

皇后个数设0<n<11。

选择皇后个数后，进入子菜单，菜单中有两个模式可以选择。

2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果显示在其后。

3、程序执行的命令包括：1）进入主菜单。

2）选择皇后问题，输入是几皇后。

3）进入子菜单。

4)选择皇后显示模式。

5）选择结束4、测试数据1）N的输入为4；2）共有2个解答。

3）分别是○●○○○○●○○○○●●○○○●○○○○○○●○○●○○●○○1.2设计平台Windows2000以上操作系统；Microsoft Visual C++ 6.02概要设计问题：N后问题问题描述：国际象棋中皇后可以攻击所在行，列，斜线上的每一个位置，按照此规则要在一个n*n的棋盘上放n个皇后使每一个皇后都不互相攻击问题分析：引入1个数组模拟棋盘上皇后的位置引入3个工作数组行数组[k]=1,表示第k行没有皇后右高左低数组[k]=1,表示第k条右高左低的斜线上没有皇后左高右低数组[k]=1,表示第k条左高右低的斜线上没有皇后观察棋盘找到规律同一右高左低的斜线上的方格，它们的行号和列号之和相等；同一左高右低的斜线上的方格，它们的行号和列号只差相等；开始时，所有行和斜线上都没有皇后，从第一列的第一行配置第一个皇后开始，在第m列的皇后位置数组[m]行放置了一个合理的皇后之后，准备考察第m+1列时，在数组行数组[]，右高左低数组[]，左高右低数组[]中为第m列，皇后位置数组[m]的位置设定有皇后标志如果按此放置位置得不到结果，则把当前列中的有皇后标记改为无皇后标记。

目录一需求分析 (1)1.1程序的功能： (1)1.2程序的输入输出要求： (1)二概要设计 (3)2.1程序的主要模块： (3)2.2程序涉及： (3)三详细设计 (3)3.1相关代码及算法 (4)3.1.1 定义相关的数据类型如下：....................... 错误!未定义书签。

3.1.2 主模块类C码算法： (4)3.1.3 画棋盘模块类C码算法 (5)3.1.4 画皇后模块类C码算法： (5)3.1.5 八皇后摆法模块（递归法）： (6)3.1.6 初始化模块 (7)3.1.7 输出摆放好的八皇后图形（动态演示）： (7)3.2相关流程图 (9)四调试分析 (12)五设计体会 (13)六附录 (13)七参考文献 (17)一需求分析1.1 程序功能：八皇后问题是一个古老而著名的问题。

该问题是十九世纪著名的数学家高斯1850年提出的。

八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法？并找出所有的摆法。

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

本程序通过对子函数void qu(int i)的调用，将八皇后的问题关键通过数据结构的思想予以了实现。

虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在横与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断。

即可完成。

如果在这个程序中，我们运用的是非递归的思想，那么将大量使用if等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。

如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。

这个程序，我运用到了数据结构中的栈、数组，以及树和回溯的方法。

八皇后问题代码实现/*代码解析*//* Code by Slyar */ #include &lt;stdio.h&gt;#include&lt;stdlib.h&gt; #define max 8 int queen[max], sum=0; /* max为棋盘最大坐标*/ void show() /* 输出所有皇后的坐标*/{ int i; for(i = 0; i &lt; max; i++){ printf("(%d,%d) ", i, queen[i]); }printf("\n"); sum++;} int check(int n) /* 检查当前列能否放置皇后*/{ int i; for(i = 0; i &lt; n; i++) /* 检查横排和对角线上是否可以放置皇后*/ { /* ///题目的要求是所有皇后不在同一横排、竖排、对角线上。

1、queen[n]值为竖排号，可看为Y轴上值。

n值为横排号，可看为X轴上值。

2、(1)先从横坐标第n点排开始放皇后，再放第n+1，所有不会同一横坐标点即同一竖排。

(2)queen[i] == queen[n]时即y坐标相等，即在同一横排，此时判断不合规则点。

(3)abs(queen[i] - queen[n]) == (n - i)，可变形为(queen[n] - queen[i]) /(n - i)==tan45°或tan135° 由公式可得出，点(n,queen[n])与点(i,quuen[i])在同一条左斜线135°或右斜45°，即国际象棋上的每个格子的两条斜角线。

3、由2即可得出当前格式是否能放置一个皇后。

*/ if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i)) { return1; } } return 0;} void put(int n) /* 回溯尝试皇后位置,n为横坐标*/{ int i; for(i = 0; i &lt; max;i++) { queen[n] = i; /* 将皇后摆到当前循环到的位置*/ if(!check(n)){ if(n == max - 1){ show(); /* 如果全部摆好，则输出所有皇后的坐标*/ } else { put(n + 1); /* 否则继续摆放下一个皇后*/ } } }} int main(){ put(0); /*从横坐标为0开始依次尝试*/ printf("TTTTTT----%d\n", sum); //system("pause"); //while(1); return 0;}/*算法系列---回溯算法引言寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。

数据结构课程设计报告八皇后问题设计任务书指导教师（签章）：年月日摘要：众所周知的八皇后问题是一个非常古老的问题，具体如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。

要求编写实现八皇后问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后问题的一个布局。

本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力。

在实践中培养独立分析问题和解决问题的作风和能力。

要求熟练运用C++语言、基本算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。

通过对题意的分析与计算，用递归法回溯法及枚举法解决八皇后是比较适合的。

递归是一种比较简单的且比较古老的算法。

回溯法是递归法的升华，在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

而枚举法，更是一种基础易懂简洁的方法。

把它们综合起来，就构成了今天的算法。

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

关键词：八皇后；递归法；回溯法；数组；枚举法…….目录1 课题综述…………………………………………………………………………………1.1 八皇后问题概述---------------------------------------------------1.2 预期目标---------------------------------------------------------1.3 八皇后问题课题要求-----------------------------------------------1.4 面对的问题-------------------------------------------------------2 需求分析…………………………………………………………………………………2.1 涉及到的知识基础--------------------------------------------------2.2 总体方案----------------------------------------------------------3 模块及算法设计……………………………………………………………………………………3.1 算法描述----------------------------------------------------------3.2．详细流程图-------------------------------------------------------4.代码编写…………………………………………………………………………5 程序调试分析……………………………………………………………………………………6 运行与测试……………………………………………………………………………………总结…………………………………………………………………………1 课题综述1.1 八皇后问题概述八皇后问题是一个古老而著名的问题。

八皇后问题的解决完整 Standardization of sany group #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#淮阴工学院数据结构课程设计报告设计题目：八皇后2008 年 6 月 25 日设计任务书摘要：八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。

关键词：八皇后 ; c++ ; 递归法目录.1. 课题综述1. 1课题的来源及意义八皇后问题是一个古老而着名的问题，该问题是十九世纪着名的数学家高斯1850年提出的。

在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。

所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。

到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。

运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。

1. 2 面对的问题1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；2）使用数据结构的知识，用递归法解决问题。

八皇后问题下面本人所用的就是回溯的思想来解决八皇后问题的。

8行8列的棋盘上放八个皇后，且不相互攻击，即每一列每一行只能放一个皇后，且必须要放一个皇后。

采用循环回溯的方法，现在第一列放一个皇后，然后再在第二列放一个皇后，以此类推，直到八个皇后都放完为止。

每个for循环语句都有一条continue语句，用来继续跳出本次循环。

// Queen.cpp(main)#include <iostream>using std::cout;using std::endl;#include <iomanip>using std::setw;#include <cmath>// using std::abs;int main(){static int queen[9];static int count=1;for (int A=1;A<=8;A++){for (int B=1;B<=8;B++){if (B==A){continue;}queen[2]=B;if ((abs(B-A))==1){continue;}queen[1]=A;for (int C=1;C<=8;C++){if ((C==B) || (C==A)){continue;}if ((abs(C-B)==1)||(abs(C-A)==2)) {continue;}queen[3]=C;for (int D=1;D<=8;D++){if ((D==C)||(D==B)||(D==A)){continue;}if ((abs(D-C)==1)||(abs(D-B)==2)||(abs(D-A)==3)){continue;}queen[4]=D;for (int E=1;E<=8;E++){if ((E==D)||(E==C)||(E==B)||(E==A)){continue;}if((abs(E-D)==1)||(abs(E-C)==2)||(abs(E-B)==3)||(abs(E-A)==4)){continue;}queen[5]=E;for (int F=1;F<=8;F++){if ((F==E)||(F==D)||(F==C)||(F==B)||(F==A)){continue;}if((abs(F-E)==1)||(abs(F-D)==2)||(abs(F-C)==3)||(abs(F-B)==4)||(abs(F-A)==5)){continue;}queen[6]=F;for (int G=1;G<=8;G++){if((G==F)||(G==E)||(G==D)||(G==C)||(G==B)||(G==A)){continue;}if((abs(G-F)==1)||(abs(G-E)==2)||(abs(G-D)==3)||(abs(G-C)==4)||(abs(G-B)==5)||(abs(G-A)==6)){continue;}queen[7]=G;for (int I=1;I<=8;I++){if((I==G)||(I==F)||(I==E)||(I==D)||(I==C)||(I==B)||(I==A)){continue;}if((abs(I-G)==1)||(abs(I-F)==2)||(abs(I-E)==3)||(abs(I-D)==4)||(abs(I-C)==5)||(abs(I-B)==6)||(abs(I-A)==7)){continue;}queen[8]=I;cout<<" NO."<<setw(2)<<count<<": ";for (int i=1;i<=8;i++){cout<<setw(3)<<queen[i];}count++;cout<<endl;}}}}}}}}return 0;}运行结果如下：。

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语⾔回溯法解⼋皇后问题的⽂章就介绍到这了。

Standardization ofsany group #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#■ •・・WAS 1 ■ ■ ■数据结构课程设计报告设计题目： __________ 八皇后_______________________________________2008 年6 月25 日设计任务书指导教师（签章）：2008 年6 月30 日摘要:八皇后问题要求在一个8 * 8的棋盘上放上8个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击.按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子.因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

而本课程设计本人的目的也是通过用C++语言平台将一个8 * 8的棋盘上放上8个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现.使用递归方法最终将其问题变得一目了然，更加易懂。

关键词：八皇后；C++ ;递归法1.课题综述1.1课题的来源及意义八皇后问题是一个古老而着名的问题，该问题是十九世纪着名的数学家高斯1850年提出的。

在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。

所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。

到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。

运用所学计算机知识来试着解决这个问题是个锻炼和提高我白己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。

1.2面对的问题1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态;2）使用数据结构的知识，用递归法解决问题。