# Straight forward Ans, DFS, Java

• Place queen row by row, mark vertical and diagonal lines that can not be used for next row.

``````public class Solution {
public List<String[]> solveNQueens(int n) {
char[][] board=new char[n][n];
for(int i=0; i<n; i++)
Arrays.fill(board[i],'.');
boolean[] lineUsed=new boolean[5*n];
placeQueen(0,board, lineUsed, rst);
return rst;

}

public void placeQueen(int row, char[][] board, boolean[] lineUsed,List<String[]> rst){
int n=board.length;
if(row==n){
String[] sol=new String[board.length];
for(int i=0; i<n; i++)
sol[i]=new String(board[i]);
return;
}
for(int i=0; i<n; i++){
//i:0~n-1 marks vertical lines that has been used,
//row-i+2*n: -(n-1)+2n~(n-1)+2n -> n+1~3n-1 marks diagonals leftUp to rightDown
//row+i+3*n : 3n~5n-2 marks diagonals rightUp to leftDown
if(lineUsed[i] || lineUsed[row-i+2*n] || lineUsed[row+i+3*n]) continue;
board[row][i]='Q';
lineUsed[i]=true;
lineUsed[row-i+2*n]=true;
lineUsed[row+i+3*n]=true;
placeQueen(row+1,board,lineUsed,rst);
board[row][i]='.';
lineUsed[i]=false;
lineUsed[row-i+2*n]=false;
lineUsed[row+i+3*n]=false;
}
}
}``````

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