N皇后问题

Problem Description

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排， 同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。 Input 共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。 Output 共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。 Sample Input 1 8 5 0 Sample Output 1 92

10

#include <iostream> #include <math.h> using namespace std; int N; //皇后数 int Queen[11]; //皇后位置，下标表示行数，数值表示列数 int count=0; //不同放置次数 int a[12]; //存放count数 bool check(int x){ //检查当前行之前的行，判断是否有位于同一列的或者同一斜线的 int i; for(i=0;i<x;i++){ if(Queen[x]==Queen[i]||abs(Queen[i]-Queen[x])==abs(x-i)) return false; } return true; } void Nqueen(int n){ //n为当前行数 int i; for(i=0;i<N;i++){ Queen[n]=i; if(check(n)){ if(n==N-1){ count++; return; }else{ Nqueen(n+1); } } } } int main(){ int i,j; for(i=1;i<=10;i++){ count=0; N=i; Nqueen(0); a[i]=count; } while(cin>>j){ if(j==0)     break; else     cout<<a[j]<<endl; } return 0; }