数据结构实验报告八皇后问题

数据结构与算法专题实验实验报告_八皇后_背包问题的求解_农夫过河实验报告：数据结构与算法专题实验报告实验题目：八皇后问题的求解与背包问题的求解实验目的：1. 掌握八皇后问题的求解方法，了解回溯算法的应用。

2. 掌握背包问题的求解方法，了解动态规划算法的应用。

3. 进一步理解数据结构与算法的基本概念和应用。

实验内容：1. 八皇后问题的求解八皇后问题是一个经典的递归与回溯算法问题，要求在一个8×8的棋盘上放置8个皇后，使得任意两个皇后不在同一行、同一列或同一斜线上。

具体求解步骤如下：a. 定义一个8×8的二维数组作为棋盘，初始化所有元素为0。

b. 从第一行开始，依次尝试在每一列放置皇后。

c. 对于每一列，判断当前位置是否与已经放置的皇后冲突。

如果冲突，则回溯到上一行，重新选择位置；否则，继续放置下一行的皇后。

d. 当放置完所有皇后时，输出结果。

2. 背包问题的求解背包问题是一个经典的动态规划算法问题，要求在给定的一组物品中选择一些物品放入背包，使得背包的总重量最大，但不能超过背包的承重量。

具体求解步骤如下：a. 定义一个二维数组dp，其中dp[i][j]表示在前i个物品中选择，背包容量为j时的最大重量。

b. 初始化dp数组的第一行和第一列为0，表示背包容量为0时和没有物品可选时的最大重量都为0。

c. 对于每个物品，分两种情况讨论：- 如果当前物品的重量大于背包的容量，则无法选择该物品，直接继承前i-1个物品的最大重量，即dp[i][j] = dp[i-1][j]；- 如果当前物品的重量小于等于背包的容量，则可以选择该物品或不选择该物品。

选择该物品时，背包的总重量为dp[i-1][j-w[i]] + v[i]，不选择该物品时，背包的总重量为dp[i-1][j]。

取两者中的较大值作为dp[i][j]的值。

d. 最终，dp[n][m]即为所求的最大重量，其中n为物品的个数，m为背包的承重量。

八皇后实验报告八皇后实验报告引言：八皇后问题是一个经典的数学问题，它要求在一个8x8的国际象棋棋盘上放置8个皇后，使得任意两个皇后都不会互相攻击。

这个问题看似简单，但实际上却充满了挑战。

在本次实验中，我们将探索八皇后问题的解法，并通过编写算法来解决这个问题。

一、问题背景：八皇后问题最早由数学家马克斯·贝瑟尔于1848年提出，它是一道经典的递归问题。

在国际象棋中，皇后可以在同一行、同一列或同一对角线上进行攻击，因此我们需要找到一种方法，使得8个皇后彼此之间不会相互攻击。

二、解决方法：为了解决八皇后问题，我们可以使用回溯法。

回溯法是一种穷举搜索的方法，它通过逐步尝试所有可能的解决方案，直到找到符合要求的解。

具体步骤如下：1. 初始化一个8x8的棋盘，并将所有格子标记为无皇后。

2. 从第一行开始，依次尝试在每一列放置一个皇后。

3. 在每一列中，检查当前位置是否符合要求，即与已放置的皇后不在同一行、同一列或同一对角线上。

4. 如果当前位置符合要求，将皇后放置在该位置，并进入下一行。

5. 如果当前位置不符合要求，尝试在下一列放置皇后。

6. 重复步骤3-5，直到找到一个解或者所有可能的位置都已尝试过。

7. 如果找到一个解，将其输出；否则，回溯到上一行，继续尝试下一列的位置。

三、编写算法：基于上述步骤，我们可以编写一个递归函数来解决八皇后问题。

伪代码如下所示：```function solveQueens(board, row):if row == 8:print(board) # 打印解returnfor col in range(8):if isSafe(board, row, col):board[row][col] = 1solveQueens(board, row + 1)board[row][col] = 0function isSafe(board, row, col):for i in range(row):if board[i][col] == 1:return Falseif col - (row - i) >= 0 and board[i][col - (row - i)] == 1:return Falseif col + (row - i) < 8 and board[i][col + (row - i)] == 1:return Falsereturn Trueboard = [[0]*8 for _ in range(8)]solveQueens(board, 0)```四、实验结果：通过运行上述算法，我们得到了八皇后问题的所有解。

数据结构实验报告实验名称：实验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. 程序运行结果程序实现八皇后问题：经过测试，程序运行良好，无明显错误。

数据结构课程设计报告设计题目：八皇后问题系（院）:数学学院专业：信息与计算科学班级：02班学生姓名王天宇学号:指导教师:设计任务书1. 课题综述1. 1课题的来源及意义八皇后问题是一个古老而着名的问题，该问题是十九世纪着名的数学家高斯1850年提出的。

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

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

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

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

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

2概要设计本课件学生是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。

在这个程序中，我的主要思路以及思想是这样的：1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；对角线：对角线有两个方向。

在这我把这两条对角线称为：主对角线和从对角线。

在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。

因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。

数据结构实验报告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]='#';说明：已放置皇后的行、列以及对角线都不能再放置皇后。

数据结构作业报告——八皇后姓名：李慧卓班级：071121班学号：07112012上机时间：2012-12-17报告时间：2013-01-05摘要1.实验目的熟悉树中回溯法与树的遍历。

2.实验方法本程序利用if函数中的条件判断，辅之循环，按要求摆放棋子。

总共有3个子函数，分别为显示结果函数，检查合法函数，置棋函数。

3.实验结果运行结果显示了符合规则的所有摆放八皇后的方法。

内容一．问题重述在8*8的棋盘上，摆放八个皇后，是之不能相互攻击，即任意两个棋子不在同一列、行、斜线上。

显示所有摆法。

二．算法描述四．函数与思路说明本函数运用了条件语句，其中最重要的判断是否合法即用if条件判断实现。

运用树的概念进行列举而后判断。

本程序总共有3子函数，1个主函数，其中3个子函数分别为show_result（）子函数，check_cross ()子函数，put_chess ()子函数。

五．程序执行结果六．结论参考列子，在根据实际情况调整编改，运行成功。

七．编程中遇到的问题以及解决方法参考网范例发现函数构成比较简单。

修改了头文件对getch（），puts()进行了了解。

八．附录#include "stdafx.h"#include <stdio.h>#include <conio.h> //配合getch()使用#include <math.h>#define MAX 8 /*棋子数及棋盘大小MAX*MAX*/int board[MAX];void show_result(){int i;for(i=0;i<MAX;i++)printf("(%d,%d)",i,board[i]);printf("\n");}/*检查在同一直线上是否有其他的棋子*/int check_cross(int n){int i;for(i=0;i<n;i++) //i小于n,只需与之前的比较{if(((board[i])==(board[n]))||((n-i)==abs((board[i])-(board[n])))) return 1;}return 0;}/*放棋子到棋盘上*/void put_chess(int n){int i;for(i=0;i<MAX;i++){board[n]=i;if(!check_cross(n)){if(n==MAX-1)show_result();/*找到其中一种方法打印出结果*/elseput_chess(n+1);}}}void main(){puts("The possible placements are:");put_chess(0);puts("\nPress any key to quit ...");getch(); ///利用它来实现程序运行完了暂停不退出的效果。

数据结构实验报告实验名称：实验二——利用栈结构实现八皇后问题学生：班级：班序号：学号：日期：实验要求实验目的：通过选择下面五个题目之一进行实现，掌握如下容：➢进一步掌握指针、模板类、异常处理的使用➢掌握栈的操作的实现方法➢掌握队列的操作的实现方法➢学习使用栈解决实际问题的能力➢学习使用队列解决实际问题的能力实验容：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）若可行，判断插入列表所在行是否为最后一行，若是，打印列标；否则，开始下一行的皇后位置的选择。

数据结构课程设计报告八皇后问题班级：***姓名：***学号：***八皇后问题1、问题分析八皇后问题是一个古老而著名的问题。

该问题是十九世纪著名的数学家高斯1850提出；在8X＜的国际象棋上摆放八皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有76种方案。

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

八皇后问题是在8*8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。

八皇后在棋盘上分布的各种可能的格局，其数非常大，但是可以将一些明显不满足问题要求的格局排除掉。

由于任何两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行。

这样在放置第i个皇后时，只要考虑它与前i-1个皇后处于不同列和不同对角线位置上即可。

2、算法描述从第一行起逐行放置皇后，每放置一个皇后均需要依次对第1, 2・3列进行试探，并尽可能取小的列数。

若当前试探的列位置是安全的，即不与已经放置的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列去试探，当8列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然后继续试探。

该算法抽象的描述如下：(1) 置当前行当前列均为1;(2) While (当前行号v = 8);(3) {检查当前行，从当前列起逐列试探，寻找安全列号；(4) if (找到安全列号)(5) 放置皇后，将列号放入栈中，并将下一行置为当前行，第1列置为当前列；(6) else(7) 退栈回溯到上一行，移去该行已经放置的皇后，已该皇后所在列的下一列作为当前列；(8) }2. 1算法求精要对上述抽象算法进行逐步求精，就需要确定相应的存储结构和有关的数据类型。

八皇后问题一．八皇后问题简述:在8*8的国际象棋棋盘上放置8个皇后，使任意两个皇后不能互相攻击，即任何行任何列或对角线（与水平轴的夹角为45°或135°的斜线）上不得有两个或两个以上的皇后，这样的一个格局称为问题的一个解。

请求八皇后问题的算法。

二．解决思路：先声明我们根据条件可以知道皇后肯定是每行都有且只有一个所以我们创建一个数组x[t]让数组角标表示八皇后的行，用这个角标对应的数组值来确定这个皇后在这行的那一列。

我们用递归来做：这问题要求皇后所在的位置必须和其他皇后的位置不在同一行、列还有把两个皇后看成点其|斜率|=1；所以我们就要写这个限定条件用一个函数来实现：函数内对每一个已经放好的皇后的位置进行判断，所以就要有个循环。

我们既然是用递归来解决问题那就要把这个问题分成一个个相同的小问题来实现。

不难发现我们要在8*8的方格里放好8个皇后那我们就要知道在8（列）*7（行）是怎么放的在有我们事先写好的判断函数放好最后行就搞定了；以此类推我们要知道8*7的怎么方的我们就要知道8*6是怎么样的就好了，所以我们是以一行怎么放作为一个单元。

我们就去建一个可以放好一行的函数backtrack（int t）里面的t表示是第几行，在main函数调用的时候第一次传进来的是0也就是从第一行开始判断。

我们就开始写函数体了：每一行有8个位置可以放，每一个位置我们都要去判断一下所以我们就用循环来搞定。

在这个循环里面我们让x[t]=i也就是从这一行的第一个开始判断。

放好后就要去判断是否符合条件。

如果符合条件我们就在调用这个函数本身backtrack 不过传进去的参数是t+1也就是下一行的意思。

在进行判断下一行之前我们要判断一下t是不是等于8也就是已经是最后一行了，如果是最后一行了我们就可以将其进行输出。

打印8*8的矩阵（提示在写一个函数）皇后的位置用1表示出来没有的用0表示。

三．代码与注解：#include <math.h>#include <stdio.h>#include <time.h>#include<string.h>#include<conio.h> //用getch()要调用的头文件#include <stdlib.h> //要用system函数要调用的头文件int SUM=0; //统计有多少种可能int shezhi(){ //设置为N皇后问题int N;printf("这是一个N皇后问题...\n请输入N=");scanf("%d",&N);return N;}void Print(int N,int x[]) //印出結果{int MAX=N;for(int i=0;i<MAX;i++){for(int j=0;j<MAX;j++)if(j==x[i])printf("@");elseprintf("*");printf("\n");}SUM++; //打印一种情况统计一次printf("\n");}int Judge(int k,int x[]) //判断是否在同一直、橫、斜线上有其它棋子{int i;for(i=0;i<k;i++)if( abs(k-i)==abs(x[i]-x[k]) || x[i]==x[k] ) //函数名: abs; 功能: 求整数的绝对值 ;return 0;return 1;}void backtrack(int t,int N,int x[]) // 把棋子放到棋盘上{ int MAX=N;int i;for(i=0;i<MAX;i++){x[t]=i;if(Judge(t,x)){if(t==MAX-1){Print(MAX,x); // 找到其中一种放法，印出結果}else backtrack(t+1,N,x);}}}void Introduce(){printf("1.设置为N皇后问题。

八皇后实验报告八皇后实验报告导言：八皇后问题是一个经典的数学问题，最早由西班牙的数学家马克斯·贝恩在1848年提出。

问题的目标是在一个8×8的棋盘上，放置8个皇后，使得它们互相之间无法攻击到对方。

本次实验旨在通过编程的方式求解八皇后问题，并分析解的个数和解的特点。

一、问题描述八皇后问题可以简化为在一个8×8的棋盘上放置8个皇后，使得任意两个皇后都不在同一行、同一列或同一斜线上。

这意味着每一行和每一列最多只能有一个皇后。

二、算法设计为了求解八皇后问题，我们采用了回溯算法。

回溯算法是一种通过逐步试错的方式来寻找问题解的方法。

具体的算法步骤如下：1. 从棋盘的第一行开始，依次尝试在每一列放置一个皇后。

2. 在放置一个皇后后，检查是否满足任意两个皇后都不在同一行、同一列或同一斜线上的条件。

3. 如果满足条件，则继续到下一行放置皇后；如果不满足条件，则回溯到上一行重新选择位置。

4. 当最后一行的皇后放置完毕后，即找到了一个解，记录下来。

5. 继续回溯，寻找下一个解，直到所有解都找到为止。

三、实验结果通过编程实现了八皇后问题的求解算法，并运行了多组实验。

实验结果如下：1. 解的个数在8×8的棋盘上，共有92个不同的解。

每个解都代表了一种放置皇后的方式，使得它们互不攻击到对方。

2. 解的特点(1) 对称性：在所有的解中，有一半解是对称的。

即如果一个解是对称的，那么它的镜像解也是一个合法解。

(2) 旋转性：每个解可以通过旋转得到其他的合法解。

例如，一个解可以通过将整个棋盘顺时针旋转90度得到另一个解。

(3) 反射性：每个解可以通过水平或垂直翻转得到其他的合法解。

例如，一个解可以通过将整个棋盘水平翻转得到另一个解。

(4) 解的数量：解的数量随着棋盘大小的增加而急剧增加。

在8×8的棋盘上有92个解，而在9×9的棋盘上有352个解。

四、讨论与总结八皇后问题是一个非常经典的数学问题，通过本次实验我们可以得出以下结论：1. 回溯算法是求解八皇后问题的有效方法，可以找到所有的解。

(2023)八皇后问题实验报告(一)实验背景八皇后问题，是一道经典的数学问题，简要地说：在一个 8x8 的国际象棋棋盘上摆放 8 个皇后，使其不能互相攻击。

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

实验目的1.理解并掌握八皇后问题的基础算法；2.利用Python编写程序，解决八皇后问题；3.掌握递归算法与回溯算法的基本思想；4.分析算法时间复杂度，理解优化算法的重要性。

实验步骤1.利用递归算法，枚举每一行中皇后的位置；2.每一行都有8个候选位置，依次尝试每个位置是否可行；3.如果某个位置可行，继续对下一行进行递归；4.如果都不可行，则回溯到上一行，重新选择位置；5.直到第8行所有位置都选择完成，输出结果。

程序实现及结果def conflict(pos, i):for j in range(i):if abs(pos[i] - pos[j]) in (0, i - j):return Truereturn Falsedef queen(num =8, pos = ()):for i in range(num):if not conflict(pos, i):if len(pos) == num -1:yield (i, )else:for result in queen(num, pos + (i, )):yield (i, ) + resultfor solution in list(queen(8)):print(solution)程序输出结果为所有可能的八皇后问题解决方案，共计92种：(0, 4, 7, 5, 2, 6, 1, 3)(0, 5, 7, 2, 6, 3, 1, 4)…(7, 3, 0, 2, 5, 1, 6, 4)(7, 4, 2, 0, 6, 1, 3, 5)结论与分析1.通过本实验，我们深入地理解了递归算法与回溯算法的基本思想，并将其应用到八皇后问题的解决中；2.程序的输出结果表明：八皇后问题有92种可能的解决方案；3.根据算法的时间复杂度分析，当八皇后问题的规模更大时，应该采用更高效的算法进行优化；4.进一步研究表明，通过基因算法等优化算法可以提高八皇后问题的解决效率。

数据结构实验报告——八皇后问题实验目的:熟练掌握栈操作的基本算法实现。

实现功能:利用回溯法和栈来实现八皇后问题：在8×8的国际象棋棋盘上, 安放8个皇后, 要求没有一个皇后能够“吃掉”任何其他一个皇后, 即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一对角线。

设计思路:数据结构:enum boolean { false , true }enum boolean a[9] , b[17] , c[17] ;//检查皇后之间是否冲突//皇后位置安全性可用逻辑表达式: a[ j ] && b[ i+j ] && c[ i-j+9 ]int s[9];//s[1..8]表示顺序栈, 栈的下标值表示皇后所在的行号, 栈的内容是皇后所在的列号。

该算法抽象描述如下:置当前行当前列均为1；while(当前行号≤8){ 检查当前行, 从当前列起逐列试探, 寻找安全列号；if ( 找到安全列号)放置皇后, 将列号记入栈中, 并将下一行置成当前行, 第一列置为当前列；else退栈回溯到上一行, 移去该行已放置的皇后, 以该皇后所在列的下一列作为当前列；} 结束程序。

程序流程图:源程序：#include<stdio.h>enum boolean {FALSE,TRUE}; //声明全局变量enum boolean a[9],b[17],c[17];int s[9];int num=0;//函数声明void print();void movequeen();void eightqueen();void main(){ //主函数eightqueen();printf("共有%d种解法\n",num);}void print() //输出函数{int k;printf("\n");printf("NO.%d\n",++num);printf("行号: 1 2 3 4 5 6 7 8\n");printf("列号:");for(k=1;k<=8;k++)printf("%3d",s[k]);printf("\n");}void movequeen(int i,int j){a[j]=TRUE;b[i+j]=TRUE;c[i-j+9]=TRUE;}void eightqueen()//算法函数{int i,j;for(i=2;i<=16;i++){if(i>=2&&i<=9)a[i-1]=TRUE;b[i]=TRUE;c[i]=TRUE;}i=1;j=1;while(i>=1){while(j<=8){if(a[j]&&b[i+j]&&c[i-j+9])break;j++;}if(j<=8){a[j]=FALSE;b[i+j]=FALSE;c[i-j+9]=FALSE;s[i]=j;if(i==8){num++；print();movequeen(i,j);i--;j=s[i];movequeen(i,j);j++;}else {i++;j=1;}}else{i--;if(i>=1){j=s[i];movequeen(i,j)；j++;}}}}实验心得:通过本次实验大大的提高了我个人的动手能力, 对VC编程更加的熟练, 这个程序也一定程度的锻炼了我的思考能力, 对于八皇后问题的逻辑编排, 全局处理, 细节完善等方面都有一个深刻的认识。

数据结构课程设计报告八皇后问题设计任务书课题名称八皇后设计目的1.调研并熟悉八皇后的基本功能、数据流程与工作规程；2.学习八皇后相关的算法和基于VC++集成环境的编程技术；3.通过实际编程加深对基础知识的理解，提高实践能力；4.学习开发资料的收集与整理，学会撰写课程设计报告。

实验环境1.微型电子计算机（PC）；2.安装Windows 2000以上操作系统，Visual C++6.0开发工具。

任务要求1.利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设计要求，注意材料收集与整理；2.在第16周末之前完成预设计，并请指导教师审查，通过后方可进行下一步工作；3.本课题要求至少用三种方法解决八皇后问题，输入棋盘的阶层，然后显示共有多少种布局方案，并显示每一种方案的具体情况。

4.结束后，及时提交设计报告（含纸质稿、电子稿），要求格式规范、内容完整、结论正确，正文字数不少于3000字（不含代码）。

工作进度计划序号起止日期工作内容1 2009.06.7~2009.06.7 在预设计的基础上，进一步查阅资料，完善设计方案，形成书面材料。

22009.06.7~2009.06.10设计总体方案，构建、绘制流程框图，编写代码，上机调试。

3 2009.06.11~2009.06.12测试程序，优化代码，增强功能，撰写设计报告。

4 2009.06.12~2009.06.13提交软件代码、设计报告，参加答辩，根据教师反馈意见，修改、完善设计报告。

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

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

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

实验项目:八皇后问题1•实验目的：通过求解皇后问题，熟悉深度优先搜索法DFS (回溯法(Backtracking Algorithms)技术。

2•实验内容：由n2个方块排成n行n列的正方形称为n元棋盘。

如果两个皇后位于n元棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。

现要找出使棋盘上n 个皇后互不攻击的布局。

编制程序解决上述问题，以n=6运行程序，输出结果。

3•程序简介：将n个皇后放到一个n*n的方阵中，要求每个皇后不在同一行同一列及同一对角线，我的程序是先把每个皇后放在了第零列，然后再按行检查，不符合要求继续下一列，若已经到这一行的最后一列，还没找到符合要求的位置，则回到上一行。

4•算法设计介绍：定义一个一维数组，数组的下标是皇后所在位置的行数，数组存的值是皇后所在位置的列数，现将A[0]-A[n-l]都赋成零，然后随着检查的进行，皇后的位置也在不断地变化，最后找到一个符合要求的方阵时，本质上就是一个存放整数的一维数组，数组的下标是行数，存放的值是列数。

5•困难及解答我很久以前就听说过八皇后问题，没想到现在轮到自己编了，一开始还真是特别糊涂呢，后来老师上课把算法大概讲了一遍，就清楚很多了，要说问题，就是一开始纠结怎么存放皇后，我开始想用二维数组着，后来老师说用一维数组比较好做，我看了一下老师的算法，就明白了大概，经过一段时间就编出来了5•心得我编程变得还是很少，天天下决心说以后多编，也没践行，心想着吧，不挂在嘴上了，努力！6•程序清单/*〃我真诚地保证：〃我独立完成了整个程序从分析、设计到编码的所有工作。

〃如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中〃详细地列举我所遇到的问题，以及别人给我的提示。

〃我的程序里中凡是引用到其他程序或文档之处，〃例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段，〃我都已经在程序的注释里很清楚地注明了引用的出处。

〃我从未没抄袭过别人的程序，也没有盗用别人的程序，〃不管是修改式的抄袭还是原封不动的抄袭。