#include <iostream.h>
#include <math.h>
//x[i] represent to  Queen i place in row i group x[i]
void backtrack(int t);
int const n=4;//the number of queen
int x[n+1];   // the solution
int sum=0;    //teh number of the solution

int nQueen()
{
 for(int i=0;i<=n;i++)
  x[i]=0;
 backtrack(1);
 return sum;
}

bool placesafe(int k)
{
 for(int j=1;j<k;j++)
   if( abs(k-j)==abs(x[j]-x[k]) || (x[j]==x[k]) )//the slope is 1 or -1,or in the same group
    return false;
   return true;
}

void backtrack(int t)
{
 if(t>n)
 {
  sum++;
   for(int j=1;j<=n;j++)
  {
   cout<<j<<","<<x[j]<<"#";
  }
  cout<<endl;
 }
 else
  for( int i=1;i<=n;i++)
  {
   x[t]=i;
   if( placesafe(t) )
    backtrack(t+1);
  }
}

int main()
{
 cout<<nQueen()<<endl;
 return 0;
}

评论