import java.util.;
public class Solution {
/*
*
* @param n int整型 the n
* @return int整型
*/
int ans=0;
public int Nqueen (int n) {
// write code here
int[][] num=new int[n][n];
dfs(num,0);
return ans;
}
void dfs(int[][] num,int start){
if(start==num.length) {
ans++;
return;
}
for(int i=0;i<num.length;i++){
int flag=0;
for(int j=0;j<start;j++){
if(num[j][i]==1) flag=1;
}
for(int k=0;k<=Math.min(i,start);k++){
if(num[start-k][i-k]==1)
flag=1;
}
for(int k=0;k<num.length;k++){
if(start-k>=0&&i+k<num.length&&num[start-k][i+k]==1)
flag=1;
}
if(flag==0) {
num[start][i]=1;
dfs(num,start+1);
num[start][i]=0;
}
}
}
}