# Clear and short solution in Java using bit masks [explanation in Mandarin]

• ``````/*
以一行为一个recursion level, 在这一行的每个位置尝试放置queen.
queen不能和*之前*已经放置过的queen在同一列, 同一个对角线.
-- diagonal方向的bit mask size为2 * n - 1, 自上向下(对应从低位到高位)看所在的bit是n - 1 + row - col
-- anti-diagonal方向的bit mask size为2 * n - 1, 自上向下(对应从低位到高位)看所在的bit是row + col
*/
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
if (n <= 0) return ans;
char[][] board = new char[n][n];
for (char[] row: board) Arrays.fill(row, '.');  // initially, all slots empty
dfs(ans, board, 0, 0, 0, 0);
return ans;
}

int n = board.length;
if (row == n) {
List<String> curAns = new ArrayList<>();
for (char[] sArr: board) curAns.add(new String(sArr));
return;
}
for (int col = 0; col < n; ++col) {  // try each position (col) at current level (row)
boolean yValid = (yMask & (1 << col)) == 0;
boolean diagValid = (diagMask & (1 << (n - 1 + row - col))) == 0;
boolean antiDiagValid = (antiDiagMask & (1 << (row + col))) == 0;
if (yValid && diagValid && antiDiagValid) {
board[row][col] = 'Q';
dfs(ans, board, row + 1, yMask | (1 << col), diagMask | (1 << (n - 1 + row - col)),
antiDiagMask | (1 << (row + col)));
board[row][col] = '.';
}
}
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.