[数据结构]八皇后问题求解（递归与非递归形式）

 #include <iostream.h>
#include <stdlib.h>
#define True 1
#define False 0
using namespace std;
int nQueen(int*a,int k,int n)
{
int i,j,conflict;
if(k>=n) return True;
for(i=0;i<n;i++)
{
conflict=False;
for(j=0;j<k;j++)
{
if(i==a[j]||(k-j)==(i-a[j])||(k-j)==(a[j]-1))
conflict=True;
}
if(conflict==False)
{
a[k]=i;
if(nQueen(a,k+1,n)==True)
return True;
}
}
return False;
}
void PrintSolution(int*a,int n)
{
int i,j;
char c=2;
char q=5;
cout<<"将Queen放入下列位置："<<endl;
for(i=0;i<n;i++)
{
cout<<"\t行"<<i+1<<"列"<<a[i]+1<<": \t\t ";
for(j=0;j<a[i];j++)
cout<<c;
cout<<"Q";
for(j=a[i]+1;j<n;j++)
cout<<c;
cout<<endl;
}
}
int main()
{
int n,*a;
cout<<"请输入n已确定问题的大小："<<endl;
cin>>n;
if(n>0)
{
a=new int[n];
}
else
{
cout<<"Error!Ivailed Input!"<<endl;
system("pause");
return False;
}
if(nQueen(a,0,n)==True)
{
PrintSolution(a,n);
}
else
cout<<"该问题无解！"<<endl;
delete(a);
system("pause");
return 0;
}
非递归函数：
int nQueen(int *a,int n)
{
int top,i,j,conflict;
if(n<=0) return False;
top=-1;
i=0;
do{
conflict=False;
for(j=0;j<top+1;j++)
if(i==a[j]||(top+1-j)==(i-a[j])||(top+1-j)==(a[j]-1))
conflict=True;
if(conflict==False)
{
a[++top]=i;
if(top==n-1) return True;
i=0;
}
else
{
while(i==n-1&&top>=0)
i=a[top--];
i++;
}
}while(i<n);
return False;
}

C++中的mutable：【上一篇】
C++主题——static类成员：【下一篇】