题解 | #N皇后问题#

#include <array>
class Solution {
public:
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int Nqueen(int n) {
        // write code here
        int ans = 0;
        search(ans,0,n);
        return ans;
    }
    void search(int &ans, int cur, int n){
        if(cur == n){
            ans++;
            return ;
        }
        for(int i = 0;i < n;i++){
            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;
                search(ans,cur+1,n);
                vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;
            }
        }
    }
    array<array<int,20>,3> vis = {};
};

代码核心思路是每一行考虑每一列能不能放这一行的皇后。所以要判断这一列皇后放的时候和前面放的皇后会不会列冲突，主对角线冲突，副对角线冲突。在同一条主对角线的元素有的特点是y-x相同，在同一条副对角线的元素的特点是x+y相同。这里使用了一个辅助全局数组，vis, vis[0][i]表示第i列是否被占用，vis[1][cur+i]表示（cur,i)这个位置所在的副对角线有没有被占用，vis[2][cur-i+n]表示(cur,i)这个位置所在的主对角线有没有被占用，+n是为了消除可能产生的负数。