N皇后问题——JAVA实现(源代码)

《N皇后问题——JAVA实现(源代码)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2011/2012学年第2学期“算法分析与设计”上机报告学院／系信息工程学院计算机科学系专业计算机科学与技术班级项目名称N皇后问题组长小组成员目录1.问题描述...........................................................................................................32.算法分析............................................................

2、...............................................33.伪代码...............................................................................................................44.演示程序设计................................................................................

3、...................55.演示界面...........................................................................................................56.算法实现...........................................................................................................87.总结.

4、..................................................................................................................198.参考文献..........................................................................................................201.问题描述：N皇后问题（n-queenpro

5、blem）是一个经典的组合优化问题，也是一个使用回溯法（backtracking）的典型例子。回溯法是一种系统地搜索问题解的方法。为了实现回溯，首先需要为为问题定义一个解空间（solutionspace）,其至少包含问题的一个解（可能是最优解）。我们要从中找出满足问题约束条件的解，即可行解（feasiblesolution）。回溯算法一次扩展一个解，在对部分解进行扩展后，检查到目前为止的解是否为问题的一个解，如果是，则输出；否则，检查是否可以继续扩展。如果可以，则继续扩展；否则，删除最后添加的元素，尝

6、试当前位置是否有另一元素。若没有合法的扩展方式，则进行回溯（backtrack）。N皇后问题要求在一个n×n的棋盘上放置n个皇后，且使得每两个皇后之间都不能相互攻击，即它们中的任意两个都不能位于同一行、同一列或者同一对角线上。这次的任务就是借助GUI实现N皇后问题的动态演示。我们设定皇后个数在四个到八个之间可选，所选编程语言为JAVA。2.算法分析：N皇后问题是回溯法的一个经典例子，它的要求就是要找出在n×n的棋盘上放置n个皇后并使其不能相互攻击的所有解。设X=(x1,x2,…，xn)表示问题的解，，

7、其中xi表示第i皇后放在第i行所在的列数。由于不存在两个皇后位于同一列上，因此xi互不相同。设有两个皇后分别位于棋盘(i,j)和(k,l)处，如果两个皇后位于同一对角线上，则表明它们所在的位置应该满足：i–j=k–l或i+j=k+l。综合这两个等式可得，如果两个皇后位于同一对角线上，那么它们的位置关系一定满足

8、j–l

9、=

10、i–k

11、。这是对皇后位置的合法性的判定，由函数PLACE来完成。N-QUEEN函数功能是求出N皇后问题的所有解。它在循环体中计算xk的值，并对每一个xk的值，调用PLACE过程测试它

12、的合法性，即寻找满足约束条件的xk的值。如果找到了一个合法的放置位置，就进一步测试求得的(x1,x2,…,xk)是否为问题的解。如果是，就将其输出；否则，就将k的值增加1继续循环，即继续寻找下一个皇后合法的位置。如果不存在合法的xk值，就将k的值减1进行回溯。1.伪代码：N-QUEEN(n)1x[1]←0//第一个皇后的列位置初始化2k←1//当前列3whilek>0do4x[k]←x[k]+1//到下一列5whilex[k]≤n＆notPLACE(k)