C++ backtracking solution


  • 0
    P

    class Solution {

    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<vector<int>> sol;
            recur(vector<int>(), sol, n);
            vector<vector<string>> res;
            for (auto v : sol)
                res.push_back(draw(v));
            return res;
        }
        
        void recur(vector<int> history, vector<vector<int>> &sol, int &n) {
            if (history.size() == n) {
                sol.push_back(history);
                return;
            }
            vector<bool> check(n, true);
            for (int i = 0; i < history.size(); ++i) {
                check[history[i]] = false;
                int top = history[i] - (history.size() - i), bot = history[i] + (history.size() - i);
                if (top >= 0) check[top] = false;
                if (bot < n) check[bot] = false;
            }
            for (int i = 0; i < n; ++i) {
                if (check[i]) {
                    history.push_back(i);
                    recur(history, sol, n);
                    history.pop_back();
                }
            }
        }
        
        vector<string> draw(vector<int> place) {
            vector<string> res;
            for (int i = 0; i < place.size(); ++i) {
                res.push_back(string(place.size(), '.'));
                res[i][place[i]] = 'Q';
            }
            return res;
        }
    

    };


Log in to reply
 

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