数据结构课程设计报告-8皇后问题

数据结构课程设计

选题： 八皇后问题

姓 名： 学 号： 指导老师：

目 录

一.选题概---------------------------------------3

1

述

二.设计要求与分--------------------------------3

三.数据

结

构

与

定

--------------------------------4

1.结构体定义

2.函数定义 3.函数之间的定义

四.程序

段

与

分

----------------------------------5

五.完整程序代码及运行结果截------------------7 六.心得

体

--------------------------------------10

七.参

考

文

--------------------------------------10

析

义

析

图会

献

2

一．选题概述：

在实际应用中，有相当一类问题需要找出它的解集合，或者要求找出某些约束条件下的最优解。求解时经常使用一种称为回溯的方法来解决。所谓回溯就是走回头路，该方法是在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择通路继续搜索。为了能够沿着原路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶的状态即为回退的第一站，因此回溯法均可利用栈来实现。而解决八皇后问题就是利用回溯法和栈来实现的。 二．设计要求与分析

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

八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等于232种，但是，可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行上。这样在放置第i个皇后时，只要考虑它与前i一1个皇后处于不同列和不同对角线位置上即可。因此，其算法基本思想如下：

从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2，?，8列进行试探，并尽可能取小的列数。若当前试探的列位置

3

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

（1)置当前行当前列均为1; （2）while(当前行号《8)

（3）｛检查当前行，从当前列起逐列试探，寻找安全列号； （4）if（找到安全列号）

（5）放置皇后，将列号记入栈中，并将下一行置成当前行，第1列置为当前列； （6）else

（7）退栈回溯到上一行，移去该行已放置的皇后，以该皇后所在列的下一列作为 当前列； （8）｝结束程序。

三．数据结构与定义

1.结构体定义

typedef struct {

int col[MaxSize]; //col[i]存放第i个皇后的列号 int top; //栈顶指针 }Type;

4

2.函数定义

bool place(Type st,int i,int j) //测试(i,j)是否与1~i-1皇后有冲突 void queen(int n) //求解皇后问题 void main() //主函数

3.函数之间的调用关系

main queen place

四．程序块与分析

bool place(Type st,int i,int j)//测试(i,j)是否与1~i-1皇后有冲突 {

int k=1;

if(i==1) return true;//存放第一个皇后时没有冲突 while(k<=i-1)//j=1到k-1是已经放置了皇后的列 {

if((st.col[k]==j)||(abs(j-st.col[k])==abs(k-i))) return false; k++; }

return true; }

（k，st.col[k]） （k，st.col[k]）

j-st.col[k] j-st.col[k] (i,j) i-k i-k (i,j)

5

//测试(i,j)位置是否与已经放好的第1个到第i~1皇后有冲突。已经放置好的第1个到第1~i-1 个皇后已放置在st栈中。St栈用的是顺序栈，栈顶指针从1开始，st.col[k]用于存放第k（1<=i<=k-1）个皇后的列号，即皇后的位置是（k,st.col[k]）。对于（i，j）位置上的皇后与已经放置的皇后（k，st.col[k]）发生冲突的情况时，则有：st.col[k]==j;对角线的冲突情况是：|j-st.col[k]|==|k-i|。

void queen(int n)//求解n皇后问题 {

int i,j,k; bool find;

Type st;//定义栈st

st.top=0;//初始化栈顶指针 st.top++;//将(1,1)放进栈 st.col[st.top]=1;

while(st.top>0)//栈不空时循环 {

i=st.top;//当前皇后为第i个皇后

if(st.top==n)//所有皇后都放置好了，输出一个解 {

printf(\第%d个解：\ for(k=1;k<=st.top;k++)

printf(\ printf(\ }

find=false;

for(j=1;j<=n;j++) {

if(place(st,i+1,j))//在i+1行找到一个放置皇后的位置(i+1,j) {

st.top++;

st.col[st.top]=j; find=true; break; }

}

if(find==false)//在i+1行找不到放皇后的位置，回溯

6

{

while(st.top>0) {

if(st.col[st.top]==n)//本行也没有可放的位置，则退栈 st.top--;

for(j=st.col[st.top]+1;j<=n;j++)//在本行的下一个位置找 if(place(st,st.top,j)) {

st.col[st.top]=j;

break; }

if(j>n)//当前皇后在本行没有可放的位置 st.top--;//退栈

else//本行找到一个位置后，推出回溯 break; } } } }

void main() //主函数 {

int n;

printf(\请输入皇后个数n=\ scanf(\

printf(\皇后问题求解如下:\\n\ queen(n); printf(\}

五.完整程序代码及运行结果截图

7

#include #include #define MaxSize 100 typedef struct {

int col[MaxSize];//col[i]存放第i个皇后的列号 int top;//栈顶指针 }StType;//定义顺序栈类型 int count=0;

bool place(StType st,int i,int j)//测试(i,j)是否与1~i-1皇后有冲突 {

int k=1;

if(i==1) return true;//存放第一个皇后时没有冲突 while(k<=i-1)//j=1到k-1是已经放置了皇后的列 {

if((st.col[k]==j)||(abs(j-st.col[k])==abs(k-i))) return false; k++; }

return true; }

void queen(int n)//求解n皇后问题 {

int i,j,k; bool find;

StType st;//定义栈st

st.top=0;//初始化栈顶指针 st.top++;//将(1,1)放进栈 st.col[st.top]=1;

while(st.top>0)//栈不空时循环 {

i=st.top;//当前皇后为第i个皇后

if(st.top==n)//所有皇后都放置好了，输出一个解 {

printf(\第%d个解：\ for(k=1;k<=st.top;k++)

printf(\ printf(\ }

find=false;

for(j=1;j<=n;j++)

if(place(st,i+1,j))//在i+1行找到一个放置皇后的位置(i+1,j) {

8

st.top++;

st.col[st.top]=j; find=true; break; }

if(find==false)//在i+1行找不到放皇后的位置，回溯 {

while(st.top>0) {

if(st.col[st.top]==n)//本行也没有可放的位置，则退栈 st.top--;

for(j=st.col[st.top]+1;j<=n;j++)//在本行的下一个位置找 if(place(st,st.top,j)) {

st.col[st.top]=j; break; }

if(j>n)//当前皇后在本行没有可放的位置 st.top--;//退栈

else//本行找到一个位置后，推出回溯 break; } } } }

void main() {

int n;

printf(\请输入皇后个数n=\ scanf(\

printf(\皇后问题求解如下:\\n\ queen(n); printf(\}

9

六.心得体会

1.善于学习别人,多请教牛人,才会更快提高自己。有些问题也许就是自己在某一点想不通，想法转不过来，这就消耗了很多时间。而经过牛人的点拨问题就解决了，牛人们也会更直接，更清晰的教导一些技术，通过向他们学习，才会更快的提高自己的技能。

2.多找一些题目来练习，多敲代码，才会更有感觉。在练习的过程中找出规则，形成编程思想。

3.小组合作形成共同进步。小组成员的讨论过程中，将各自的想法提出来，分析优缺点，这过程中每个成员也可以学习到其他成员的解题思想，也可以审视自己的解题思想，获得提升。

七.参考文献

1.数据结构（C语言版）严蔚敏，吴伟民 清华大学出版社 2.C语言程序设计 何钦铭，颜晖 高等教育出版社 3.数据结构教程 李春葆 清华大学出版社

10

本文来源：https://www.bwwdw.com/article/r9pd.html