# Collection of solutions in Java

• This post is mainly for myself as I learnt a lot from all kinds of solutions posted under this question. The copyright goes to the original author :)

Click on the title of each method and you can see the original author's explanations (if there is any).

``````public class Solution {
int count=0;
public int totalNQueens(int n) {
dfs(new int[n],0,n);
return count;
}
public void dfs(int[] pos,int step,int n) {
if(step==n) {
count++;
return;
}
for(int i=0;i<n;i++) {
pos[step]=i;
if(isvalid(pos,step)) dfs(pos,step+1,n);
}
}
public boolean isvalid(int[] pos, int step) {
for(int i=0;i<step;i++) {
if(pos[i]==pos[step]||(Math.abs(pos[i]-pos[step]))==(step-i)) return false;
}
return true;
}
}
``````

essentially the same one:
#Share. Java, 3ms, recurrsion, backtracing, very easy to understand. by Yuan__Yuan#

``````public class Solution {
public int totalNQueens(int n) {
if (n == 0)
return 0;
int[] q = new int[n];
return track(q, 0);
}

private int track(int[] q, int row) {
if (row == q.length)
return 1;
int solutions = 0;
for (int i = 0; i < q.length; i++) {
q[row] = i;
if (isValid(q, row, i)) {
solutions += track(q, row + 1);
}
}
return solutions;
}

private boolean isValid(int[] q, int row, int col) {
for (int i = 0; i < row; i++) {
if (q[i] == col || Math.abs(row - i) == Math.abs(col - q[i]))
return false;
}
return true;
}
}
``````
``````public class Solution {
private int counter = 0;
public int totalNQueens(int N) {
for(int i=0; i<N; i++) {
char[][] board = new char[N][N];
board[i][0] = 'Q';
solve(board, N, 1);
}
return counter;
}
private boolean isSafe(char[][] board, int N, int row, int col) {
for(int i=0; i<N; i++) {
if(board[i][col]!=0) return false;
if(board[row][i]!=0) return false;
}

int step = 1;
step = 1;
while(row-step>=0 && col-step>=0) {
if(board[row-step][col-step]!=0) return false;
++step;
}
step = 1;
while(row+step<N && col-step>=0) {
if(board[row+step][col-step]!=0) return false;
++step;
}
return true;
}
private boolean solve(char[][] board, int N, int col) {
if(col==N) {
++counter;
return false;
}
for(int i=0; i<N; i++) {
if(isSafe(board, N, i, col)) {
board[i][col] = 'Q';
if(solve(board, N, col+1)) return true;
else {
board[i][col] = 0;
}
}
}
return false;
}
}
``````
``````public class Solution {
Set<Integer> col = new HashSet<Integer>();
Set<Integer> diag1 = new HashSet<Integer>();
Set<Integer> diag2 = new HashSet<Integer>();

public int totalNQueens(int n) {
int[] res = new int[1];
helper(res,n,0);
return res[0];
}
public void helper(int[] res, int n, int row){
if(row==n){
res[0]++;
}
else{
for(int i=0; i<n; i++){
if(col.contains(i) || diag1.contains(i+row) || diag2.contains(row-i)) continue;
else{
helper(res,n,row+1);
col.remove(i);
diag1.remove(i+row);
diag2.remove(row-i);
}
}
}
}
}
``````

Similar idea as above but better implementation:

``````public class Solution {
int count = 0;
public int totalNQueens(int n) {
boolean[] cols = new boolean[n];     // columns   |
boolean[] d1 = new boolean[2 * n];   // diagonals \
boolean[] d2 = new boolean[2 * n];   // diagonals /
backtracking(0, cols, d1, d2, n);
return count;
}

public void backtracking(int row, boolean[] cols, boolean[] d1, boolean []d2, int n) {
if(row == n) count++;

for(int col = 0; col < n; col++) {
int id1 = col - row + n;
int id2 = col + row;
if(cols[col] || d1[id1] || d2[id2]) continue;

cols[col] = true; d1[id1] = true; d2[id2] = true;
backtracking(row + 1, cols, d1, d2, n);
cols[col] = false; d1[id1] = false; d2[id2] = false;
}
}
}
``````

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