算法分析与设计大作业.docx

算法分析与设计大作业

《回溯法计算皇后跳棋》

班级：

学号：

姓名：

指导老师：

得分：

问题陈述：

在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。要求在n×n格的棋盘上放置n个皇后，任何两个皇后不放在同一行或同一列或同一斜线上。

回溯法基本思想：

回溯算法也叫试探法，它是一种系统地有哪些信誉好的足球投注网站问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：

1、定义一个解空间，它包含问题的解。

2、利用适于有哪些信誉好的足球投注网站的方法组织解空间。

3、利用深度优先法有哪些信誉好的足球投注网站解空间。

4、利用限界函数避免移动到不可能产生解的子空间。

问题的解空间通常是在有哪些信誉好的足球投注网站问题的解的过程中动态产生的，这是回溯算法的一个重要特性

回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明确的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。

算法描述：

Q

Q

Q

Q

Q

Q

Q

Q

01234567

解向量：（x1，x2，···，xn）

显约束：xi=1,2，···，n

隐约束：1）不同列：xi!=xj

2）不处于同一正、反对角线：|i-j|!=|x(i)-x(j)|

解空间：满N叉树

(j,x[j])(i,x[i])

（i,x[i]）(j,x[j])

程序代码：

#includeiostream

#includevector

usingnamespacestd;

classqueen

{

structq_place{

intx,y;

q_place():x(0),y(0){}

};

public:

queen(intqc):q_count(qc),sum_solution(0){

curr_solution.resize(q_count);

}

voidbacktrack(){

_backtrack(0);

}

private:

void_backtrack(intt){

if(t=q_count){

++sum_solution;

for(size_ti=0;icurr_solution.size();++i){

coutx=curr_solution[i].xy=curr_solution[i].yendl;

}

cout解决方案有sum_solution个endl;

}

else{

for(inti=0;iq_count;++i){

curr_solution[t].x=i;

curr_solution[t].y=t;

if(_place(t)){_backtrack(t+1);}

}

}

}

bool_place(intk){

for(inti=0;ik;++i){

if((abs(curr_solution[i].x-curr_solution[k].x)==abs(curr_solution[i].y-curr_solution[k].y))||curr_solution[i].x==curr_solution[k].x)

{returnfalse;}

}

returntrue;

}

private:

vectorq_placecurr_solution;

constintq_count;

intsum_solution;

};

intmain()

{

inti;

cout请输入皇后的个数：endl;

cini;

queenq(i);

cout各个皇后在不同位置时，对应的解决方案个数如下：endl;

q.backtrack();

return0;

}

运行结果：

结论分析：

n后问题主要在于可行解，一个一个的试，（t）能走通就往（t+1）下走，走不通就倒回去（t-1）换条走，再不行再回走。就要不停的尝试，不停地回溯，直到找全可行解，或者一个也没有就停止。还有重要的是约束条件，两个皇后不能在同行同列或者斜线上。这题需要理解程序设计的顺序结构基本思想，掌握顺序结构语句特点。并且学会用算法分析问题，能够使用顺序结构编写简单的程序解决