c++ simple solution using backtracing


  • 0
    H
    class Solution {
    public:
        vector<vector<string>> ans;
        void print(vector<int> pos) {
            vector<string> tmp(pos.size(), string (pos.size(), '.'));
            for(int x = 0; x < pos.size(); x ++) tmp[x][pos[x]] = 'Q';
            ans.push_back(tmp);
        }
        
        bool isValid(vector<int> pos, vector<bool> occupy, int x, int y) {
            if(occupy[y]) return false;
            for(int i = 0; i < x; i ++)
                if(abs(x - i) == abs(y - pos[i])) return false;
            return true;
        }
        
        void helper(vector<int> pos, vector<bool> occupy, int cur_x) {
            if(cur_x == pos.size()) {
                print(pos);
                return;
            }
            for(int y = 0; y < pos.size(); y ++) {
                if(isValid(pos, occupy, cur_x, y)) {
                    occupy[y] = true;
                    pos[cur_x] = y;
                    helper(pos, occupy, cur_x+1);
                    occupy[y] = false;
                }
            }
        }
        
        vector<vector<string>> solveNQueens(int n) {
            vector<int> pos(n);
            vector<bool> occupy(n, false);
            helper(pos, occupy, 0);
            return ans;
        }
    };
    

Log in to reply
 

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