**Explanation**

The basic solution is similar as N-Queens, the difference is using HashSet to validate column, instead of for loop. In this way, it will improve validation time complexity from O(n) to O(1). Another trick is diagonal checking: 1) 45° diagonal=>y1-y2=x1-x2=>y1-x1=y2-x2; 2) 135° diagonal=>y1-y2=-1*(x1-x2)=>y1+x1=y2+x2. Thanks for this great idea from Alex, DFS solution as the following:

```
HashSet<Integer> cols = new HashSet<Integer>(); // Used columns
HashSet<Integer> diag1 = new HashSet<Integer>(); // 45° diagonal
HashSet<Integer> diag2 = new HashSet<Integer>(); // 135° diagonal
public int totalNQueens(int n) {
return DFS(0, 0, n);
}
int DFS(int row, int count, int n) {
if (row == n)
return count + 1;
for (int col = 0; col < n; col++) {
if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col))
continue;
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
count = DFS(row + 1, count, n);
cols.remove(col);
diag1.remove(row - col);
diag2.remove(row + col);
}
return count;
}
```