My C++ DFS+Backtracking solution (O(N) memory, O(N^2) time )

  • 0

    The same idea as N-QUEEN, use three bool arraies to track if the current column (indexed by col), diagonal line (indexed by row-col+N), or the anti-diagonal line (indexed by row+col) is available (i.e., no other queen is already put on that line); do DFS and backtracking from row 1 to row N-1 for each column.

    class Solution {
        void  dfs(int &res, int row, int N, bool colValid[], bool diagValid[], bool antiDiagValid[])
            if(row==N) ++res;
                for(auto col=0; col<N; ++col)
                    if(colValid[col] && diagValid[row-col+N] && antiDiagValid[row+col])
                        colValid[col] = diagValid[row-col+N] = antiDiagValid[row+col] = false;
                        dfs(res, row+1, N, colValid, diagValid, antiDiagValid);
                        colValid[col] = diagValid[row-col+N] = antiDiagValid[row+col] = true;
        int totalNQueens(int n) {
            if(n<=0) return 0;
            int res =0;
            bool colValid[n], diagValid[2*n], antiDiagValid[2*n];
            fill_n(colValid, n, true);
            fill_n(diagValid,2*n, true);
            fill_n(antiDiagValid, 2*n, true);
            dfs(res, 0, n, colValid, diagValid, antiDiagValid);
            return res;

  • 0

    By using dfs, why O(N^2) time??

Log in to reply

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