N皇后问题——JAVA实现(源代码).doc
文本预览下载声明
2011/2012学年第2学期“算法分析与设计”上机报告
学院/系 信息工程学院计算机科学系 专业 计算机科学与技术 班级 项目名称 N皇后问题 组长 小组成员
目录
1. 问题描述...........................................................................................................3
2. 算法分析...........................................................................................................3
3. 伪代码...............................................................................................................4
4. 演示程序设计...................................................................................................5
5. 演示界面...........................................................................................................5
6. 算法实现...........................................................................................................8
7. 总结...................................................................................................................19
8. 参考文献.......................................................................................................... 20
问题描述:
N皇后问题(n-queen problem)是一个经典的组合优化问题,也是一个使用回溯法(backtracking)的典型例子。回溯法是一种系统地搜索问题解的方法。为了实现回溯,首先需要为为问题定义一个解空间(solution space),其至少包含问题的一个解(可能是最优解)。我们要从中找出满足问题约束条件的解,即可行解(feasible solution)。回溯算法一次扩展一个解,在对部分解进行扩展后,检查到目前为止的解是否为问题的一个解,如果是,则输出;否则,检查是否可以继续扩展。如果可以,则继续扩展;否则,删除最后添加的元素,尝试当前位置是否有另一元素。若没有合法的扩展方式,则进行回溯(backtrack)。
N皇后问题要求在一个n×n的棋盘上放置n个皇后,且使得每两个皇后之间都不能相互攻击,即它们中的任意两个都不能位于同一行、同一列或者同一对角线上。这次的任务就是借助GUI实现N皇后问题的动态演示。我们设定皇后个数在四个到八个之间可选,所选编程语言为JAVA。
算法分析:
N皇后问题是回溯法的一个经典例子,它的要求就是要找出在n×n的棋盘上放置n个皇后并使其不能相互攻击的所有解。设X=(x1,x2,…,xn)表示问题的解,,其中xi表示第i皇后放在第i行所在的列数。由于不存在两个皇后位于同一列上,因此xi互不相同。设有两个皇后分别位于棋盘( i , j )和( k , l )处,如果两个皇后位于同一对角线上,则表明它们所在的位置应该满足:i – j = k – l或i + j = k + l。综合这两个等式可得,如果两个皇后位于同一对角线上,那么它们的位置关系一定满足| j – l | = | i – k |。这是对皇后位置的合法性的判定,由函数PLACE来完成。
N-QUEEN函数功能是求出N皇后问题的所有解。它在循环体中计算xk的值,并对每一个xk的值,调用PLACE过程测试它的合法性,即寻找满足约束条件的xk的值。如果找到了一个合法的放置位置,就进一步测试求得的(x1,x2,…,xk)是否为问题的解。如果是,就将其输出;否则,就将k的值增加1继续循环,即继续寻找下一个皇后合法的位置。如果不存在合法的xk值,就将k的值减1进行回溯。
伪代码:
N-
显示全部