# Simple Java solution

• It's very simple column by column tries with DFS. For each column, try every row; for each try point, check if it is safe. When reached level n, print out.

``````List<String[]> list = new ArrayList<String[]>();

public List<String[]> solveNQueens(int n) {
int[][] b = new int[n][n];
dfs(b, 0, n);
return list;
}

public void dfs(int[][] b, int col, int n)
{
if (col == n)
{
return;
}
for (int row = 0; row < n; row ++)
{
if (isSafe(b, row, col, n))
{
b[row][col] = 1;
dfs(b, col + 1, n);
b[row][col] = 0;
}
}
}
public boolean isSafe(int[][] b, int x, int y, int n)
{
for (int i = 0; i < n; i++)
{
if (b[x][i] == 1 || b[i][y] == 1)
{
return false;
}
}
for (int i = 0; i< n; i ++)
for (int j = 0; j < n; j++)
{
if ((i + j == x + y) &&  b[i][j] == 1)
{
return false;
}
}
for (int i = 0; i < n; i++)
{
if (x-i >=0 && y-i >= 0  &&  b[x-i][y-i] == 1)
{
return false;
}
if (x+i < n && y+i < n && b[x+i][y+i] == 1)
{
return false;
}
}
return true;
}``````

• I'm doing the same, except i'm doing per row rather than per column. i found this approach would choak when n== 13 or above. my solution passed OJ, but wonder if there's better solution...

• the isSafe function can be simplified as below:

``````public boolean isSafe (int[][]matrix,  column, int row, int n){

for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==row && matrix[i][j]==1) return false;
if(j==column&& matrix[i][j]==1) return false;
if((Math.abs(row-i)==Math.abs(column-j))&&(matrix[i][j]==1)) return false;
}
}
return true;

}``````

• I use same idea, but instead of using a two-dimension array, I use an one-dimension array plus a hash set to speed it up. Notice, we can't have two queue in same row or in same queue. So using one-dimension array is enough to express the queue position, every value in the array represent the column of the queue in this row. So if the queue[i] = j; it means queue in ith row is in jth column. Instead of trying every column from 0 ~ n, I use a hash set to store the 0 ~n value, if we set a queue to kth column, we remove k from the set, other queues can only choose column among the rest elements in the set.

• you can reduce auxillary space of O(n^2) to O(n) in your dfs function
instead of doing b[row][col]=1 , do b[row]=col;

• I tried 13, it has 73712 solution.

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