n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。

给定一个整数n，返回所有不同的n皇后问题的解决方案。

每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。

class Solution {
public:
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
     
    vector<vector<string> > ret;
     
    bool check(int * maze, int len) {
        for(int i = 1; i <= len-1; ++i) {
            for(int j = i+1; j <= len; ++j) {
                if(i-j == maze[i]-maze[j] || j-i == maze[i]-maze[j]) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    void process(int * maze, int len) {
        vector<string> tmp;
        for(int i = 1; i <= len; ++i) {
            char * str = new char[len+1];
            int pos = 0;
            //printf("fdsafa");
            for(int j = 1; j <= len; ++j) {
                if(j == maze[i]) {
                    str[pos++] = 'Q';
                } else {
                    str[pos++] = '.';
                }
            }
            str[pos] = '\0'; // 特别注意
            //puts(str);
            string s(str);
            delete [] str;
            tmp.push_back(s);
        }
        ret.push_back(tmp);
    }
    
    void callPermutation(int * maze, int start, int end) {
        
        if(start > end) {
            return;
        }
        
        if(start == end) {
            if(check(maze, end)) {
                
                process(maze, end);
            }
        }
        for(int i = start; i <= end; ++i) {
            swap(maze[start], maze[i]);
            callPermutation(maze, start+1, end);
            swap(maze[start], maze[i]);
        }
    } 
     
    vector<vector<string> > solveNQueens(int n) {
        // write your code here
        
        int * maze = new int[n+1];
        for(int i = 0; i <= n; ++i) {
            maze[i] = i;
        }
        
        callPermutation(maze, 1, n);
        delete [] maze; 
        return ret;
    }
};