N皇后

class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        vector<string> track;
        string s="";
        for(int i=0;i<n;i++)
        {
            s+=‘.‘;
        }
        for(int i=0;i<n;i++)
        {
            track.push_back(s);
        }
        DFS(n,0,track);
        return res;
    }
    void DFS(int n,int index,vector<string>& track)
    {
        if(index==n)
        {
            res.push_back(track);
            return;
        }
        for(int i=0;i<n;i++)
        {
            if(!valid(track,index,i))
            {
               continue;
            }
            track[index][i]=‘Q‘;
            DFS(n,index+1,track);
            track[index][i]=‘.‘;
        }
    }
    bool valid(vector<string>map,int row,int col)
    {
        for(int i=0;i<row;i++)
        {
            if(map[i][col]==‘Q‘)
            {
                return false;
            }
        }
        for(int i=row-1,j=col-1;i>=0 &&j>=0;i--,j--)
        {
            if(map[i][j]==‘Q‘)
            {
                return false;
            }   
        }
        for(int i=row-1,j=col+1;i>=0 &&j<map.size();i--,j++)
        {
            if(map[i][j]==‘Q‘)
            {
                return false;
            }   
        }
        return true;
    }
};