```
public class Solution {
boolean[] plus, minus, column;
int n, ans = 0;
void search(int p) {
if (p == n) {
ans++;
return;
}
for (int i = 0; i < n; i++)
if (!column[i] && !plus[p+i] && !minus[p-i+n-1]) {
column[i] = plus[p+i] = minus[p-i+n-1] = true;
search(p+1);
column[i] = plus[p+i] = minus[p-i+n-1] = false;
}
}
public int totalNQueens(int n) {
plus = new boolean[2*n-1];
minus = new boolean[2*n-1];
column = new boolean[n];
this.n = n;
search(0);
return ans;
}
}
```