题意

给定一个$n\ast nn*n$的国际象棋棋盘，求在上面放$nn$个国际象棋中后的方案。

思路

n皇后问题也是一类典型的回溯问题，题目的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在／ 斜线上的行列值之和相同；如果同在＼ 斜线上的行列值之差相同；我们可以建立三个数组来判断某行某列某对角线能否放置皇后，在找到一个方案后进行回溯从而计算所有的方案数目。

代码如下：

class Solution {
public:
#define MAX 30
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int N,ans=0;
    int Nqueen(int n) {
        // write code here
        N=n;
        DFS(1);//开始搜索
        return ans;
    }
    bool use1[MAX]={false},use2[MAX]={false},use3[MAX]={false};//分别表示行列斜线
void DFS(int y)
{
    if (y>N) {ans++; return;}//求出一个方案
    for (int x=1; x<=N; x++)
    {
        if (use1[x]||use2[y-x+N]||use3[y+x])
            continue;//若该行该列该对角线已有皇后则不能放置
        use1[x]=use2[y-x+N]=use3[y+x]=1;
        DFS(y+1);
        use1[x]=use2[y-x+N]=use3[y+x]=0;//回溯
    }
} 
};

复杂度分析

时间复杂度：$O(n!)O(n!)$，回溯算法所用时间。 空间复杂度：$O(n)O(n)$,dfs所用栈空间。