回溯法解决N皇后问题Java代码实现_N皇后问题能用贪心算法资源-CSDN文库

回溯法

5星 · 超过95%的资源需积分: 44 49 浏览量 2013-04-29 22:08:03 上传评论 4 收藏 183KB DOC 举报

资源推荐

资源详情

资源评论

N 皇后问题

1. 问题描述...........................................................................................................3

2. 算法分析...........................................................................................................3

3. 伪代码...............................................................................................................4

4. 演示程序设计...................................................................................................5

5. 演示界面...........................................................................................................5

6. 算法实现...........................................................................................................8

7. 总结...................................................................................................................19

8. 参考文献.......................................................................................................... 20

1. 问题描述：

N 皇后问题（n-queen problem）是一个经典的组合优化问题，也是一个

使用回溯法（backtracking）的典型例子。回溯法是一种系统地搜索问题解

的方法。为了实现回溯，首先需要为为问题定义一个解空间（ solution

space）,其至少包含问题的一个解（可能是最优解）。我们要从中找出满足

问题约束条件的解，即可行解（feasible solution）。回溯算法一次扩展一个

解，在对部分解进行扩展后，检查到目前为止的解是否为问题的一个解，

如果是，则输出；否则，检查是否可以继续扩展。如果可以，则继续扩展；

否则，删除最后添加的元素，尝试当前位置是否有另一元素。若没有合法

的扩展方式，则进行回溯（backtrack）。

N 皇后问题要求在一个 n×n 的棋盘上放置 n 个皇后，且使得每两个皇后

之间都不能相互攻击，即它们中的任意两个都不能位于同一行、同一列或

者同一对角线上。这次的任务就是借助 GUI 实现 N 皇后问题的动态演示。

我们设定皇后个数在四个到八个之间可选，所选编程语言为 JAVA。

2. 算法分析：

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 的值。如果找到了一个合法的放置位置，就进一步测试

剩余19页未读，继续阅读

评论收藏

内容反馈

zzxxccnngghh

2014-05-18

写的简单明了。。还不错
WTT_2

2015-04-07

为什么我没懂得怎么用呢？
娜_么爱你

2014-05-22

如果能把界面优化一下，会更棒的
晴一一

2014-05-19

对算法分析课程的学习很有帮助
青青河边草1234567890

2016-01-28

不错的思路

Astro门

粉丝: 0
资源: 4

回溯法解决N皇后问题 Java代码实现

最新资源

回溯法解决N皇后问题 Java代码实现

回溯法解决N皇后问题

用回溯法实现n皇后问题(java源码)

用回溯法求解N皇后问题

利用回溯法求解n皇后问题

N皇后问题-java实现

NQueen N皇后问题java实现

回溯法求N皇后问题

回溯法---n皇后问题，c语言编程

回溯法解决N皇后问题（以四皇后为例）

用Java编写的八皇后问题

回溯法解决n皇后问题

利用回溯法解决n皇后问题

回溯解决N皇后问题

回溯算法实现N皇后问题

回溯法实现N皇后问题

回溯法实现n后问题

n后问题回溯算法 java

n皇后问题回溯法

n皇后问题java解

n 皇后问题n 皇后 回溯法n 皇后 回溯法

n后问题（回溯法）

用回溯法解决八皇后问题C语言实现

Java编写的N皇后问题

n皇后问题的最简单解决方案

回溯算法实现5皇后问题

回溯法解决皇后问题

四皇后问题-回溯实现

八皇后问题的回溯法实现

N后问题（回溯法）

Java 回溯法解8皇后问题

最新资源

n 皇后问题n 皇后回溯法n 皇后回溯法