class Solution {

int t = 0;

void findQueens(int dep, int des, int ld, int d, int rd, int valid) {

if (dep == des) {

t ++;

}

int pos = ~ (ld | d | rd) & valid;

while (pos > 0) {

int cur = pos & -pos;

findQueens(dep + 1, des, (ld | cur) << 1, d | cur, (rd | cur) >> 1, valid);

pos ^= cur;

}

}

public int totalNQueens(int n) {

findQueens(0, n, 0, 0, 0, (1 << n) - 1);

return t;

}

}