A standard backtracing solution


  • 0
    S
    struct location{
        int row;
        int col;
        location(int r, int c): row(r), col(c) {}
    };
    
    // recursive backtracking solution
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string> > ans;
        vector<string> board(n, string(n, '.'));
        vector<location> placed;
        
        // row "0" try all the possibilities
        for (int j = 0; j < n; j++) {
            board[0][j] = 'Q';
            placed.push_back(location(0, j));
            solveNQueens(1, placed, board, ans);
            placed.pop_back();
            board[0][j] = '.';
        }
        
        return ans;
    }
    
    void solveNQueens(int r, vector<location> &placed, vector<string> &board, vector<vector<string> > &ans) {
        if (r == board.size()) {
            ans.push_back(board);
            return;
        }
        
        // row "r" try all the possibilities
        for (int j = 0; j < board.size(); j++) {
            // first check whether location (r, j) is valid or not
            bool conflict = false;
            for (int i = 0; i < placed.size(); i++) {
                //check whether the column or the diagonal line is used
                if(placed[i].col == j || abs(placed[i].row - r) == abs(placed[i].col - j)) {
                    conflict = true;
                    break;
                }
            }
            
            if(conflict) continue;
            
            board[r][j] = 'Q';
            placed.push_back(location(r, j));
            solveNQueens(r + 1, placed, board, ans);
            placed.pop_back();
            board[r][j] = '.';
        }
    }

Log in to reply
 

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