Non-Attacking Queens

• Time : O(n!)
• Space : O(1)

c++

int helper(int& n, int diag, int rdiag, int down) {
    if(down == ((1<<n) - 1)) return 1;
    else {
        int res = 0;
        int mask = (1<<n) - 1;
        mask &= ~(diag | rdiag | down);
        while(mask) {
            int p = mask & -mask;
            mask -= p;
            res += helper(n, (diag + p) << 1, (rdiag + p) >> 1, down + p);
        }
        return res;
    }
}

int nonAttackingQueens(int n) {
    return helper(n, 0, 0, 0);
}

• Time : O(n!)
• Space : O(1)

c++

using namespace std;
int helper(int& n, int diag, int rdiag, int down) {
    if(down == ((1<<n) - 1)) return 1;
    else {
        int res = 0;
				int mask = (diag | rdiag | down);
				for(int i = 0; i < n; i++) {
					if(mask & (1<<i)) continue;
					res += helper(n, (diag + (1<<i)) << 1, (rdiag + (1<<i)) >> 1, down + (1<<i));
				}
        return res;
    }
}

int nonAttackingQueens(int n) {
    return helper(n, 0, 0, 0);
}