My clear iterative 8ms cpp code with comments


  • 0
    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;
        }
        
        vector<string> generateSolution(const vector<int> &res)
        {
            vector<string> solution;
            
            for(int row : res)
            {
                string s(res.size(), '.');
                s[row] = 'Q';
                
                solution.push_back(s);
            }
            
            return solution;
        }
        
        vector< vector<string> > solveNQueens(int n) 
        {
            vector< vector<string> > results;
            
            if(!n) return results;
            
            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)
                {
                    results.push_back( generateSolution(res) );
                    continue;
                }
                
                // go down
                depth++;
            }
            
            return results;
        }
    };

Log in to reply
 

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