void backtrack(int t){
if(t>n)
{
printf("第"%d"个解的答案为:",k);
k++;
sum++;
for(int i=1;i<=n;i++)printf("%d",x[i]);
}
else
{
for(int i=1;i<=n;i++)
{
x[t]=i;
if(place(t)) {
backtrack(t+1);
}
}
}
}
main(){
int nn;
printf("输入n皇后n值:");
scanf("%d %d",&n,&n);
nQueen(nn);
}
江西理工大学
《算法分析与设计》课实验报告
实验三贪心及回溯法
专业班级实验人学号
实验日期同组人
一、实验目的
1.掌握能用回溯法求解的问题应满足的条件;
2.加深对回溯法算法设计方法的理解与应用;
3.锻炼学生对程序跟踪调试能力;
4.通过本次实验的练习培养学生应用所学知识解决实际问题的能力。
二、实验内容
由N2个方块排成N行N列的正方形,称为N元棋盘,在N元棋盘上放置N个皇后,如果某两个皇后位于N元棋盘的同一行或同一列或同一斜线(斜率为±1)上,则称它们在互相攻击,试设计算法找出使N个皇后互不攻击的所有布局。
三、实验要求
(1)用回溯法算法设计方法求解N元皇后问题
(2)找出N皇后问题的互不攻击的所有解
(3)皇后数N由键盘动态输入
(4)上机实现所设计的算法;
(5)分析所设计的算法的时间/空间复杂性。
四、实验过程设计(算法设计过程)
(1)分析N皇后问题的约束条件,并将其显示化,选择存储结构建立相应的数学模型;(2)根据所建立的数学模型,设计求解该问题的粗略算法;
(3)对所设计的粗略算法求精,得具体算法;
(4)在C/C++/VC++下实现所设计的算法;
(5)分屏显示结果;
(6)分析运行结果的正确性;
(7)进行算法效率分析;
(8)课后写出实验报告。
五、实验结果和分析
六、实验体会
通解n后问题主要在于可行解,一个一个的试,(t)能走通就往(t+1)下走,走不通就倒回去(t-1)换条走,再不行再回走。就要不停的尝试,不停的回溯,直到找全可行解,或者一个也没有就停止。还有重要的事约束条件,两个皇后不能在同行同列或者斜线上。
七、附录:(源代码)#include "iostream.h"
#include "string.h"
#include
int n;
int sum=0;
int k=1;
int nQueen(int nn)
{
n=nn;
void backtrack(int t);
for(int i=0;i<=n;i++)
{
x[i]=0;
}
backtrack(1);
return sum;
}
int place(int k)
{
for(int j=1;j { if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) { return 0; }