n皇后问题(MFC界面显示)

2015-2016学年第2学期“软件工程”课程设计报告学院／系信息工程学院计算机科学系专业计算机科学与技术班级计算机2班项目名称递归法解决N皇后问题演示软件组长张一轮小组成员关童，孙吉阳，杨策文，何林轩张一轮SRS文档编写，设计报告编排修改关童代码框架结构编写，单步求解，依次求解，一步求解孙吉阳速度控制功能实现，伪代码联动杨策文LLD文档编写，软件白盒测试何林轩HLD文档编写，软件黑盒测试2目录摘要................................................................4第一章算法描述...................................................6第二章需求说明书.................................................72.1介绍............................................................72.1.1目的.......................................................82.1.2文档约定...................................................82.1.3目标读者与阅读建议.........................................82.2总体说明........................................................82.2.1产品的角度.................................................82.2.2用户类别及特点.............................................92.2.3操作环境...................................................92.2.4用户文档...................................................92.2.5假设与依赖关系.............................................92.3外部接口要求....................................................92.3.1用户界面...................................................92.3.2硬件接口..................................................102.3.3软件界面..................................................102.3.4通信接口..................................................102.4其他非功能需求.................................................102.4.1性能需求..................................................102.4.2安全需求..................................................102.4.3软件质量属性..............................................10第三章概要设计说明..............................................113.1范围...........................................................113.1.1标识......................................................113.1.2系统概述..................................................113.1.3文档概述..................................................113.2引用文件......................................................1123.3全系统的设计决策..............................................1123.4结构设计......................................................1123.4.1组件.....................................................1123.4.2执行的概念................................................133.4.3动态控制序列..............................................133.4.4状态转换图................................................143.4.5各单位之间的优先事项......................................153.4.6异常和错误处理............................................163.4.7其他方面的动态行为........................................163.4.8界面设计..................................................163.5需求追踪.......................................................1633.6检查清单.......................................................173.7说明...........................................................17第四章详细设计说明..............................................184.1.概述...........................................................184.2.实现设计.......................................................184.2.1单元模块的设计决策........................................184.2.2约束限制..................................................184.2.3用伪代码或者流程图来说明执行逻辑..........................194.2.4错误和系统记录信息........................................244.2.5数据结构、功能的名字,原型和文件名称.......................244.3.实现过程中要考虑的问题.........................................24第五章软件测试..................................................255.1黑盒测试.......................................................255.2.白盒测试.......................................................264摘要n皇后问题是一个古老而著名的问题，它是回溯算法的典型例题。该问题是十九世纪德国著名数学家高斯于1850年提出的：在8行8列的国际象棋棋盘上摆放着八个皇后。使他们之间不能互相攻击。若两个皇后位于同一行、同一列或同一对角线上，则它们之间就可以互相攻击。后来人们从8皇后问题延伸到了n皇后问题，问题的重点即使每两个皇后都不能在同一行、同一列、同一对角线上。在分析这个问题时，我们不妨从第一列开始放置皇后。这里我们选择使用回溯法即经典的递归法来求解n皇后问题，这个算法将在棋盘上一列一列地放置皇后直到n个皇后在不相互攻击的情况下都被摆放在棋盘上，算法便终止。当一个新加入的皇后因为与已经存在的皇后之间相互攻击而不能被摆在棋盘上时，算法便发生回溯。一旦发生这种情况，就试图把最后放在棋盘上的皇后移动到其他地方。这样做是为了让新加入的皇后能够在不与其它皇后相互攻击的情况下被摆放在棋盘的适当位置上。如图所示是两种满足要求摆放皇后的图。关键词：回溯法，n皇后，GUIABSTRACTNqueensproblemisanoldandwell-knownproblem,itisbacktrackingalgorithmstypicalexample.Theproblemiswell-knownnineteenth-centuryGermanmathematicianGaussproposedin1850:Online8of8chessboardplacedeightQueens.Sothattheycannotattackeachotherbetween.Ifthetwoqueensonthesamerow,thesamecolumnorthesamediagonal,theycanattackeachotherbetweenthem.Later,peoplefromeightqueensproblemextendstothenqueensproblem,evenifeachofthetwokeyissuesofthequeencannotbeinthesamerow,thesamecolumn,onthesamediagonal.Inanalyzingthisquestion,wemightbegintoplacetheQueenfromthefirstcolumn.Herewechoosetousebacktrackingieclassicalrecursionmethodtosolvenqueensproblem,thealgorithmwillplacequeensontheboardaoneplaceuntilthen-queenswithoutmutualattackshavebeenplacedontheboard,thealgorithmisterminated.WhenaddinganewqueenbecausealreadyexistingbetweentheQueenandmutualattackswhichcannotbeplacedontheboard,backtrackingalgorithmwillhappen.Oncethishappens,itistryingtomovethelastplacedqueenontheboardelsewhere.Thisisdonetoallownewentrantstothequeencanbewithout5theotherqueensattackeachothertobeplacedintheappropriatepositionontheboard.AsshowninFIGplacedtomeettherequirementsaretwoqueenFIG.KEYWORDS:bac