My iterative cpp code


  • -1
    C
    class Solution {
    public:
    
        bool isValid(const vector<int> &solution, int row, int col)
        {
            for(int i=0; i<col; i++)
            {
                if( (row == solution[i]) || (abs(row-solution[i]) == (col-i)) )
                    return false;
            }
            
            return true;
        }
        
        int totalNQueens(int n) 
        {
            int result = 0;
            
            if(!n) return result;
            
            int depth = 0;
            vector<int> res(n, -1);
            
            // dfs
            while(depth >= 0)
            {
                int cur = res[depth];
                
                // go right to its valid neighbour
                while(++cur < n)
                {
                    if( isValid(res, cur, depth) )
                        break;
                }
                
                // reset current level, then go up
                if(cur >= n)
                {
                    res[depth--] = -1;
                    continue;
                }
                
                res[depth] = cur;
                // if it's leaf, add solution
                if(depth == n-1)
                {
                    result++;
                    continue;
                }
                
                // go down
                depth++;
            }
            
            return result;
        }
    };

Log in to reply
 

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