# Accepted Java Solution

• ``````/**
* don't need to actually place the queen,
* instead, for each row, try to place without violation on
* col/ diagonal1/ diagnol2.
* trick: to detect whether 2 positions sit on the same diagnol:
* if delta(col, row) equals, same diagnol1;
* if sum(col, row) equals, same diagnal2.
*/
private final Set<Integer> occupiedCols = new HashSet<Integer>();
private final Set<Integer> occupiedDiag1s = new HashSet<Integer>();
private final Set<Integer> occupiedDiag2s = new HashSet<Integer>();
public int totalNQueens(int n) {
}

private int totalNQueensHelper(int row, int count, int n) {
for (int col = 0; col < n; col++) {
if (occupiedCols.contains(col))
continue;
int diag1 = row - col;
if (occupiedDiag1s.contains(diag1))
continue;
int diag2 = row + col;
if (occupiedDiag2s.contains(diag2))
continue;
// we can now place a queen here
if (row == n-1)
count++;
else {
count = totalNQueensHelper(row+1, count, n);
// recover
occupiedCols.remove(col);
occupiedDiag1s.remove(diag1);
occupiedDiag2s.remove(diag2);
}
}

return count;
}``````

• Smart solution. The way to classify diagonal cells is impressive! And also votes for your good code.

• This post is deleted!

• Thanks for solution-sharing. very impressive solution, especially the notation of diagonal1 and diagonal2.

• Why does this function stop when ( row > = n)

• Thanks for sharing. Here is a similar idea but shorter and slightly different version.

``````public class Solution {
int result = 0;
public int totalNQueens(int n) {
boolean[] column = new boolean[n];
boolean[] dia45 = new boolean[2 * n - 1];
boolean[] dia135 = new boolean[2 * n - 1];
helper(0, n, column, dia45, dia135);
return result;
}
private void helper(int row, int n, boolean[] column, boolean[] dia45, boolean[] dia135) {
if (row == n) {
result++;
return;
}
for (int col = 0; col < n; col++) {
if (!column[col] && !dia45[col + row] && !dia135[n - 1- row + col]) {
column[col] = dia45[col + row] = dia135[n - 1- row + col] = true;
helper(row + 1, n, column, dia45, dia135);
column[col] = dia45[col + row] = dia135[n - 1- row + col] = false;
}
}
}
}``````

• vote for your comment, and the solution is very smart, we needn't place indeed. thanks.
for a explanation , in the 45 diag lines col - row are always same , and in 135 drag lines col + row are always same , so we can put then in a set.

Also I have a question, in c++ , I should pass count in the form int &count, so the recursive function can influence the count, how can you pass the count in the form int count, in java, the count should not be stored in stack?

• Could you please explain why you use two set for diagonal points? why one store r+c and r-c doesn't work

• @brookc : thanks for the advice. 1 set will work for sure. using 2 sets will just make it clearer that we are dealing with 2 diagonals.

• Using three boolean arrays
Proceed row by row

``````    int res = 0;
public int totalNQueens(int n) {
//int[] horizonal = new int[n];
boolean[] vertical = new boolean[n];
boolean[] leftfall = new boolean[2 * n - 1];
boolean[] rightfall = new boolean[2 * n - 1];
helper(n, vertical, leftfall, rightfall, 0);
return res;
}

void helper(int n, boolean[] v, boolean[] l, boolean[] r, int row){

if(row == n){
res++;
return;
}

for(int col = 0; col < n; col++){
if(v[col] || l[row - col + n - 1] || r[row + col]) continue;
v[col] = true;
l[row - col + n - 1] = true;
r[row + col] = true;

helper(n, v, l, r, row + 1);

v[col] = false;
l[row - col + n - 1] = false;
r[row + col] = false;
}
}``````

• @EdickCoding you's idea is very smalier.

• This post is deleted!

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