class Solution {

public List<List<String>> solveNQueens(int n) {

List<List<String>> boards = new ArrayList<>();

if(n < 1) return boards;

int col = 0, aDiag = 0, diag = 0;

dfs(n, 0, new ArrayList<>(), boards, col, aDiag, diag);

return boards;

}

private void dfs(int n, int row, List<String> board, List<List<String>> boards,int col, int aDiag, int diag){

//recursion terminator

if(row >= n) {

boards.add(new ArrayList<>(board));

return;

}

//get available spots for the current row

int bits = (~(col | aDiag | diag)) & ((1 << n) - 1);

while(bits > 0){

int p = bits & -bits;

int pos = Integer.toBinaryString(p).length();

char[] boardRow = new char[n];

Arrays.fill(boardRow, '.');

boardRow[n - pos] = 'Q';

board.add(String.valueOf(boardRow));

dfs(n, row + 1, board, boards, col | p, (aDiag | p) << 1, (diag | p) >> 1);

board.remove(board.size() - 1);

bits &= bits - 1;

}

}

}