回溯算法（六）：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;
    }
};