《北邮数据结构试验报告 八皇后问题》由会员分享，可在线阅读，更多相关《北邮数据结构试验报告 八皇后问题（6页珍藏版）》请在金锄头文库上搜索。
1、北京邮电大学数据结构试验报告实验名称： 实验二 栈和队列学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014 年 1 月 3 日1 实验目的 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力2 实验内容2.2 题目 2利用栈结构实现八皇后问题。八皇后问题 19 世纪著名的数学家高斯于 1850 年提出的。他的问题是：在 8*8 的棋盘上放置 8 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。3 程序分析3.1 存储结构
2、栈的存储结构：3.2 算法分析八皇后问题可看成是 07 这八个数满足一定条件的排序1.判断某位置是否可用于摆放皇后bool check(int position,int data)/position 表示行数，所以不会同行，检查是否存在有多个皇后在同一列/对角线的情况int i;int j;for(i=0;iusing namespace std;static int EightQueens8=0,Count=0;void print();/输出每一种情况下棋盘中皇后的摆放情况bool check(int position,int data);/检查插入位置是否与之前插入的皇后在同一列/对角线
3、void eight_queen(int position);int main()eight_queen(0);cout可以的组合一共有：Count种endl;return 0;void print()/输出每一种情况下棋盘中皇后的摆放情况for(int i=0;i8;i+)coutEightQueensi ;coutendl;bool check(int position,int data)/检查是否存在有多个皇后在同一列/对角线的情况int i;int j;for(i=0;iposition;i+)j=EightQueensi;if(j=data) return false; /列数相同，
4、错误if(position-i)=(data-j) return false; /同一对角线，错误if(position-i)=(j-data) return false; /同一对角线，错误return true;void eight_queen(int position)int data;for(data=0;data8;data+)if(check(position,data)EightQueensposition=data;if(position=7) /直到完成一种组合Count+;print();EightQueensposition=0;return;eight_queen(position+1); /递归EightQueensposition=0;
