N皇后问题

参考

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

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

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

您在真实的面试中是否遇到过这个题？ Yes
样例
对于4皇后问题存在两种解决的方案：

[

    [".Q..", // Solution 1

     "...Q",

     "Q...",

     "..Q."],

    ["..Q.", // Solution 2

     "Q...",

     "...Q",

     ".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
     */
    #define INITIAL -1000
    
    bool isValid(vector<int> &table,int row,int col,int n) {
       for(int i = 0;i < n;i++) {
           if (table[i] == col || abs(i-row) == abs(table[i]-col)) {
               return false;
           }
       }
       return true;
    }
    
    vector<string> getOneResult(vector<int> &table,int n) {
        string a(n,'.');
        vector<string> result(n,a);
       for(int i = 0;i < n;i++) {
            string temp = result[i];
            temp[table[i]] = 'Q';
            result[i] = temp;
       }
        return result;
    }
    
    vector<vector<string> > solveNQueens(int n) {
        // write your code here
        vector<vector<string> > results;
        vector<int> table(n,INITIAL);
        int i = 0;
        int j = 0;
        while(i < n) {
            
            while(j < n) {
                if (isValid(table,i,j,n) == true) {
                    table[i] = j;
                    j = 0;
                    break;
                } else {
                    ++j;
                }
            } //这个j循环找到适合的放置地点，若找不到table[i] == INITIAL
            
            if (table[i] == INITIAL) {
                if(i == 0) {
                    break;//回溯到第一行没解就终止
                } else {
                    i--;//回溯上一行的下一列
                    j = table[i] + 1;
                    table[i] = INITIAL;
                    continue;
                }
            }
            
            if (i == n-1) { //最后一行打印
                results.push_back(getOneResult(table,n));
                j = table[i] + 1;
                 table[i] = INITIAL;
                 continue;
            }
            
            i++;
        }
        return results;
    }
};