xmu1008 皇后问题

时间：2010-05-05 来源：hbj_2008

n皇后问题
很有名的一个问题。大致意思是在一个n×n的棋盘上，有n个棋子，两个棋子不能在同一条直线上，总共有多少种排列，并给出其中的一种排列。
在算法书上看到一个算法，是利用回溯法。定义Queen这个类，并在类中定义了一个友元函数、位置判断函数--判断位置k与前k-1个位置是否冲突，回溯函数--对总体情况进行处理。
下面的是一个递归算法，也可以修改一下，变成非递归算法，更节约空间。

#include<iostream>
#include<cstdlib>
#include<cmath>
int point[14]={0} ;
using namespace std ;

class Queen{
      friend int nQueen(int);
      private:
         void backtrack(int);
         bool queenplace(int);
         int number ;
      public:
         int * a ;
         int sum ;
         };
bool Queen::queenplace(int k)
//检验皇后k与前k-1皇后是否冲突
{

     bool flag =true;
     for(int i=1;i<k;i++)
      if((abs(i-k)==abs(a[i]-a[k]))||(a[i]==a[k]))
      { flag=false ;
           break;
      }

     return flag ;
}
void Queen::backtrack(int k)
//递归，依次往后检验
{
     if(k>number)
     {
                  sum++;
                  for(int i=1;i<=number;i++)
                  point[i]=a[i];
     }
     else
         for(int i=1;i<=number;i++)
         {
                 a[k]=i;
                 if(queenplace(k)) backtrack(k+1);
         }
}
int nQueen(int n)
{
    Queen T ;
    T.number = n ;
    T.sum = 0 ;
    int *p = new int[n+1];
    int *pp= new int[n+1];
    for(int i=0;i<=n;i++)
            p[i]=0;
    T.a=p;
    T.backtrack(1);
    delete[] p ;
    delete[] pp ;
    return T.sum ;
}

int main()
{
    int n ;
    int rezult ;
    cin>>n ;
    Queen T ;
    rezult = nQueen(n);
    cout<<rezult<<endl;
    for(int i=1;i<=n;i++)
    cout<<i<<" "<<point[i]<<endl;
    system("pause");
    return 0 ;
}