哈尔滨理工大学信管专业数据结构课程实践报告之八皇后....doc

数据结构课程设计 学院：管理学院 班级：信息11-2班 数据结构课程设计 八皇后问题1、 内容 设计程序完成如下要求：在88的国际象棋棋盘上，放置8个皇后，使得这8个棋子不能互相被对方吃掉。 要求：(1)依次输出各种成功的放置方法。(2)最好能画出棋盘的图形形式，并在其上动态地标注行走的过程。(3)程序能方便地移植到其他规格的棋盘上。 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8x8格的国际象棋上摆放八个皇后，使其不能互相攻击，根据国际象棋的规定，皇后可以攻击与它在同一行、同一列或者同一斜线上的棋子，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。在8!=40320种排列中共有92种解决方案。二、本程序需要解决的问题1、建立合适的数据类型表示皇后在棋盘上所处的位置。2、成功的输出全部正确的放置方法。3、画出棋盘形式，在上面动态的标注其行走的过程。4、预期目标：运用c+程序设计的编程思想编写代码，实现八皇后问题的所有（92种）摆放情况。三、数据结构的选择和概要设计1、为了简单易行的表示皇后在棋盘所处的位置，在此建立一个整型数组queeni来表示，若queen3=2则表示皇后处在88棋盘的第三行和第二列。2、列：规定每一列放一个皇后，就不会造成列上的冲突；行：当第i行被某个皇后占据时，该行所有空格就都不能放置其他皇后；对角线：对角线有两个方向，在同一对角线上的所有点都不能有冲突。四、代码编写第一种：#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=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() 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=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); /如果前次的皇后放置