# Easy Java/Python recursive & iterative backtracking solutions

• For detail explanation see n-queens solution

Java recursive

``````private int bt(boolean[] c, boolean[] f, boolean[] b, int row, int n) {
if (row == n) return 1;
int ans = 0;
for (int col = 0; col < n; ++col) {
int i = col + row, j = col - row + n;
if (c[col] || f[i] || b[j]) continue;
c[col] = f[i] = b[j] = true;
ans += bt(c, f, b, row + 1, n);
c[col] = f[i] = b[j] = false;
}
return ans;
}

public int totalNQueens(int n) {
return bt(new boolean[n], new boolean[2 * n], new boolean[2 * n], 0, n);
}

// Runtime: 2ms
``````

Java Iterative

``````public int totalNQueens(int n) {
int ans = 0;
int[] queens = new int[n];
boolean[] c = new boolean[n + 1];
boolean[] f = new boolean[2 * n];
boolean[] b = new boolean[2 * n];
c[n] = true; //dummy boundary
int col = 0, row = 0;
while (true) {
if (c[col] || f[col + row] || b[col - row + n]) {
if (row == n || col == n) {
if (row == 0) return ans;
if (row == n) ans++;
col = queens[--row];
c[col] = f[col + row] = b[col - row + n] = false;
}
col++;
} else {
c[col] = f[col + row] = b[col - row + n] = true;
queens[row++] = col;
col = 0;
}
}
}
// Runtime: 4ms
``````

Python iterative

``````def totalNQueens(self, n):
row = col = ans = 0
queens = [-1] * n
columns = [True] * n + [False]  # || col with dummy for boundary
back = [True] * n * 2  # \\ col - row
forward = [True] * n * 2  # // col + row
while True:
if columns[col] and back[col - row + n] and forward[col + row]:
queens[row] = col
columns[col] = back[col - row + n] = forward[col + row] = False
row += 1
col = 0
else:
if row == n or col == n:
if row == n:
ans += 1
if row == 0:
return ans
row -= 1
col = queens[row]
columns[col] = back[col - row + n] = forward[col + row] = True
col += 1

# Runtime: 60 ms
``````

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