《哈尔滨理工大学信管专业数据结构课程实践报告之八皇后....doc》由会员分享，可在线阅读，更多相关《哈尔滨理工大学信管专业数据结构课程实践报告之八皇后....doc（6页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计 学院：管理学院 班级：信息11-2班 数据结构课程设计 八皇后问题一、 内容 设计程序完成如下要求：在88的国际象棋棋盘上，放置8个皇后，使得这8个棋子不能互相被对方吃掉。 要求：(1)依次输出各种成功的放置方法。(2)最好能画出棋盘的图形形式，并在其上动态地标注行走的过程。(3)程序能方便地移植到其他规格的棋盘上。 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，根据国际象棋的规定，皇后可以攻击与它在同一行、同一列或者同一斜线上的棋子，即任意两个皇后都不能处于同一行
2、、同一列或同一斜线上，问有多少种摆法。在8!=40320种排列中共有92种解决方案。二、本程序需要解决的问题1、建立合适的数据类型表示皇后在棋盘上所处的位置。2、成功的输出全部正确的放置方法。3、画出棋盘形式，在上面动态的标注其行走的过程。4、预期目标：运用C+程序设计的编程思想编写代码，实现八皇后问题的所有（92种）摆放情况。三、数据结构的选择和概要设计1、为了简单易行的表示皇后在棋盘所处的位置，在此建立一个整型数组queeni来表示，若queen3=2则表示皇后处在88棋盘的第三行和第二列。2、列：规定每一列放一个皇后，就不会造成列上的冲突；行：当第i行被某个皇后占据时，该行所有空格就都不
3、能放置其他皇后；对角线：对角线有两个方向，在同一对角线上的所有点都不能有冲突。四、代码编写第一种：#include#define true 1#define false 0int a9,b17,c17;int s9;void main()void print(),movequeen(),eightqueen();eightqueen();void print()int k;printf(n行号: 1 2 3 4 5 6 7 8n);printf(列号:);for(k=1;k=8;k+)printf(%4d,sk);printf(n);void movequeen(int i,int j)aj=
4、1;bi+j=1;ci-j+9=1;void eightqueen()int i,j;for(i=2;i=2 & i=1)while(j=8)if(aj & bi+j & ci-j+9) break;j+;if(j=1)j=si;movequeen(i,j);j+;运行结果：以行号和列号的形式出现92种结果。第二种：#include static char Queen88;static int a8;static int b15;static int c15;static int iQueenNum=0; /记录总的棋盘状态数void qu(int i); /参数i代表行int main()
5、int iLine,iColumn; /棋盘初始化，空格为*，放置皇后的地方为 for(iLine=0;iLine8;iLine+) aiLine=0; /列标记初始化，表示无列冲突 for(iColumn=0;iColumn8;iColumn+) QueeniLineiColumn=*; /主、从对角线标记初始化，表示没有冲突 for(iLine=0;iLine15;iLine+) biLine=ciLine=0; qu(0); return 0;void qu(int i) int iColumn; for(iColumn=0;iColumn8;iColumn+) if(aiColumn=
6、0&bi-iColumn+7=0&ci+iColumn=0) /如果无冲突 QueeniiColumn=; /放皇后 aiColumn=1; /标记，下一次该列上不能放皇后 bi-iColumn+7=1; /标记，下一次该主对角线上不能放皇后 ci+iColumn=1; /标记，下一次该从对角线上不能放皇后 if(i7) qu(i+1); /如果行还没有遍历完，进入下一行 else /否则输出 /输出棋盘状态 int iLine,iColumn; printf(第%d种状态为：n,+iQueenNum); for(iLine=0;iLine8;iLine+) for(iColumn=0;iColumn8;iColumn+) printf(%c ,QueeniLineiColumn); printf(n); printf(nn); /如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置 QueeniiColumn=*; aiColumn=0; bi-iColumn+7=0; ci+iColumn=0; 运行结果：出现92种状态。
