N皇后问题

N皇后问题

const int N = 15;
class Solution {
public:
    int ans = 0;
    int d1[N][N];
    bool check(int x,int y,int n) {
        for (int i = 0;i < x;i++) {
            if (d1[i][y] == 1) {
                return false;
            }
        }
        int k = min(x,y);
        for (int i = 1;i <= k;i++) {
            if (d1[x-i][y-i] == 1) {
                return false;
            }
        }
        k = min(x,n-y-1);
        for (int i = 1;i <= k;i++) {
            if (d1[x-i][y+i] == 1) {
                return false;
            }
        }
        return true;
    }
    void dfs(int x,int n) {
        if (x == n) {
            ans++;
            return ;
        }
        for (int i = 0;i < n;i++) {
            if (check(x,i,n)) {
                d1[x][i] = 1;
                dfs(x+1,n);
                d1[x][i] = 0;
            }
        }
    }
    int totalNQueens(int n) {
        dfs(0,n);
        return ans;
    }
};