算法分析与设计大作业

算法分析与设计大作业

《回溯法计算皇后跳棋》

班级： 学号：

姓名：

指导老师：

得分：

一、 问题陈述：

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

二、 回溯法基本思想：

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：

1、定义一个解空间，它包含问题的解。 2、利用适于搜索的方法组织解空间。 3、利用深度优先法搜索解空间。

4、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性

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

三、 算法描述：

Q Q Q Q Q Q Q Q 0 1 2 3 4 5 6 7 解向量：（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]) 四、 程序代码： #include #include using namespace std; class queen {

struct q_place{ int x,y;

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

queen(int qc):q_count(qc),sum_solution(0){ curr_solution.resize(q_count); }

void backtrack(){ _backtrack(0); } private:

void _backtrack(int t){

if(t >= q_count){

++sum_solution;

for(size_t i=0;i

cout<<\= \y =

\ }

bool _place(int k){

if((abs(curr_solution[i].x-curr_solution[k].x)==abs(curr_solution[ifor(int i=0;i

for(int i=0;i

curr_solution[t].x = i; curr_solution[t].y = t; if(_place(t)){_backtrack(t+1);} }

cout<<\解决方案有\个\

].y-curr_solution[k].y))||curr_solution[i].x==curr_solution[k].x) } }

return true; {return false;}

本文来源：https://www.bwwdw.com/article/vkqt.html