文档介绍：用回溯法求解n皇后问题
学号:1202121463
姓名:程园
回溯法的基本思想
回溯法的基本思想是在问题的解空间树上按深度优先搜索策略,从根节点出发搜索整个解空间。搜索过程中,每到达一个结点时,则判断该结点为根的子树是否含有问题的解,如果可以确定该子树中不含有问题的解,则放弃对该子树的搜索,逐层向其祖先节点回溯。否则,进入该子树。
n皇后问题描述
在nxn的棋盘上放置彼此不受攻击的n个皇后。任何2个皇后不能放在同一行、同一列、同一对角线上。
分析问题
我们从第一行开始放皇后,第一行有n个位置可以放,我们用x[1]来表示第一行的皇后所在的列,第二行有n-1个位置可以放,我们用x[2]来表示第二行皇后所在的列······因此,我们用一个数组x[n]来表示问题的解,x[i]表示皇后i放在第i行第x[i]列。
x[i]≠x[j],i≠j
分析问题
问题分析
分析问题
如何保证任何两个皇后不再一条斜线上?设两个皇后q1和q2放在(i,j)和(k,l)位置上,如果q1和q2在斜率为-1的对角线上,那么i - j = k - l成立,如果在斜率为1的对角线上,那么
i + j = k + l成立,由此可知只要
| i - k | ≠| j - l |成立,q1和q2就不再同一条斜线上。
| i - k | ≠| j - l |
问题分析
分析问题
用完全n叉树表示解空间,现在以n=4为例:
问题分析
1
×
×
×
×
×
×
√
√
×
分析问题
//求解的递归函数
void Queen(int i,int n)
{
if(i>n)
Output();
else
{
for(int j=1;j<=n;++j) // j代表列值
{
int k=1;
x[i]=j;//重新换一个列值,这里就是体现回溯的地方
while(k<i)
{
if((x[k]-x[i])*(abs(x[k]-x[i])-abs(k-i))!=0)
c程序实现
分析问题
{
k++;
if(k==i) //到目前为止该解合法
Queen(i+1,n);//搜索下一层
}
else
{
break; //跳出while循环
}
}
}
}
}
c程序实现
分析问题
运行结果
分析问题
谢谢
c程序实现