# Java Solution using Backtracking

• Using one dimensional array pos[row] , row=0,1,...,n-1 to save the column position for that row.

class Solution {

private int count=0;

public int totalNQueens(int n) {

// save the col position of queens
int[] pos = new int[n];
NQueenHelper(pos, 0, n);
return count;

}

private void NQueenHelper(int[] pos, int row, int n) {

if (row == n) {
count++;
return;
}
for (int col=0; col<n; col++) {
if (isValid(pos, row, col, n)) {
pos[row] = col;
NQueenHelper(pos, row+1, n);
pos[row] = 0;
}
}

}

private boolean isValid(int[] pos, int row, int col, int n) {

// any row has a queen in this col
for (int i=0; i<row; i++) {
if (pos[i] == col) {
return false;
}
}
// any queen in the 45 diagonal direction
for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
if (pos[i] == j) {
return false;
}
}
// any queen in the 135 diagonal direction
for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
if (pos[i] == j) {
return false;
}
}
return true;

}

}

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