1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #include<queue>
5 using namespace std;
6 const int maxn = 21;
7 const int inf = INT_MAX;
8 int r[ maxn ],c[ maxn ],sd[ maxn ],md[ maxn ];//sd=r+c,md=r-c+n-1;
9 int ans,n;
10 void init(){
11 memset( r,0,sizeof( r ));
12 memset( c,0,sizeof( c ));
13 memset( sd,0,sizeof( sd ));
14 memset( md,0,sizeof( md ));
15 ans=0;
16 }
17
18 void dfs( int x,int y,int sum ){
19 if( sum==n ) {
20 ans++;
21 return ;
22 }
23 for( int i=x;i<n;i++ ){
24 for( int j=0;j<n;j++ ){
25 if( r[ i ]==1||c[ j ]==1||sd[ i+j ]==1||md[ i-j+n-1 ]==1 ) continue;
26 r[ i ]=c[ j ]=sd[ i+j ]=md[ i-j+n-1 ]=1;
27 dfs( i,j,sum+1 );
28 r[ i ]=c[ j ]=sd[ i+j ]=md[ i-j+n-1 ]=0;
29 }
30 }
31 }
32
33 int main(){
34 int aa[12]={0};
35 aa[10]=724;
36 while( scanf("%d",&n)==1 && n ){
37 if( aa[n]!=0 ){
38 printf("%d\n",aa[n]);
39 continue;
40 }
41 init();
42 dfs( 0,0,0 );//x,y,sum
43 aa[n]=ans;
44 printf("%d\n",aa[n]);
45 }
46 return 0;
47 }
View Code
