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


  • 0
    D

    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 {
    private:
        void  dfs(int &res, int row, int N, bool colValid[], bool diagValid[], bool antiDiagValid[])
        {
            if(row==N) ++res;
            else{
                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;
                    }
                }
            }
        }
    
    public:
        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
    S

    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.