DEV Community

Fatima Alam
Fatima Alam

Posted on

N-Queen's Problem Solution

class Solution {
public:
    void solve(int i,int& n,vector<string> &tmp, vector<vector<string>> &ans,vector<bool> &c,vector<bool> &md,vector<bool> &td){
        if(i==n){
            ans.push_back(tmp);
            return;
        }
        string str(n,'.');
        for(int j = 0; j < n; j++){
            if((c[j]==false&&md[i-j+n]==false&&td[i+j]==false)){
                str[j] = 'Q';
                c[j] = true;md[i-j+n]=true;td[i+j] = true;
                tmp.push_back(str);
                solve(i+1,n,tmp,ans,c,md,td);
                tmp.pop_back();
                str[j] = '.';
                c[j] = false;md[i-j+n]=false;td[i+j] = false;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<string> tmp;
        vector<bool> c(n,false),md(2*n+3,false),td(2*n+3,false);
        solve(0,n,tmp,ans,c,md,td);
        return ans;
    }
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)