#include <stdio.h>
int board[12][12];//棋盘数组
int cont=0;//记录解的个数
int main()
{
void df(int x,int N);
int n;
scanf("%d",&n);
df(0,n);
printf("%d",cont);
return 0;
}
void df(int x,int N)//递归求解
{
int i,j,t,n=N;
for(i=0;i<N;i++)
{
if(board[x][i]==0)//如果当前位置为0，说明跟之前的几个皇后没有冲突，此位置放一个皇后
{
if(x==N-1)//当查询到最后一行时，解的个数加一，进入下次循环
{
cont++;
continue;
}
else//以皇后为中心的八个方向数值加一
{
for(t=0;t<N;t++)
board[t][i]+=1;
for(j=0;j<N;j++)
board[x][j]+=1;
for(t=x,j=i;j<N,t<N;j++,t++)
board[t][j]+=1;
for(t=x,j=i;j>0,t>0;j--,t--)
board[t][j]+=1;
for(t=x,j=i;j<N,t>0;j++,t--)
board[t][j]+=1;
for(t=x,j=i;j>0,t<N;j--,t++)
board[t][j]+=1;
df(x+1,n);//递归寻找下一个皇后
}//回溯到此之后清空上一个节点所引起的变化
for(t=0;t<N;t++)
board[t][i]-=1;
for(j=0;j<N;j++)
board[x][j]-=1;
for(t=x,j=i;j<N,t<N;j++,t++)
board[t][j]-=1;
for(t=x,j=i;j>0,t>0;j--,t--)
board[t][j]-=1;
for(t=x,j=i;j<N,t>0;j++,t--)
board[t][j]-=1;
for(t=x,j=i;j>0,t<N;j--,t++)
board[t][j]-=1;
}
}
}
