An iterative backtracking solution


  • 0
    S
    // backtracing iterative solution
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string> > ans;
        vector<int> col(n, 0);
        int row = 0;
    
        while (1) {
            if (row == n) { 
                // n rows has been set
                // generate string for this solution.
                string str(n, '.');
                vector<string> vs(n, str);
                for (int i = 0; i < n; i++) vs[i][col[i]] = 'Q';
                ans.push_back(vs);
                col[--row]++; // go back to previous row and increment that queen by 1 column.
            }
            else if (col[row] == n) { // all columns has been tried
                col[row--] = 0;       // reset this queen to column 0 and go back to previous row ???
                if (row == -1) break; // all cases checked, then exit
                col[row]++;           // go back to previous row and increment that queen by 1 column.
            }
            else if (!check(col, col[row], row)) {
                col[row]++; // fail to check at this column, so go to next column.
            }
            else row++;   // everything's perfect, lets go to queen in next row.
        }
        
        return ans;
    }
    
    // check last queen with all previous queens
    bool check(vector<int> &col, int c, int r) {
        for (int i = 0; i < r; ++i)
            if (col[i] == c || abs(col[i] - c) == abs(i - r)) // in the same column or the same diagonal
                return false;
        return true;
    }

Log in to reply
 

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