八皇后问题地解决完整文档

淮阴工学院

数据结构课程设计报告设计题目：八皇后

2008 年 6 月25 日

设计任务书

课题

名称

八皇后

设计目的1.用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既

攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．

2.通过这次课程设计,提高自己的编程能力,熟悉c++的编程坏境,为以后的程

序开发打下基础.

实验环境1）系统要求：win98以上操作系统；2）语言平台：tc++或vc++6.0；3）执行文件：八皇后.exe

任务要求试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。

工作进度计划

序号起止日期工作内容

1 2008.6.23~2008.6.24查阅相关内容

2 2008.6.24~2008.6.25编写代码及实习报告

3 2008.6.25~2008.6.26完善课程设计报告

4 2008.6.26~2008.6.27答辩

指导教师（签章）：

2008 年 6 月30 日

摘要：

八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

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

关键词：八皇后; c++; 递归法

目录

1. 课题综述 (1)

1.1课题的来源及意义 (1)

1.2面对的问题 (1)

2. 需求分析 (1)

2.1涉及到的知识 (1)

2.2软硬件的需求 (1)

2.3功能需求 (2)

3. 概要设计 (2)

4. 详细设计和实现 (2)

4.1算法描述及详细流程图 (2)

4.1.1算法描述 (3)

4.1.2算法流程图 (3)

5. 代码编写及详细注释 (4)

6. 程序调试 (7)

6.1调试过程、步骤及遇到的问题 (7)

7. 运行与测试 (7)

7.1运行演示 (7)

总结 (9)

致谢 (10)

参考文献 (11)

.

1. 课题综述

1. 1课题的来源及意义

八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。

在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。

到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。

1. 2 面对的问题

1）解决冲突问题：

这个问题包括了行，列，两条对角线；

列：规定每一列放一个皇后，不会造成列上的冲突；

行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；

2）使用数据结构的知识，用递归法解决问题。

2. 需求分析

2. 1 涉及到的知识

本次课程设计中，用到的主要知识有：递归法的运用，for语句的灵活运用，数据结构中树知识的灵活运用、栈及数组的掌握。

2. 2 软硬件的需求

1）系统要求：win98以上操作系统；

2) 语言平台：tc++或vc++6.0；

2. 3 功能需求

当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比较直观的界面显示。

3. 概要设计

本课件学生是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。在这个程序中，我的主要思路以及思想是这样的：1）解决冲突问题：

这个问题包括了行，列，两条对角线；

列：规定每一列放一个皇后，不会造成列上的冲突；

行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；

对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。

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

2）数据结构的实现

而对于数据结构的实现，学生则是着重于:

数组a[I]：a [I]表示第I个皇后放置的列；I的范围：1..8;

对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后；

4. 详细设计和实现

4. 1 算法描述及详细流程图

4.1.1 算法描述

A、数据初始化。

B、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（n，m）是否等于0（未被占领）。如果是，摆放第n个皇后，并宣布占领（记得姚横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n<=8，m=8时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。

C、使用数组实现回溯法的思想。

D、当n>8时，便打印出结果。

E、输出函数我使用printf输出，运行形式为：第m种方法为：* * * * * * * *

4.1.2 算法流程图

5. 代码编写及详细注释

#include

#include

#include

#include

#include

#define QUEENS 8

int iCount = 0; //!记录解的序号的全局变量。

int Site[QUEENS]; //!记录皇后在各行上的放置位置的全局数组。

void Queen(int n); //!递归求解的函数。

void Output();//!输出一个解。

int IsValid(int n);

//!判断第n个皇后放上去之后，是否有〉冲突。

void main() /*----------------------------Main：主函数。----------------------------*/

{ system("title 叶青--递归算法八皇后问题 ");

cout<<" "<<"八皇后的解法："<

cout<<" "<<"-------------------------------------"<

Queen(0); //!从第0行开始递归试探。

getch();//!按任意键返回。

}

void Queen(int n) /*-----------------Queen：递归放置第n个皇后，程序的核心!----------------*/

{ int i;

if(n == QUEENS) //!参数n从0开始，等于8时便试出了一个解，将它输出并回溯。

{ Output(); return; }

for(i = 1 ; i <= QUEENS ; i++) //!n还没到8，在第n行的各个行上依次试探。

{ Site[n] = i; //!在该行的第i行上放置皇后。

if(IsValid(n)) //!如果放置没有冲突，就开始下一行的试探。

Queen(n + 1); }}

int IsValid(int n) /*------IsValid：判断第n个皇后放上去之后，是否合法，即是否无冲突。------*/

{ int i;

for(i = 0 ; i < n ; i++) //!将第n个皇后的位置依次于前面n－1个皇后的位置比较。

{ if(Site[i] == Site[n]) //!两个皇后在同一列上，返回0。

return 0;

if(abs(Site[i] - Site[n]) == (n - i)) //!两个皇后在同一对角线上，返回0。

return 0; }

return 1; //!没有冲突，返回1。

}

void Output()/*------------Output：输出一个解，即一种没有冲突的放置方案。------------*/

{

int i;

printf("No.%-5d" , ++iCount); //!输出序号。

for(i = 0 ; i < QUEENS ; i++)//!依次输出各个行上的皇后的位置，即所在的列数。

printf("%d " , Site[i]);

printf("\n");

}

6. 程序调试

6. 1调试过程、步骤及遇到的问题

在完整程序调试时遇到几个小问题，后经细心改正后才把调试工作做完。

例如:当用printf输出时,出现了一些错误,几经调试后,发现原来是缺少了stdio.h 这样一个头文件,添加了头文件后, 还出现了一些问题,逻辑错误导致程序死循环或不循环或循环一小部分,但是编译时却没有错误,就是没有正确的输出答案,一开始我也不知道是怎么回事,通过和同学的交流,发现是逻辑错误,经过改正后,程序终于可以运行了.

7. 运行与测试

7.1运行演示

总结

通过了19周这个星期的程序设计，我从中得到了许多的经验以及软件设计的一些新的思路；从这个八皇后问题设计以及分析中，本人从中理解到了数据结构对于计算机软件设计的重要性，它的使用，可以改变一个软件的运行周期，也可以将软件的思路从繁化简，并且都能够通过数据结构的相关引导，将本身以前编程思想进行扩充，发展；这也是在这次课程设计中我所掌握得到的。

但由于我的基本知识还不是那么扎实，也缺乏对软件设计的经验，在这过程中也出现了一些问题，如，八皇后在变成初期由于没真正体会到数据结构中“树”在里面的运用，将程序往大一时c语言的方向发展，不自觉的采用了非递归的算法，结果大大增加了程序的复杂程度。并且也让整个程序的时间复杂度变得更大；在后来学生对数据结构的第六章进行了比较深入的研读，才发现了数据结构树的实际运用的空间是相当的大，并且，通过了重温树的回溯，以及二叉树的遍历，最终将程序进行了一次较大的改造。并且通过思考，再将以前的数组知识加以运用才最终解决了这个问题，整个程序的算法的可看性也有了相当的改进。

课程设计随着时间的推移，也即将结束了，但这个学期数据结构的学习还是具有相当大的意义，它从一个程度上改变了我们的编程思想，如何将一个程序快速而又准备的进行编写，进行编译，都成为了我们思考的重点，也通过这一个学期的学习，我们将数据结构的思想带入到了我们以后的编程学习中去。在这个阶段，我也明白了，好的思想，不能提留于字面上的认知，还需要的是平时多练多写一些相关的程序，并且通过修改，加入新的算法去尝试改变自己的一些编程思想。保持更新算法的速度，这才是关键。

课程设计已经接近尾声了，但它给我的不只是程序设计上的满足，更重要的是对自己编程思想的一次更新，以及对算法的一个全新的认识！

我觉得还可以考虑开发N皇后问题,在主界面中添加一个int型的变量,程序一开始要求输入一个数(确定是几皇后问题),输入后按下enter 后,输出各种解.主程序与八皇后的求解大体相同.

致谢

在这次课程设计中,我遇到了不少问题,包括程序上的和课程设计的撰写上的,同学曾给过我许多帮助,在此我表示对他们的忠心感谢。同时，指导老师和实验人员给了我很多上机的机会，给了我一个做课程设计的很好的条件，我才能够顺利的完成，在此，我仅以文字的形式表示忠心感谢，感谢他们这么多天对我的帮助。

参考文献

[1] 苏仕华,数据结构课程设计.-北京:机械工业出版社,2005.5

[2] 于永彦,赵建洋.课程设计指导书.淮安：江苏淮阴工学院计算机工程系,2006

[3] 刘振安,刘燕君，孙忱. C++语言课程设计.北京：高等教育出版社,2003

[4] 陈志泊, 张海燕, 王春玲. Visual C++程序设计. 中国铁道出版社,2005

[5] 吕凤哲,C++语言程序设计（第二版）.北京：电子工业出版社,2005

[6]殷人昆，陶永雷等.数据结构（用面向对象方法与C++ ）.北京:清华大学出版社，

1999

[7]严蔚敏，吴伟民，数据结构．北京：清华大学出版社，1997

[8]李春葆.数据结构—考研指导.北京:清华大学出版社,2002

[9]陈慧南．数据结构—C++语言描述．北京：人民邮电出版社，2005．03

指导教师评语

学号1061303127 姓名叶青班级信息106

选题

名称

八皇后

序号评价内容权重（%）得分1 考勤记录、学习态度、工作作风与表现。5

2 自学情况：

上网检索机时数、文献阅读情况（笔记）。

10

3 论文选题是否先进，是否具有前沿性或前瞻性。 5

4 成果验收：

是否完成设计任务；能否运行、可操作性

如何等。

20

5 报告的格式规范程度、是否图文并茂、语言规

范及流畅程度；主题是否鲜明、重心是否突出、

论述是否充分、结论是否正确；是否提出了自

己的独到见解。

30

6 文献引用是否合理、充分、真实。 5

7 答辩情况：

自我陈述、回答问题的正确性、用语准确

性、逻辑思维、是否具有独到见解等。

25

合计

指导教师（签章）：

2008年6月30日

八皇后问题的解决完整文档

工学院 数据结构课程设计报告设计题目：八皇后 2008 年 6 月25 日 设计任务书

摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法

目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (2) 2.2软硬件的需求 (2) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (3) 4.1算法描述及详细流程图 (3) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (8) 6.1调试过程、步骤及遇到的问题 (8) 7. 运行与测试 (8) 7.1运行演示 (8) 总结 (10) 致 (11)

参考文献 (12) .

1. 课题综述 1. 1课题的来源及意义 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。 到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。 1. 2 面对的问题 1）解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 2）使用数据结构的知识，用递归法解决问题。 2. 需求分析

八皇后解题思路

1.引子 中国有一句古话，叫做“不撞南墙不回头"，生动的说明了一个人的固执，有点贬义，但是在软件编程中，这种思路确是一种解决问题最简单的算法，它通过一种类似于蛮干的思路，一步一步地往前走，每走一步都更靠近目标结果一些，直到遇到障碍物，我们才考虑往回走。然后再继续尝试向前。通过这样的波浪式前进方法，最终达到目的地。当然整个过程需要很多往返，这样的前进方式，效率比较低下。 2.适用范围 适用于那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题。 3.应用场景 在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。国际象棋的棋盘如下图所示： 4.分析 基本思路如上面分析一致，我们采用逐步试探的方式，先从一个方向往前走，能进则进，不能进则退，尝试另外的路径。首先我们来分析一下国际象棋的规则，这些规则能够限制我们的前进，也就是我们前进途中的障碍物。一个皇后q(x,y)能被满足以下条件的皇后 q(row,col)吃掉 1）x=row(在纵向不能有两个皇后) 2) y=col（横向） 3）col + row = y+x;（斜向正方向） 4) col - row = y-x;（斜向反方向） 遇到上述问题之一的时候，说明我们已经遇到了障碍，不能继续向前了。我们需要退回来，尝试其他路径。 我们将棋盘看作是一个8*8的数组，这样可以使用一种蛮干的思路去解决这个问题，这样我们就是在8*8=64个格子中取出8个的组合，C(64,80) = 4426165368,显然这个数非常大，在蛮干的基础上我们可以增加回溯，从第0列开始，我们逐列进行，从第0行到第7行找到一个不受任何已经现有皇后攻击的位置，而第五列，我们会发现找不到皇后的安全位置了，前面四列的摆放如下:

算法实验 递归回溯解八皇后问题

深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：15级软工学术型实验时间：2015-12-08 实验报告提交时间：2015-12-09 教务部制

一．实验目的 1.掌握选回溯法设计思想。 2.掌握八皇后问题的回溯法解法。 二．实验步骤与结果 实验总体思路： 根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。 回溯法的实现及实验结果： 1、判断函数 代码1： procedure BTrack_Queen(n) //如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。 global X(1:k);integer i,k i←1 while i0 do X(k)←X(k)+1 //移到下一个位置 while X(k)<=n and not Judge(k) do //判断能否放置皇后 X(k)←X(k)+1 repeat if X(k)<=n //找到一个位置 then if k=n //是一个完整的解吗

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

数据结构课程设计 选题：八皇后问题 姓名： 学号： 指导老师： 目录 一.选题概述---------------------------------------3

二.设计要求与分析--------------------------------3 三.数据结构与定义--------------------------------4 1.结构体定义 2.函数定义 3.函数之间的定义 四.程序段与分析----------------------------------5 五.完整程序代码及运行结果截图------------------7 六.心得体会--------------------------------------10 七.参考文献--------------------------------------10

一．选题概述： 在实际应用中，有相当一类问题需要找出它的解集合，或者要求找出某些约束条件下的最优解。求解时经常使用一种称为回溯的方法来解决。所谓回溯就是走回头路，该方法是在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择通路继续搜索。为了能够沿着原路逆序回退，需用栈来保存曾经到达的每一个状态，栈顶的状态即为回退的第一站，因此回溯法均可利用栈来实现。而解决八皇后问题就是利用回溯法和栈来实现的。 二．设计要求与分析 八皇后问题是在8x8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。 八皇后在棋盘上分布的各种可能的格局，其数目非常大，约等于232种，但是，可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行上。这样在放置第i个皇后时，只要考虑它与前i 一1个皇后处于不同列和不同对角线位置上即可。因此，其算法基本思想如下： 从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1，2，…，8列进行试探，并尽可能取小的列数。若当前试探的列位置

回溯法之N皇后问题(C语言)

//回溯法之N皇后问题当N>10，就有点抽了~~ /*结果前total行每行均为一种放法，表示第i行摆放皇后的列位置，第total+1行，输出total*/ #include #include int n,stack[100]; //存当前路径 int total; //路径数 void make(int l) //递归搜索以stack[l]为初结点的所有路径 { int i,j; //子结点个数 if (l==n+1) { total=total+1; //路径数+1 for(i=1;i<=n;i++) printf("%-3d",stack[i]); //输出第i行皇后的列位置stack[i] printf("\n"); exit; //回溯（若试题仅要求一条路径，则exit改为halt即可）} for (i=1;i<=n;i++) { stack[l]=i; //算符i作用于生成stack[l-1]产生子状态stack[l]; if (!att(l,i)) make(l+1); } //再无算符可用，回溯 } int att(int l,int i) { int k; for (k=1;k

数据结构实验报告利用栈结构实现八皇后问题

数据结构实验报告 实验名称：实验二——利用栈结构实现八皇后问题 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月21日 1．实验要求 （1）实验目的 通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力 （2）实验内容 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 ①可以使用递归或非递归两种方法实现 ②实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线。 （3）代码要求 ①必须要有异常处理，比如删除空链表时需要抛出异常； ②保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 ③递归程序注意调用的过程，防止栈溢出 2. 程序分析 2.1 存储结构 栈（递归）：

2.2 关键算法分析 (1)递归 void SeqStack::PlaceQueen(int row) //在栈顶放置符合条件的值的操作,即摆放皇后{ for (int col=0;col::Judgement() { for(int i=0;i

八皇后问题算法分析

流程图 八皇后问题算法分析 在这个问题中首先定义的是一个用于构造界面的二位数组a【i】【j】和一个用于判断的表头数组number【】。在开始进行八皇后棋子排列的时候，首先对行进行递增循环，即i初始值为0，每次i++，i最大值为8的循环。在每次循环中产生一个小于8的随机数q，然后判断表头数组number【】中number【q】位置的值是否为1，如果不是，则在二维数组a【i】【q】位置上打印表示棋子的“K”；如果为1，则返回产生随机数的步骤继续产生随机数。在循环到i>8时，跳出循环，这时候一个完整的八皇后排列也就出来了。 源代码： package queen; import java.awt.*; import java.awt.event.*; class equeen extends Frame implements ActionListener{ //构造界面和定义数组 Button enter; Button clean; Button exit; int number[] = new int[8]; int i,j,q; Label a[][] = new Label[8][8]; equeen(String s){ GridLayout grid; grid = new GridLayout(9,8); setLayout(grid); enter = new Button("begin"); clean = new Button("clean");

exit = new Button("esit"); for(int i = 0;i<8;i++){ for(int j = 0;j<8;j++){ a[i][j] = new Label(); if((i+j)%2==0)a[i][j].setBackground(Color.yellow); else a[i][j].setBackground(Color.gray); add(a[i][j]); } } for(int i = 0;i<8;i++){ number[i] = 0;//初始化判断数组 } add(enter); add(clean); add(exit); enter.addActionListener(this); clean.addActionListener(this); exit.addActionListener(this); setBounds(100,100,300,300); setVisible(true); validate(); } public void actionPerformed(ActionEvent e){ if(e.getSource()==enter){ for(int i =0;i<8;i++){ for(int j=0;j<8;j++){ a[i][j].setText(""); } } for(int i =0;i<8;i++){ while(true){ q = (int)(Math.random()*8); if(number[q]==0){ a[i][q].setText("K"); number[q] = 1; break; } else if(number[q]!=0) continue; } } for(int i = 0;i<8;i++){ number[i] = 0; } }

数据结构实验报告——栈(八皇后问题)

1．实验要求 【实验目的】 1、进一步掌握指针、模板类、异常处理的使用 2、掌握栈的操作的实现方法 3、掌握队列的操作的实现方法 4、学习使用栈解决实际问题的能力 5、学习使用队列解决实际问题的能力 【实验内容】 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 提示： 1、可以使用递归或非递归两种方法实现 2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析 2.1 存储结构 存储结构：栈（递归） 2.2 关键算法分析 【设计思想】 由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法 【伪代码】 1、输入皇后个数n 2、k=1 3、判断k是否大于n 3.1 是：打印一组可能 3.2 否：循环行位置1~n 判断该位置是否符合要求，若符合记录q[k]的坐标y值 k+1 重复3 【关键算法】 1、递归 void Queen::Queens(int k,int n)

{ int i; if(k>n) { Print(n); count(); } else { for(i=1;i<=n;i++) if(Isavailable(i,k)) //判断该行中该位置放置‘皇后’是否符合要求 { q[k]=i; //记录改行中该点的位置 Queens(k+1,n); //放置下一行的‘皇后’ } } } 2、判断皇后放置位置是否符合要求 bool Queen::Isavailable(int i,int k) { int j; j=1; while(j

八皇后问题地解决完整文档

淮阴工学院 数据结构课程设计报告设计题目：八皇后 2008 年 6 月25 日 设计任务书 课题 名称 八皇后 设计目的1.用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既 攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现． 2.通过这次课程设计,提高自己的编程能力,熟悉c++的编程坏境,为以后的程 序开发打下基础.

实验环境1）系统要求：win98以上操作系统；2）语言平台：tc++或vc++6.0；3）执行文件：八皇后.exe 任务要求试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。 工作进度计划 序号起止日期工作内容 1 2008.6.23~2008.6.24查阅相关内容 2 2008.6.24~2008.6.25编写代码及实习报告 3 2008.6.25~2008.6.26完善课程设计报告 4 2008.6.26~2008.6.27答辩 指导教师（签章）： 2008 年 6 月30 日

摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法

八皇后问题及解答

八皇后问题 问题描述： 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相冲突 （在每一横列，竖列，斜列只有一个皇后）。 求解： 标题: 八皇后问题的解（回溯法程序代码） 发信站: 网易虚拟社区(Fri Jul 14 10:06:52 2000),站内信件 以前上学的时候，写8皇后程序的时候偷懒用最笨的算法，在8086上计算十皇后的时候，我放了张纸条，说明计算机正在运行，然后去吃饭，吃完以后，才看到结果。前几天，刚好有空，所以重写了一次，以补当年的遗憾。 #include "stdio.h" int attacked(int *array,int position){ int flag=-1; float step; if(position==1) return flag; for(step= 1.00;step

(array+(int)step)-*(array+position))/(step-position))==-1){ flag=1; break;}} return flag;}void main(void){ int countSum,queenSum,printCount,*queenArray,queenPosition=0; int tempArray[20]={66,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; countSum=1; queenArray=tempArray; printf("input you queenSum here: "); scanf("%d",&queenSum); fflush(stdin); if(queenSum<4){ printf("the %d queen's sum is 0\n",queenSum); return;}for(;;){ if(countSum=queenSum){ if(*(queenArray+countSum-1)

八皇后问题的解决完整文档

淮阴工学院 数据结构课程设计报告 设计题目：八皇后 系（院）:计算机工程系 专业：信息安全 班级：信息 1 0 6 学生姓名: 叶青学号:1061303127 指导教师:张亚红寇海洲胡荣林夏森 学年学期: 2007 ~ 2008 学年第 2 学期 2008 年 6 月25 日

设计任务书

摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法

目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (1) 2.2软硬件的需求 (1) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (2) 4.1算法描述及详细流程图 (2) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (7) 6.1调试过程、步骤及遇到的问题 (7) 7. 运行与测试 (7) 7.1运行演示 (7) 总结 (9) 致谢 (10) 参考文献 (11) .

八皇后问题vb解

Dim int1 As Integer Private Sub cmd_click() List1.Clear int1 = 0 Dim i As Single, j As Single i = 1 j = 1 Dim p As Integer, b As Boolean Dim a(1 To 8, 1 To 8) As Boolean Dim ii(1 To 8) As Single Dim jj(1 To 8) As Single a(i, j) = True ii(1) = i jj(1) = j Do Do While i < 8 i = i + 1 If i = 0 Then Exit Sub j = 1 If b = True Then a(i, jj(i)) = False b = False j = jj(i) + 1 End If Do If j > 8 Then i = i - 2: b = True: Exit Do For p = 1 To i - 1 If j = jj(p) Or Abs(i - ii(p)) = Abs(j - jj(p)) Then Exit For Next If p = i Then Exit Do j = j + 1 Loop If b = False Then ii(i) = i: jj(i) = j a(i, j) = True End If Loop

Dim p1 As Integer, p2 As Integer, str1 As String For p1 = 1 To 8 str1 = "" For p2 = 1 To 8 If a(p1, p2) = False Then str1 = str1 & "+ " Else: str1 = str1 & "@ " End If Next List1.AddItem str1 Next int1 = int1 + 1 Caption = int1 i = i - 1: b = True List1.AddItem " " & Str(int1) List1.AddItem vbCrLf Loop End Sub 窗体上一个list控件list1 一个按钮 cmd

回溯算法与八皇后问题N皇后问题Word版

回溯算法与八皇后问题(N皇后问题) 1 问题描述 八皇后问题是数据结构与算法这一门课中经典的一个问题。下面再来看一下这个问题的描述。八皇后问题说的是在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。更通用的描述就是有没有可能在一张N*N的棋盘上安全地放N个皇后？ 2 回溯算法 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。 下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘： 1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列 2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没 有两个皇后)，若不满足，跳到第4步 3) 在当前位置上满足条件的情形： 在当前位置放一个皇后，若当前行是最后一行，记录一个解； 若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；

若当前行是最后一行，当前列不是最后一列，当前列设为下一列； 若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置； 以上返回到第2步 4) 在当前位置上不满足条件的情形： 若当前列不是最后一列，当前列设为下一列，返回到第2步; 若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步; 算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。为了提高效率，有各种优化策略，如多线程，多分配内存表示棋盘等。 为了便于将上述算法编程实现，将它用另一种形式重写： Queen() Loop: if check_pos(curr_row, curr_col) == 1 then put_a_queen(curr_row, curr_col); if curr_row == N then record_a_solution(); end if; if curr_row != N then curr_row = curr_row + 1; curr_col = 1; else if curr_col != N then curr_col = curr_col + 1; else backtrack(); end if; end if; else if curr_col != N then

n皇后问题算法实验报告

算法分析与设计实验报告 实验内容：N皇后问题 实验时间：2013.12.3 姓名：杜茂鹏 班级：计科1101 学号：0909101605

一、实验内容及要求 在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 二、实验目的 1.巩固和加深对回溯法的理解 2.了解递归和迭代法在回溯法中的应用 三、算法分析 1.理解皇后不被攻击的条件：n后问题等价于在n*n格的棋盘上放置n个皇后，任何两个皇后不能放在同一行或同一列或同一斜线上。 2.算法模块简要分析 用数组存储皇后的位置，将i设置为0. Int place(*x,n) :数组x[] 用来表示列数，n为皇后个数，用来判断皇后是否被攻击，判断的条件是（x[i]-x[n]==i-n||x[i]-x[n]==n-i||x[i]==x[n]）即用来判断“同一行或同一列或同一斜线上”。 Int print(*x,n):打印皇后解的空间。 Int iniprint(*x,n):初始化打印函数，相当于对棋盘初始化。将可以放皇后的位置记为“1”，不放皇后的位置记为“0”。 Int Nqueen(int n):n皇后问题求解，如果满足一组可行解，sum++。Int i=0,如果x[i]>=n的时候即进行下一行，i++；当i=n时，

sum++；输出该组可行解的个数和位置的矩阵。并且i--，回溯到上一层继续搜索可行解。 四、运行结果及分析 1、三皇后没有可行解 2、 2.4个皇后有2个可行解 3.5皇后有10个可行解 五、源代码 #include static int n, sum=0;//可行解个数 static int locate[20]; int place(int k) {//判断是否在一条线上并返回0,1 for(int i=1;in){

数据结构八皇后问题

如对您有帮助，请购买打赏，谢谢您！ 目录 一需求分析............................................ 错误！未定义书签。 1.1程序的功能：...................................... 错误！未定义书签。 1.2程序的输入输出要求：.............................. 错误！未定义书签。二概要设计............................................ 错误！未定义书签。 2.1程序的主要模块：.................................. 错误！未定义书签。 2.2程序涉及：........................................ 错误！未定义书签。三详细设计............................................. 错误！未定义书签。 3.1相关代码及算法..................................... 错误！未定义书签。 3.1.1 定义相关的数据类型如下：...................... 错误！未定义书签。 3.1.2 主模块类C码算法：............................. 错误！未定义书签。 3.1.3 画棋盘模块类C码算法........................... 错误！未定义书签。 3.1.4 画皇后模块类C码算法：........................ 错误！未定义书签。 3.1.5 八皇后摆法模块（递归法）：.................... 错误！未定义书签。 3.1.6 初始化模块.................................... 错误！未定义书签。 3.1.7 输出摆放好的八皇后图形（动态演示）：.......... 错误！未定义书签。 3.2相关流程图......................................... 错误！未定义书签。四调试分析............................................. 错误！未定义书签。五设计体会............................................ 错误！未定义书签。六附录................................................ 错误！未定义书签。七参考文献............................................ 错误！未定义书签。

回溯法解八皇后问题

回溯法解八皇后问题 在N * N 格的棋盘上放置彼此不受攻击的N 个皇后。N个皇后问题等价于在N * N 格的棋盘上放置N 个皇后，任何2个皇后不在同一行或同一列或同一斜线上。当N等于8，就是著名的八皇后问题。 此问题是通过C语言程序编写的，在Turboc环境下完成实现的。输出结果见（输出结果。TXT文件） 详细代码为： /*///////////////////////////////////////////////////////////////////// /// /////The programming is a complex problem about the ways of queens./////// /////Programmer: Luo Xiaochun /////// /////Completed date: 2007.12 //////// /////V ersion number: Turboc 2.0 //////// /////////////////////////////////////////////////////////////////////// /*/ #include #include #define false 0 #define true 1 #define quesize 8 int gx[quesize+1]; int sum=0; int place( int k ); void print( int a[] ); void nqueens( int n ); FILE *fp; int main( ) { system("cls"); fp = fopen("outfile.txt", "w");

8皇后问题matlab算法

M文件 function PlaceQueen(row,matrix,N)%回溯法放置皇后 if row>N PrintQueen(N,matrix);%打印棋盘 else for col=1:N matrix(row,col)=1; if row==1||Conflict(row,col,N,matrix)%检测是否冲突 PlaceQueen(row+1,matrix,N); end matrix(row,col)=0; end end %子函数：检测冲突 function result=Conflict(row,col,N,matrix)%检测是否冲突 result=1; for i=1:row-1 for j=1:N if matrix(i,j)==1 if ((j==col)||(abs(row-i)==abs(col-j)))%是否产生冲突：在同一直线，斜线上 result=0; break; end end end if result==0 break; end end %子函数：打印棋盘信息

function PrintQueen(N,matrix) global solutionNum; %定义全局变量，来累积方法数 solutionNum=solutionNum+1; disp(['第',num2str(solutionNum),'种方法：']) disp(matrix) 脚本文件 clear all clc global solutionNum; solutionNum=0;%全局变量记录方法数 N=8;%皇后个数 matrix=zeros(N);%存储皇后位置信息 PlaceQueen(1,matrix,N)%调用放置方法

数据结构课程设计之_八皇后问题

课程设计报告 课程名称数据结构课程设计 课题名称八皇后问题演示 专业通信工程 班级通信工程1081 学号201013120103 姓名刘献文 指导教师田娟秀郭芳 2012年7 月 6 日

湖南工程学院 课程设计任务书 课程名称数据结构 课题八皇后问题演示 专业班级通信工程1081 学生姓名刘献文 学号201013120103 指导老师田娟秀郭芳 审批 任务书下达日期2012 年7 月 1 日 任务完成日期2012 年7 月 6 日

1设计内容与设计要求 1.1设计内容 （4）课题四：八皇后问题演示 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 设计思路：解决8皇后时，在安放第i行皇后时，需要在列的方向从1到n试 探(j =1,…, n)：首先在第j列安放一个皇后，如果在列、主对角线、次对角线方 向有其它皇后，则出现攻击，撤消在第j列安放的皇后。如果没有出现攻击，在第 j列安放的皇后不动，递归安放第i+1行皇后。 对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动。要求用Turbo C或VC6.0 MFC实现的八皇后问题的图形程序，能够演示全部的92组解。 1.2 选题方案： 所选题目根据学号确定，学号模6加1，即（学号%6+1）。如你的学号为9，则 所选题目号为：9%6+1＝（题目4）。注意，所有的课题都要求用图形方式演示步骤 和结果。同学们可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。 1.3设计要求： 1.3.1 课程设计报告规范 （1）需求分析 a.程序的功能。 b.输入输出的要求。 （2）概要设计 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块 的功能。

八皇后问题(回溯法)

八皇后问题（回溯法）2009-08-11 12:03问题描述： 求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局，这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线4个方向互相捕捉。 解题思路： 总体思想为回溯法。 求解过程从空配置开始。在第1列~的m列为合理配置的基础上，再配置第m+1列，直至第n列也是合理时，就找到了一个解。在每列上，顺次从第一行到第n行配置，当第n行也找不到一个合理的配置时，就要回溯，去改变前一列的配置。 为使在检查皇后配置的合理性方面简易方便，引入一下4个工作数组： ?数组col[i],表示在棋盘第i列，col[i]行有一个皇后； ?数组a[],a[k]表示第k行上还没有皇后； ?数组b[],b[k]表示第k列右高左低斜线上没有皇后； ?数组c[],c[k]表示第k列左高右低斜线上没有皇后； 代码： #include #include void queen(int N) { //初始化N+1个元素，第一个元素不使用int col[N+1]; //col[m]=n表示第m列，第n行放置皇后 int a[N+1]; //a[k]=1表示第k行没有皇后 int b[2*N+1]; //b[k]=1表示第k条主对角线上没有皇后 int c[2*N+1]; //c[k]=1表示第k条次对角线上没有皇后 int j,m=1,good=1;char awn; for(j=0;j<=N;j++) {a[j]=1;} for(j=0;j<=2*N;j++) {b[j]=c[j]=1;} col[1]=1;col[0]=0; do { if(good) { if(m==N) //已经找到一个解

八皇后问题

安徽省巢湖学院计算机与信息工程学院 课程设计报告 课程名称《数据结构》 课题名称八皇后问题 专业计算机科学与技术 班级 学号 姓名 联系方式 指导教师 2011 年 12 月 25日

目录 1、数据结构课程设计任务书.............................................................................................. １ 1.1、题目..................................................................................................................... １ 1.2、要求..................................................................................................................... １ 2、总体设计....................................................................................................................... １ 2.1、功能模块设计 ...................................................................................................... １ 2.2、所有功能模块的流程图........................................................................................ ２ 3、详细设计....................................................................................................................... ５ 3.1、程序中所采用的数据结构及存储结构的说明........................................................ ５ 3.2、算法的设计思想................................................................................................... ５ 3.3、稀疏矩阵各种运算的性质变换 ............................................................................. ５ 4、调试与测试：................................................................................................................ ６ 4.1、调试方法与步骤： ............................................................................................... ６ 4.2、测试结果的分析与讨论： .................................................................................... ６ 4.3、测试过程中遇到的主要问题及采取的解决措施：................................................. ６ 5、时间复杂度的分析：..................................................................................................... ６ 6、源程序清单和执行结果 ................................................................................................. ６ 7、C程序设计总结 ........................................................................................................ １０ 8、致谢.......................................................................................................................... １０ 9、参考文献................................................................................................................... １０