回溯算法（六）：N皇后问题

51. N 皇后
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

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

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
           

一、解题思路

1. 首先我们写一个函数，来判定在某个格子上放置皇后是否合法
2. 对于棋盘，按层向下每层放置一个皇后
3. 如果能够放到最后，就可以得到一个可行解

其实这就是一个回溯问题，只不过路径选择的合法性更复杂一些

二、代码实现

class Solution {
private:
    vector<vector<string>> res;  //用于存储合法棋盘的结果

	/-----皇后放在[row][col]位置上的合法性-----/
    bool isVaild(int row, int col, int n, vector<string>& chessboard){

		/----列上是否合法：由于当前行的下面还没放置皇后，因此遍历当前行的上面即可判定---/
        for(int i = 0; i < row; i++){
            if(chessboard[i][col] == 'Q') return false;
        }

		/---135度斜线是否合法：同样只用判定当前行的上半部分-----/
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if(chessboard[i][j] == 'Q') return false;
        }
		
		/-----45度上是否合法：同样只用判定当前行的上半部分-----/
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
            if(chessboard[i][j] == 'Q') return false;
        }
        return true;  //均合法，返回ture
    }

    void backTracking(int n, int row, vector<string>& chessboard){
    	//如果已经放置到index = n的行了，完成，添加到结果
        if(row == n){
            res.push_back(chessboard);
            return;
        }

		/----对于当前行，判定每一个格子的合法性，在合法的格子上调用递归回溯继续寻找-----/
        for(int col = 0; col < n; col++){
            if(isVaild(row, col, n, chessboard)){
                chessboard[row][col] = 'Q';
                backTracking(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }


/-----初始化棋盘，调用递归获取全部答案-----/
public:
    vector<vector<string>> solveNQueens(int n) {
        res.clear();
        vector<string> chessboard(n, string(n, '.'));  //初始化棋盘
        backTracking(n, 0, chessboard);
        return res;
    }
};