Typical backtracking solution


  • 0
    class Solution {
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<string> board(n, string(n, '.'));
            vector<vector<string>> ans;
            helper(board, ans, 0, n);
            return ans;
        }
        
    private:
        void helper(vector<string> &board, vector<vector<string>> &ans, int row, int n){
            if(row == n){
                ans.push_back(board);
                return;
            }
            
            for(int i = 0; i < n; ++i){
                if(isValid(board, row, i, n)){
                    board[row][i] = 'Q';
                    helper(board, ans, row + 1, n);
                    board[row][i] = '.';
                }
            }
        }
        
        bool isValid(const vector<string> &board, int row, int col, int n){
            int left = col - 1, right = col + 1;
            for(int i = row - 1; i >= 0; --i){
                if(board[i][col] == 'Q') return false;
                if(left >= 0 && board[i][left] == 'Q') return false;
                if(right < n && board[i][right] == 'Q') return false;
                --left;
                ++right;
            }
            
            return true;
        }
    };
    

Log in to reply
 

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