n皇后问题——java实现(已成功)

《n皇后问题——java实现(已成功)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、N皇后问题目录1.问题描述...........................................................................................................32.算法分析...........................................................................................................33.伪代码...............................................

2、................................................................44.演示程序设计...................................................................................................55.演示界面...........................................................................................................5

3、6.算法实现...........................................................................................................87.总结...................................................................................................................198.参考文献..............................................

4、............................................................201.问题描述：N皇后问题（n-queenproblem）是一个经典的组合优化问题，也是一个使用回溯法（backtracking）的典型例子。回溯法是一种系统地搜索问题解的方法。为了实现回溯，首先需要为为问题定义一个解空间（solutionspace）,其至少包含问题的一个解（可能是最优解）。我们要从中找出满足问题约束条件的解，即可行解（feasiblesolution）。回溯算法一次扩展一个解，在对部分解进行扩展后，检查到目前为止的解是否为问题的

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

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

7、j–l

8、=

9、i–k

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

11、的值。如果找到了一个合法的放置位置，就进一步测试求得的(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)do6x[k]←x[k]+17ifx[k]≤n//找到一个位置8thenifk=n//测试是否为问题的解9thenoutput(X)