51. N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 上图为 8 皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 示例:

输入: 4
输出: [
[".Q..",  // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.",  // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

提示：

• 皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。（引用自 百度百科 - 皇后 ）

解题思路

回溯算法
按层按列遍历，检查每个当前位置是否合法，不合法的位置则跳过，合法的位置作为当前选择，并进入下一层。回溯时，即撤销本层当列的选择，继续遍历下一列。

class Solution {
public:
    vector<vector<string>> res;
    int len;
    vector<vector<string>> solveNQueens(int n) {
        len = n;
        vector<string> solveOne(n,string(n,'.'));
        recurDep(0,solveOne);
        return res;
    }
     void recurDep(int row,vector<string>& solveOne){
         //终止条件
        if(row == len) {
            res.push_back(solveOne);
            return;
        }
        for(int col = 0;col < len;col++) {
            //只有合适的位置才能放置，排除其他不合法的选择
            if(checkPosi(row,col,solveOne)) {
                //当前选择
                solveOne[row][col] = 'Q';
                //进行下一决策
                recurDep(row + 1,solveOne);
                //回溯，撤销选择
                 solveOne[row][col] = '.';
            }
        }
     }
    //检查位置(row,col)是否可以放置皇后
     bool checkPosi(int row,int col,vector<string>& solveOne) {
         //检查列是否有皇后互相冲突
         for (int i = 0;i < row;i++)
             if(solveOne[i][col] == 'Q') return false;
         //检查右上方是否有皇后冲突
         for(int i = row-1,j = col + 1; i >= 0&& j < len;i--,j++)
              if(solveOne[i][j] == 'Q') return false;
         //检查左上方是否有皇后冲突
         for(int i = row-1,j = col - 1; i >= 0&& j >= 0;i--,j--)
              if(solveOne[i][j] == 'Q') return false;
        return true;
     }
};