# Java 1 ms linked list solution

• Not as awesome as the bit mask one (I admit I hadn't thought of using that), but still pretty efficient, and I haven't seen this posted yet. The idea is to use a linked list of columns (implemented as an index array) to quickly remove attacked columns. Typical Boolean tables are used for diagonal attacks.

``````public int totalNQueens(int n) {
int[] next = new int[n + 1]; // linked list of columns
for (int i = 0; i < next.length; ++i) {
next[i] = i + 1;
}
boolean[] main = new boolean[2 * n - 1]; // attacked diagonals
boolean[] counter = new boolean[2 * n - 1]; // attacked diagonals
}

private static int totalNQueens(int n, int i, int[] next, boolean[] main, boolean[] counter) {
if (i > n) {
return 1; // one way has been found
} else {
int ways = 0;
for (int j = next[0], jp = 0; j <= n; jp = j, j = next[j]) {
int m = j - i + (n - 1); // main diagonal index starts at bottom-left
int c = j + i - 2; // counter diagonal index starts at top-left
if (!main[m] && !counter[c]) {
next[jp] = next[j];
main[m] = true;
counter[c] = true;
ways += totalNQueens(n, i + 1, next, main, counter);
main[m] = false; // backtrack
counter[c] = false;
next[jp] = j;
}
}
return ways;
}
}``````

• cool. you can always bring something new ;p

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