n皇后问题：在N行N列的棋盘上放置不能互相攻击的N个皇后。根据国际象棋规则，处在同一行或同一列或同一斜线上的皇后可以互相攻击。N皇后问题的解满足以下条件：棋盘每行均放置一个皇后，且任何2个皇后不在同一列，也不在同一斜线上。
#include <stdio.h> #include <math.h> class Queen { friend int nQueen(int); private: bool Place(int k); void Backtrack(int t); int n,*x; long 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(int t) { if (t>n) { sum++; } else { for (int i=1; i<=n; i++) { x[t]=i; if (Place(t)) Backtrack(t+1); } } } 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(1); delete[] p; return X.sum; } int main() { int x,y; x=8; y=nQueen(x); printf("sum=%d\n",y); return 0; }