lintcode-N皇后問題

n皇后問題はn個の皇后をn*nの碁盤に置くことであり,皇后同士が互いに攻撃することはできない.
整数nを与え,すべての異なるn皇后問題の解決策を返す.
各ソリューションは、「Q」および「.」の明確なn皇后配置レイアウトを含む.それぞれ女王と空の位置を表す.

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 > 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 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 > 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;
    }
};