算法连载（4）--回溯法之N皇后问题

1.问题描述：在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜角线上。

2.设计思想与分析：
    基本思路：X(j)表示一个解的空间，j表示行数，里面的值表示可以放置在的列数，抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法，当可以放置皇后时就继续到下一行，不行的话就返回到第一行，重新检验要放的列数，如此反复，直到将所有解解出。

#include <iostream.h>
#include <math.h>

/*检查可不可以放置一个新的皇后*/
bool place(int k, int *X)
{
 int i;
 i=1;
 while(i<k)
 {
  if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))
   return false;
  i++;
 }
 return true;
}
/*求解问题的所有解*/
void Nqueens(int n,int *X)
{
 int k;
 
 X[1]=0;k=1;
 while(k>0)
 {
  X[k]=X[k]+1;
 
  while((X[k]<=n)&&(!place(k, X)))
    X[k]=X[k]+1;
 
  if(X[k]<=n)
   if(k==n)
   {
    for(int i=1;i<=n;i++)
    cout<<X[i]<<" ";
    cout<<"\n";
   }
   else
   {
    k=k+1;
    X[k]=0;
   }
   
  else k=k-1;
 }
 
}

void main()
{
 cout<<"|--------------N皇后问题--------------|"<<endl;
 cout<<"|---power by zhanjiantao(028054115)---|"<<endl;
 cout<<"|-------------------------------------|"<<endl<<endl;
 int n;
 int *X;
 int i;
  while(i)
  {
   cout<<"请输入皇后的个数:";
   cin>>n;
   X=new int[n];
   cout<<"问题的解有:"<<endl;
   Nqueens(n,X);
   cout<<"Press<1> to run again"<<endl;
   cout<<"Press<0> to exit"<<endl;
   cin>>i;
  }
 
}

本文地址：http://com.8s8s.com/it/it22385.htm