LeetCode-N Queens

N皇后问题。
经典回溯问题：

以下是递归及非递归的方法：

class Solution {
public:
    
  //判断是否是合法的位置
    bool valid(vector<int>& ans,int row,int col){

        for (int index=0;index<row;++index){
            if (ans[index] == col)return false;
            if (ans[index] == col-(row-index))return false;
            if (ans[index] == col+(row-index))return false;
        }
        return true;
    }
    
  //根据一维解构建二维位置图
    int cst(vector<vector<int>>& ans, vector<vector<string>>& res){
        
        vector<string> tmp;
        for (int j = 0;j<ans.size();++j){
            tmp.clear();
            for (int i=0;i<ans[j].size();++i){
                string row(ans[j].size(),'.');
                row[ans[j][i]] = 'Q';
                tmp.push_back(row);
            }
            res.push_back(tmp);
        }
        return 0;
    }
    
  //递归解法
    int _rec_cst(vector<int>& tmp,int num,vector<vector<int>>& ans,int row){
        if (row == num){
            ans.push_back(tmp);
            return 0;
        }
        
        for (int pos=0;pos<num;++pos){
            //tmp[row] = pos;
            if(valid(tmp,row,pos)){
                tmp[row] = pos;
                _rec_cst(tmp,num,ans,row+1);
            }
        }
        return 0;
    }
    
    int rec_cst(vector<vector<int>>& ans,int num){
        
        vector<int> tmp(num,-1);
        _rec_cst(tmp,num,ans,0);
        return 0;
    }
    
  //非递归解法
    int non_cst(vector<vector<int>>& ans,int num){
        vector<int> tmp(num,-1);
        int row=0;
        int pos=0;
        while(row<num){
            while(pos<num){
                if (valid(tmp,row,pos)){
                    tmp[row] = pos;
                    pos = 0;
                    break;
                }else{
                    pos++;
                }
            }
            if (tmp[row] == -1){
                if (row==0)break;
                row--;
                pos = tmp[row]+1;
                tmp[row] = -1;
                continue;
            }
            if (row == num-1){
                pos = tmp[row]+1;
                ans.push_back(tmp);
                tmp[row] = -1;
                continue;
            }
            row++;
        }
        return 0;
    }
    
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<int>> ans;
        vector<vector<string>> res;
        
        //递归的算法
        //int ret = rec_cst(ans,n);
        
        //非递归的算法
        int ret = non_cst(ans,n);
        
        
        //根据ans，构造结果
        cst(ans,res);
        return res;
    }
};