新建 文本文档.txt

这是一个N皇后问题

#include <iostream.h>
#include <stdio.h>
#include <math.h>
#include <dos.h>
enum bool{false, true};
class Queen{
  friend int nQueen(int);
  private:
    inline bool Place(int k);
    void Backtrack(void);
    int n, *x;
    long sum;
};
inline bool Queen::Place(int k)
{
  int j;
  for (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(void)
{
  x[1] = 0;
  int k = 1;
  while (k > 0){
    x[k] += 1;
    while ((x[k] <= n) && !(Place(k)))
      x[k] += 1;
    if (x[k] <= n)
      if (k == n)
sum++;
      else {
k++;
x[k] = 0;
      }
    else
      k--;
  }
}

int nQueen(int n)
{
  Queen 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();
  delete []p;
  return X.sum;
}
int main()
{
  int n;
  struct time t1, t2; //取系统时间.
  gettime (&t1);
  cout << "input n = ";
  cin >> n;
  cout << nQueen(n) << endl;
  gettime (&t2);
  cout << (t2.ti_sec - t1.ti_sec) + (t2.ti_hund-t1.ti_hund)*1.0/100;
  return 0;
}