haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 初中作文初中作文

八皇后

发布时间:2013-12-07 09:31:55  

B 类 题

———八皇后问题 学 院 计算机科学与技术 专 业 计算机科学与技术 学 号 110341202 学 生 姓 名 陈格 指导教师姓名 沈中林 题 目 来 源 2010年程序设计题目 题 目 难 度 B类

2013 年 5月 22 日

一、题目

八皇后问题

a.程序功能简介:解决八皇后问题的程序。

b.设计要求:

(1)增加函数,每输出一组解,暂停屏幕,显示“按任意键继续!”。

(2)完善程序,编程计算八皇后问题共有几种排列方案。

(3)增加输出,显示在第一个皇后确定后,共有几组排列。

c.设计提示:

(1)该问题是19世纪著名数学家高斯1850年提出的会速算法的典型例题:在8*8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种方案。

(2)当指示用户输入第一个皇后的位置时,行列数必须为[0,7]区间内的整数。

(3)只要计算出第一个皇后放在任一相同列0~7行8种位置的排列总数即为八皇后问题的全部排列方案数目。

二、问题分析及求解基本思路

图1.八皇后放置原理图

Left↗ ↖Right

由八皇后放置原理图(如图1所示)可知,已有皇后(2,2),故深色部分不可再放置其他皇后,对于此棋盘有以下性质:对于15条Left方向对角线的格子,行号与列号之和为一常量,分别为0,1,?,13,14;而对于15条Right方向对角线的格子,行号与列号之差加上7也为一常量,分别为0,1,?,13,14。

使用数组col[]表示列方向使用情况,Left[]表示左对角线方向,Right[]表示右对角线方向,值均为true时表示可放置新皇后,否则不行。即第n行h列可放皇后的条件是表达式1为真:

col[h] && Left[n+h] && Right[n-h+7] 表达式1 程序的流程图如下图所示:

图1 程序流程图

三、问题求解的整体框架结构

先把0号皇后放在(0,0)位置,然后把1号皇后放在(1,h)位置,使其满足要求,接着放2号皇后,以此类推。若遇到某个皇后无论放在该行哪一列都不满足要求,则前一个皇后放置不当,须将其重置。若8个皇后均按要求放置好,这就是一组成功的排列方案,再如前所述,重置最后一个皇后,找到下一组方案。

四、主要算法

递归寻找皇后位置generate()

(1)声明变量col[]表示棋盘列方向使用情况,Left[]表示左对角线方向,Right[]表示右对角线方向,n为棋盘行数,h为棋盘列数,sum为总方案数;

(2)h=0;

(3)若col[h] && Left[n+h] && Right[n-h+7]为真,放置新皇后;

(4)col[h]=false,Left[n+h]=false,Right[n-h+7]=false,n=n+1;

(5)若八个皇后放好,sum=sum+1,否则跳到第(2)步;

(6)n=n-1,col[h]=true,Left[n+h]=true,Right[n-h+7]=true;

(7)若h<=7,h=h+1,否则结束。

五、测试

当用户输入第一个皇后位置错误时,提示重新输入,如图2所示。

图2.输入错误提示

输入第一个皇后位置后,输出该位置有皇后的所有方案,每输出一组排列方案,暂停屏幕,显示“请按任意键继续!”,如图3所示。

图3.输出符合要的排列方案

最后输出确定第一个皇后位置的排列方案数和八皇后问题总的排列方案数,如图4所示。

图4. 输出排列方案数

六、总结

本次课程设计中遇到了许多的困难,产生了不少的问题。

刚开始使用结构体表示皇后的位置,构造了较多的变量,程序设计中产生了许多的错误,判断同斜线情况不太方便,算法性能也不少很好。后来想到运用数组来表示皇后的位置,不但数据结构简单,而且较容易的表示处皇后的位置,容易分析皇后同列、同斜线的情况(用到abs( )函数),所以建立整型数组来表示皇后在棋盘上的位置。

最后就是——每输出一组解,暂停屏幕的问题,起初不知道该怎么样实现,但是后来想到在产生八皇后排列时加上 if(queen[row]==column)就输出一组解。(row以及column都是在主函数自动输入的)。

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com