3ms | 9 test cases | C++ | integer array to track previous locations


  • 0
    P

    Each solution is represented as an integer array v, where v[index] is the location of the queen at row index, ie a top row of [..Q.] would make v[0] == 2.

    The process() function then recursively tries every single column in the row passed in as a parameter. It goes back up the board, setting the valid flag false if there's a collision in the same column or diagonal, which is found by comparing the delta in row and delta in column.

    If the recursion reaches past the last row, then the vector represents a valid solution and the build() function creates a vector<string> from the vector<int> solution.

    class Solution {
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<vector<string>> res;
            
            vector<int> v(n);
            
            process(v, res);
            
            return res;
        }
        
        vector<string> build(vector<int> v) {
            int n = v.size();
            string row;
            for(int i = 0; i < n; i++)
                row += '.';
            vector<string> soln(n, row);
            
            for(int r = 0; r < n; r++)
                soln[r][v[r]] = 'Q';
            
            return soln;
        }
        
        void process(vector<int> v, vector<vector<string>> &res, int row = 0) {
            int n = v.size();
            if(row == n) {
                vector<string> soln = build(v);
                res.push_back(soln);
                return;
            }
            
            for(int c = 0; c < n; ++c) {
                bool valid = true;
                
                // check back up for same col or same diag
                for(int r = row - 1; r >= 0 && valid; --r) {
                    if(v[r] == c)
                        valid = false;
                    else if(abs(row - r) == abs(c - v[r]))
                        valid = false;
                }
    
                if(valid) {
                    v[row] = c;
                    process(v, res, row + 1);
                }
            }
        }
    };
    

Log in to reply
 

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