n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输入：n = 4 输出：2 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 9
分析：本质上和51题 N 皇后 I 没有区别。依然是生成 n 位数的全排列，在生成的过程中判断这个序列是否满足要求。
如何生成这样的序列？不妨设当前要生成序列的第index位。用flag数组标记数字是否被使用，每次枚举还没有用过的数字，把它放到index位上，同时递归地生成下一位。当index=n时，说明已经生成了一个序列，此时判断是否满足N皇后的条件。
int flag[15],num[15],t;
void getnum(int index,int n)
{if(index==n){t++;return;}for(int i=1;i<=n;++i){if(flag[i]==0){int f=1;if(index>=1)for(int j=index-1;j>=0;--j)if(abs(index-j)==abs(i-num[j])){f=0;break;}if(f){num[index]=i,flag[i]=1;getnum(index+1,n);//注意每次生成完了要复原状态num[index]=0,flag[i]=0;//因为要生成所有的序列}}}
}
int totalNQueens(int n) {t=0;getnum(0,n);return t;
}