For each position on the board, it's easy to check row and column, for the two diagonals, if two positions are at the same diagonal then there must have x1+y1 = x2 + y2 or x2 - x1 = y2 - y1. We can use an boolean array col to remember whether current column is valid to put a queen, and as for the row, we can do the backtracking recursively row by row.

```
public class Solution {
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
board[i][j] = '.';
}
boolean[] col = new boolean[n];
boolean[] diagonal_1 = new boolean[2*n-1]; //x1 + y1 = x2 + y2, we have 2*n-1 such diagonals
List<List<String>> res = new ArrayList<>();
backtrack(res, 0, board, col, diagonal_1);
return res;
}
public void backtrack(List<List<String>> res, int row, char[][] board, boolean[] col, boolean[] diagonal_1) {
if(row == board.length) {
List<String> ans = new ArrayList<>();
for(int i = 0; i < board.length; i++)
ans.add(String.valueOf(board[i]));
res.add(ans);
return;
}
for(int j = 0; j < board.length; j++) {
if(!col[j] && !diagonal_1[row+j] && checkDiagonal_2(board, row, j)) {
board[row][j] = 'Q';
col[j] = true;
diagonal_1[row+j] = true;
backtrack(res, row+1, board, col, diagonal_1);
board[row][j] = '.';
col[j] = false;
diagonal_1[row+j] = false;
}
}
}
/* check the diagonal which has the feature x1 - x2 = y1 - y2 */
public boolean checkDiagonal_2(char[][] board, int x, int y) {
int min = Math.min(x, y);
x -= min;
y -= min;
while(x < board.length && y < board.length) {
if(board[x++][y++] == 'Q')
return false;
}
return true;
}
```

}