N皇后报告.doc

2011/2012学年第2学期
“算法分析与设计”上机报告
学院/系
信息工程学院计算机科学系
专业
计算机科学与技术
班级
项目名称
N皇后问题
组长
小组成员
N皇后联动
N皇后联动
N皇后gui
N皇后算法
N皇后算法
N皇后联动
目录
摘要························第3页
关键字·······················第3页
问题描述······················第3页
算法分析······················第3页
伪代码·······················第4页
模块功能实现···················第4页
界面························第 9页
实现功能及其函数················ 第10页
总结·······················第 11页
2011/2012学年第2学期“算法分析与设计”上机报告
N皇后问题
摘要
N皇后问题是八皇后问题的扩展,这是一个经典问题,要求在一个N*N的棋盘上放置N个皇后,且使得每两个皇后之间都不能相互攻击,即它们中的任意两个都不能位于同一行、同一列或者同一对角线上。我们采用位运算的方法,实现了自由选择皇后个数、显示解的个数、显示求得全部解的时间、调整运行速度、暂停程序、显示上一解下一解、单步演示求得第一组解的回溯过程、单步演示执行上一步下一步、暂停单步演示、棋盘显示总区域一定,但是根据输入皇后的大小,会改变小格的大小这十项功能。并且,位运算的方法大大缩短了求解时间,减少程序运行时间。
关键字
N皇后、位运算、回溯、单步显示
问题描述
在一个N*N的棋盘上放置N个皇后,且使得每两个皇后之间都不能相互攻击,即它们中的任意两个都不能位于同一行、同一列或者同一对角线上。
算法分析
这是一个递归过程,程序一行一行地寻找可以放皇后的地方。过程带三个参数,row、ld和rd,分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。以6x6的棋盘为例,假设现在已经递归到第四层,前三层放的子已经标在下图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置,位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来,得到该行所有的禁位,取反后就得到所有可以放的位置(用pos来表示)。第6行后其结果是取出最右边的那个1。这样,p就表示该行的某个可以放子的位置,把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化,每个参数都加上了一个禁位,但两个对角线方向的禁位对下一行的影响需要平移一位。最后,如果递归到某个时候发现row=111111了,说明六个皇后全放进去了,此时程序从第1行跳到第11行,找到的解的个数加一。
伪代码
N—QUEEN(n)
x[1]←0
K←1
While k>0 do
x[k]←x[k]+1
while x[k]<=n & not PLACE(k) do
x[k]←x[k]+1
if x[k]<=n
then if k=n
then output(X)
else k←k+1
x[k]←0
else k←k-1
return
PLACE(k)
i←1
While i<k do
if(x[i]=x[k] or abs(x[i]-x[k])=abs(i-k))
then return (false)
i=i+1
Return (true)
模块功能实现
1 算法实现
该算法采用的采用回溯法进行位运算,达到求解N皇后目的。位运算中先将所有位都置0,当该位置可以放皇后时,将此位置为1,依次类推,直至求出最终结果。该算法的优越之处在于采用位运算既节省了内存,也加快了运行时间,从空间和时间量方面使算法达到优化的目的。
其具体算法及注释如下:
dfs(int row , int ld , int rd , int deep)
{
int i,buf,pos;
if(deep == m_queenNumber) //如果deep==n,表示已经递归到最后一层,且是正确的解
{
if(m_answer<HANG)
{
for(i=0;i<m_queenNumber;i++)
M_allAnswer[m_answer][i] = jilu[i]; //保存解到二维数组
}
m_answer++; //解的个数加1
return ; //得到正确的解后又返回倒数第二层,继续找正确的解,
//倒数第二层找完后,再返回倒数第三层,依次回溯
}