N-Queens

 //dfs

class Solution {

public:
    vector<vector<string> > solveNQueens(int n){
        vector<vector<string> > ans;
        vector<int> C(n,-1);
        search(0, n, C, ans);
        return ans;
    }
    void search(int cur, int n, vector<int>&C, vector<vector<string> > &ans){
        if(cur == n){
            vector<string> vs;
            for(int i=0; i<n; ++i){
                string s(n, '.');
                s[C[i]] = 'Q';
                vs.push_back(s);
            }
            ans.push_back(vs);
            return;
        }
        for(int i=0; i<n; ++i){
            bool ok = true;
            C[cur] = i;
            for(int j=0; j<cur; ++j)
                if(C[cur]==C[j] || cur-j==C[cur]-C[j] || cur-j==C[j]-C[cur]){
                    ok = false;
                    break;
                }
            if(ok) search(cur+1, n, C, ans);
        }
    }
};

// almost the same

class Solution {

public:
    vector<vector<string> > solveNQueens(int n){
        vector<vector<string> > ans;
        vector<int> columnsforrow(n,0);
        search(0,n,columnsforrow,ans);
        return ans;
    }
    void search(int row, int n, vector<int>& columnsforrow,vector<vector<string> >&ans){
        if(row==n){
           
            vector<string> ones;
            for(int i=0;i<n;i++){
                string s(n,'.');
                s[columnsforrow[i]]='Q';
                ones.push_back(s);
            }
            ans.push_back(ones);
            return;
        }
        for(int i=0;i<n;i++){
            columnsforrow[row]=i;
            if(check(row,columnsforrow))
                search(row+1,n,columnsforrow,ans);
        }  
    }
    bool check(int row,vector<int>& columnsforrow){
        for(int i=0;i<row;i++)
            if(columnsforrow[row]==columnsforrow[i]||
            columnsforrow[row]-columnsforrow[i]==row-i||
            columnsforrow[i]-columnsforrow[row]==row-i)
                return false;
        return true;       
    }

};