题解 | #N皇后问题#

#include <bits/types/FILE.h>
class Solution {
  public:
    /**
     *
     * @param n int整型 the n
     * @return int整型
     */
    int arr[10][10];
    int ans = 0;
    int tmp = 0;
    int N;
    int Nqueen(int n) {
        N = n;
        backTrack(0);
        return ans;
    }
    void backTrack(int r) {
        if (r == N && tmp == N) {
            ans++;
            return;
        }
        for (int i = 0; i < N; i++) {
            if(islegal(r, i)){
                arr[r][i]=1;
                tmp++;
                backTrack(r+1);
                tmp--;
                arr[r][i]=0;
            }
        }
    }
    bool islegal(int r, int c) {
        for (int i = r - 1; i > -1; i--)
            if (arr[i][c] == 1)return 0;
        int i = r, j = c;
        while (i > -1 && j > -1) {
            if (arr[i][j] == 1)return 0;
            i--;
            j--;
        }
        i = r, j = c;
        while (i > -1 && j < N) {
            if (arr[i][j] == 1)return 0;
            i--;
            j++;
        }
        return 1;
    }
};