bool check_2 (int a[ ],int n)
{//多次被调用，只需一重循环
for(int i=1;i<=n-1;i++)
{
if((abs(a[i]-a[n])==n-i)||(a[i]==a[n]))
return false;
}
return true;
}
void queens_2()
{
int a[9];
int count = 0;
for(a[1]=1;a[1]<=8;a[1]++)
{
for(a[2]=1;a[2]<=8;a[2]++)
{
if (!check_2(a,2)) continue;
for(a[3]=1;a[3]<=8;a[3]++)
{
if (!check_2(a,3)) continue;
for(a[4]=1;a[4]<=8;a[4]++)
{
if (!check_2(a,4)) continue;
for(a[5]=1;a[5]<=8;a[5]++)
{
if (!check_2(a,5)) continue;
for(a[6]=1;a[6]<=8;a[6]++)
{
if (!check_2(a,6)) continue;
for(a[7]=1;a[7]<=8;a[7]++)
{
if (!check_2(a,7)) continue;
for(a[8]=1;a[8]<=8;a[8]++)
{
if (!check_2(a,8))
continue;
else
{
for(int i=1;i<=8;i++)
{
cout<<a[i];
}
cout<<endl;
count++;
}
}
}
}
}
}
}
}
}
cout<<count<<endl;
}
void main()
{
queens_2();
}
n此算法可读性很好，体现了“回溯”。但它只针对八皇后问题，解决任意的n皇后问题还要修改程序结构。如果要解决n皇后的问题，就需要将n作为参数传递给函数，函数需要重写来实现回溯（不能采用级联的for循环，n不确定）；从另一方面，程序中出现了大量的for循环，而且for中的函数结构很相似，自然想到的是递归迭代回溯。这就是回溯比较常用的两种实现方法：非递归回溯和递归回溯。
非递归回溯的程序实现：
void backdate (int n)
{
int count = 0;
int a[100];
int k = 1;
a[1]=0;
while(k>0)
{
a[k]=a[k]+1;//对应for循环的1~n
while((a[k]<=n)&&(!check_2(a,k)))//搜索第k个皇后位置
{
a[k]=a[k]+1;
}
if(a[k]<=n)//找到了合理的位置
{
if(k==n )
{//找到一组解
for(int i=1;i<=8;i++)
{
cout<<a[i];
}
cout<<endl;
count++;
}
else
{
k=k+1;//继续为第k+1个皇后找到位置，对应下一级for循环
a[k]=0;//下一个皇后一定要从头开始搜索
}
}
else
{
k=k-1;//回溯,对应执行外内层for循环回到更上层
}
}
cout<<count<<endl;
}
void main()
{
backdate(8);
}
这样也可以得到，8皇后问题的92中结果。更简单、可读的方法是采用递归的方式，如下：
int a[100], n, count;
void backtrack(int k)
{
if (k>n)//找到解
{
for(int i=1;i<=8;i++)
{
cout<<a[i];
}
cout<<endl;
count++;
}
else
{
for (int i = 1;i <=n; i++)
{
a[k] = i;
if (check_2(a,k) == 1)
{backtrack(k+1);}
}
}
}
void main()
{
n=8,count=0;
backtrack(1);
cout<<count<<endl;
}
可见，递归调用大大减少了代码量，也增加了程序的可读性。给出其中的一个解，如下：
