Easy Java/Python recursive & iterative backtracking solutions


  • 1

    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
    

Log in to reply
 

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