题解 | #N皇后问题#

题解：回溯
首先，每个皇后不能同行，不能同列，不能同斜线。
对于一个3皇后问题，如图：
图片说明

约束条件判断：同行和同列好判断，同斜线判断如图：
图片说明

可以看出斜线约束判断([ (i-1)-(j-1),(i-j),(i+1)-(j+1) ], [ (i+1)+(j-1),(i+j),(i-1)+(j+1) ]
递归函数分析：
递归边界： cur==n 表明每个皇后都已放好
递归过程：尝试这在第cur行的某个位置放皇后 graph[cur] =i, 并判断是否与之前放置的皇后有冲突。如果没有，就去在第cur+1行放置皇后。
回溯：如果有冲突了，将graph[cur] 恢复状态。

复杂度分析:
时间复杂度： $O(N!)$ : 首先每一行有N的位置可以放.
空间复杂度： $O(N)$ : 申请一个数组保存放置状态，且递归栈长度也为N
实现如下：

class Solution {
public:
    /**
     *
     * @param n int整型 the n
     * @return int整型
     */
    void dfs(int n,vector<int>& graph,int cur,int &ans){
        if(cur == n) { ans++; return;}
        for(int i = 0;i<n;i++){
            graph[cur] = i;  //尝试这在i处放
            int ok = 0;
            //与之前放置的冲突否
            for(int j = cur-1;j>=0;j--){
                if(i == graph[j]||graph[j]+j==cur+i||j-graph[j]==cur-i) {ok = 1; break;}
            }
            //当前没有冲突，就开始新的一行
            if(!ok) dfs(n,graph,cur+1,ans);
            //有冲突，回溯，恢复状态
            graph[cur] = -1;
        }
    }
    int Nqueen(int n) {
        // write code here
        int ans = 0;vector<int> graph(n,-1);
        dfs(n, graph, 0, ans);
        return ans;
    }
};

题解二：优化上面的回溯
在上面的每次判断冲突都需要遍历之前的放置的位置，但是观察可以发现每一列可以用一个标志表示这一列以及放置了皇后，同时，斜线上可以用一个标志代表这个斜线上已经有皇后了。
图示:
图片说明

用一个二维数组vis来保存每个标志

复杂符分析：
时间复杂度： $O(N!)$ ,同题解一
空间复杂度： $O(N)$ ，同题解一

实现如下：

class Solution {
public:
    /**
     *
     * @param n int整型 the n
     * @return int整型
     */
    int ans = 0;
    int vis[3][30]={0};
    void dfs(int cur,int n){
        if(cur==n) {++ans;return;}
        for(int i = 0;i<n;i++){
            //判断3个标志
            if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n]){
                vis[0][i] = vis[1][cur+i]=vis[2][cur-i+n] = 1;
                dfs(cur+1,n);
                vis[0][i] = vis[1][cur+i]=vis[2][cur-i+n] = 0; // 回溯
            }
        }
    }
    int Nqueen(int n) {
      dfs(0,n);
      return ans;
    }
};