# Super FAST Java solution

• There are 5 solutions HERE, if you are interested in digging deeper in N-Queens problem. Step by step, one solution by one solution, digging deeper and deeper and finally comes to the fastest one - the solution using `bit array`.

I listed 2 solutions below, one is normal, and another is quite fast. I guess, the fastest.

Below is a normal one, 8ms

``````public class Solution {
private boolean[] pie, na, shu;
private int[] sol;
// pie = row + col;
// na = n - 1 + col - row;
public List<List<String>> solveNQueens(int n) {
shu = new boolean[n];
pie = new boolean[2 * n - 1];
na = new boolean[2 * n - 1];
sol = new int[n];
List<List<String>> res = new ArrayList();
DFS(res, 0, n);
return res;
}
private void DFS(List<List<String>> res, int row, int N) {
for (int col = 0; col < N; col++) {
int j = row + col, k = N - 1 + col - row;
if (shu[col] || pie[j] || na[k]) continue;
sol[row] = col;
if (row == N - 1) {
List<String> list = new ArrayList();
for (int i = 0; i < N; i++) {
String s = "";
for (int c = 0; c < N; c++) {
if (c != sol[i]) s += ".";
else s += "Q";
}
list.add(s);
}
res.add(list);
} else {
shu[col] = pie[j] = na[k] = true;
DFS(res, row + 1, N);
shu[col] = pie[j] = na[k] = false;
}
}
}
}
``````

The solution below is 4ms, beats 99%:

``````public class Solution {
// pie = row + col;
// na = n - 1 + col - row;
int[] sol;
public List<List<String>> solveNQueens(int n) {
sol = new int[n];
List<List<String>> res = new ArrayList();
DFS(res, n, 0, 0, 0, 0);
return res;
}
private void DFS(List<List<String>> res, int N, int row, int shu, int pie, int na) {
int ok = ((1 << N) - 1) & ~(shu | pie | na);
while (ok != 0) {
int p = ok & -ok;
ok ^= p;
sol[row] = p;
if (row == N - 1) {
List<String> list = new ArrayList();
for (int i = 0; i < N; i++) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c < N; c++) {
if ((1 << c) == sol[i]) sb.append("Q");
else sb.append(".");
}
list.add(sb.toString());
}
res.add(list);
} else {
DFS(res, N, row + 1, shu ^ p, (pie ^ p) >> 1, (na ^ p) << 1);
}
}
}
}
``````

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