回朔算法
在程序设计中,有这样一类问题:求一类解,或求全部解,或求最优解的问题(例如八皇后问题),不是根据某种确定的算法设计法则,而是利用试探和回朔的搜索技术求解.
回朔还是设计递归算法的重要方法,其求解过程实质:是一个先序遍历一棵"状态树"但是这棵树不是在遍历前预先建立的,而是隐含在遍历过程中.
为了应用回朔，所求的解必须能表示成一个n元组（x1，x2，…，xn），其中xi是取自某个有穷集si．下面给出n皇后的程序代码，给出代码前先描述问题：在一个n×n的棋盘上放置n个皇后，且使得每两个皇后之间不能相互＂攻击＂也就是使得每两个不在同一行，同一列及同一斜角线．（经典问题八皇后问题）
#include<iostream.h>
#include<math.h>
int sum=0;//用于统计解的个数
int n;／／表示皇后的个数
int *x;／／解向量
bool place(int k)／／判断是否能放置
{ //cout<<"begin place";
for(int j=1;j<k;j++)／／若j＝＝k则同行
if(abs(k-j)==abs(x[j]-x[k])||x[j]==x[k])／／abs(k-j)==abs(x[j]-x[k])表示在斜对角线
／／x[j]==x[k]表示在同一列
return false;
return true;
}
void backtract＿queen(int t)
{
if(t>n)
{／／一次求解完成，计数器加一，并将该组解输出
sum++;
for(int i=1;i<=n;i++)
cout<<x<<" ";
cout<<endl;
}
else
for(int i=1;i<=n;i++)
{
x[t]=i;
if(place(t)) backtract(t+1);／／递归调用
}
}
void main()
{
cout<<"input the number of queen:";
cin>>n;
x=new int[n];
backtract_queen(1);
cout<<"sum="<<sum<<endl;
cout<<"edn
";
}