# Concise JAVA solution based on DFS

• Explanation

The basic idea is to check possible columns row by row based on DFS: If the column is already used or the column is on 45° /135° diagonals with the placed queens, then ignore it, otherwise place a queen on it and keep DFS procedure. As the following:

``````public List<List<String>> solveNQueens(int n) {
int[] usedCols = new int[n];// usedCols[i]: Column of the queen in row i
Arrays.fill(usedCols, -1);
DFS(usedCols, 0, res);
return res;
}

void DFS(int[] usedCols, int row, List<List<String>> res) {
int n = usedCols.length;
if (row == n) {
return;
}

// Check Possible columns for the inputed row.
for (int col = 0; col < n; col++) {
if (isValid(usedCols, row, col)) {
usedCols[row] = col;
DFS(usedCols, row + 1, res);// Move on to the next row
}
}
}

// Check if the column is valid to place queen for the row.
boolean isValid(int[] usedCols, int row, int col) {
for (int i = 0; i < row; i++) {
// Excludes used columns and diagonal positions
// (x2-x1)/(y2-y1) == 1 or -1
if (usedCols[i] == col || row - i == Math.abs(col - usedCols[i]))
return false;
}
return true;
}

List<String> drawGrids(int[] usedCols) {