Using sets in recursion instead of checking validity


  • 0
    M

    Here's my solution...

    1. Within each recursive call, iterate through one row.
    2. For each cell, check to make sure it's not in 1 of 3 sets... (1) column, (2) top left to bottom right diagonal (i + j) of (3) top right to bottom left diagonal (i - j).

    Let me know what you think...

        void findNxt(set<int> &blkCol, set<int> &blkd1, set<int> &blkd2, int i, int n, vector<string> &row, vector<vector<string> >& res) {
        for (int j=0; j<n; j++) {
            if ((blkCol.find(j) == blkCol.end()) &&
                (blkd1.find(i - j) == blkd1.end()) &&
                (blkd2.find(i + j) == blkd2.end())) {
                    row[i][j] = 'Q';
                    if (i == (n-1)) {
                        res.push_back(vector<string>(row));
                    } else{
                        blkCol.insert(j);
                        blkd1.insert(i - j);
                        blkd2.insert(i + j);
                        findNxt(blkCol, blkd1, blkd2, i+1, n, row, res);
                        blkCol.erase(j);
                        blkd1.erase(i - j);
                        blkd2.erase(i + j);
                    }
                    row[i][j] = '.';
            }
        }
    }
    
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string> > res;
        vector<string> row(n, string(n, '.'));
    
        set<int> blkCol, blkd1, blkd2;
    
        findNxt(blkCol, blkd1, blkd2, 0, n, row, res);
    
        return res;
    }

Log in to reply
 

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