queen.cpp

算法设计:著名的n后问题:在nXn的棋盘上放彼此不受攻击的n个皇后,按国际象棋的规则,任何2个皇后不在同一行或同一列或同一斜线上. 本算法才用回朔法来解决.

#include <math.h>
#include <iostream.h>
#include <fstream.h>
class Queen
{friend nQueen(ofstream&,int);
 private:
     bool Place(int);
     void Backtrack(ofstream&); 
     int n,  // 皇后数
        *x,  // 当前解
       sum;  // 当前已找到的可行解数
};

bool Queen::Place(int k)
{ for(int j=1; j<k; j++)
   if((abs(k-j)==abs(x[j]-x[k])) || x[j]==x[k]) return false;
 return true; 
}
void Queen::Backtrack(ofstream& out)
{ int k=1;   x[1]=0;
  while(k>0)
   { x[k] += 1;
     while((x[k]<=n) && !(Place(k))) x[k] += 1;
     if(x[k]<=n)
       if(k==n){ sum++; for(int i=1; i<=n; i++)out<<"  "<<x[i];  out<<endl;  }
       else { k++; x[k]=0;  }
     else k--;
   }
}
int nQueen(ofstream& out,int n)
{  Queen X;
 // initialize X 
 X.n = n;   X.sum = 0;  
 int *p = new int[n+1];   
 for(int i=0; i<=n; i++) p[i]=0;
 X.x = p;   X.Backtrack(out);
 delete[] p;  
 return X.sum;
}
void main(void)
{  int n; 
   ofstream out("QueenOUT.dat");
   cout<<" Please input n= ";   cin>>n; out<<" n= "<<n<<endl;
   out<<"\nThe number of solution Queen is "<<nQueen(out,n)<<endl;
   out.close(); 
}