前言

今日感冒在家剛好利用時間打一篇文章，天氣變冷了大家要多注意保暖阿。

題目

給定數字n，並列出n * n皇后所有可能。

輸入

4

輸出

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

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

解析

這經典提我想很多人大概都知道解法，。

規則

首先要先知道主要規則，每個皇后上下左右的行列和對角線都不能放置其它皇后，由此我們可以詳細列出規則來分析。

1. 八皇后每一個水平列(水平行)不能有其它皇后。
2. 八皇后每一個垂直行(水平列)不能有其它皇后。
3. 八皇后每一個45度左上下方不能有其它皇后。
4. 八皇后每一個45度右上下方不能有其它皇后。

排除

當在寫程式時走訪都是按照順序從第一個擺到最後一個，所以有些規則是不必要的，則可以排除。

1. 不需考慮到第一點。
2. 只需檢查目前位置以上的垂直行(水平列)。
3. 只需檢查目前位置以上的45度左上位置。
4. 只需檢查目前位置以上的45度右上位置。

以下方為例：
下面將皇后放置在第三層放置在第三個位置

第零層N..N..N.
第一層.N.N.N..
第二層..NNN...
第三層...Q....
第四層........
第五層........
第六層........
第七層........

下面將皇后放置在第三層放置在第四個位置

第零層.N..N..N
第一層..N.N.N.
第二層...NNN..
第三層....Q...
第四層........
第五層........
第六層........
第七層........

第三層放置在第三個位置(3, 3)
1.考慮第二點檢查第零層到第二層的第三個位置是否有皇后，(0, 3)、(1, 3)、(2, 3)。
2.考慮第三點檢查第零層到第二層的45度左上方是否有皇后，(0, 0)、(1, 1)、(2, 2)。
3.考慮第四點檢查第零層到第二層的45度右上方是否有皇后，(0, 6)、(1, 5)、(2, 4)。

第三層放置在第四個位置(3, 4)
1.考慮第二點檢查第零層到第二層的第四個位置是否有皇后，(0, 4)、(1, 4)、(2, 4)。
2.考慮第三點檢查第零層到第二層的45度左上方是否有皇后，(0, 1)、(1, 2)、(2, 3)。
3.考慮第四點檢查第零層到第二層的45度右上方是否有皇后，(0, 7)、(1, 6)、(2, 5)。

上述可得到：

• 第一點知道因為單純判斷垂直行是否有皇后，所以只需要8個空間來去記憶。
• 第二和三點因為每個行列位置都不同則需要8 * 8的空間來去記憶。

但若仔細觀察第三和第四點的圖形或座標，可推倒出一個公式，若abs(放置位置 - N層放置位置) = (放置層 - N層)則代表已有皇后放置，接著直接來看一下如何推導出來。
第三層放置在第三個位置(3, 3)

• 對於第二層：放置位置左邊為3 - 1，右邊為3 + 1，與目前層數差為1。
• 對於第一層：放置位置左邊為3 - 2，右邊為3 + 2，與目前層數差為2。
• 對於第零層：放置位置左邊為3 - 3，右邊為3 + 3，與目前層數差為3。

第三層放置在第四個位置(3, 4)

• 對於第二層：放置位置左邊為4 - 1，右邊為4 + 1，與目前層數差為1。
• 對於第一層：放置位置左邊為4 - 2，右邊為4 + 2，與目前層數差為2。
• 對於第零層：放置位置左邊為4 - 3，右邊為4 + 3，與目前層數差為3。

由上可知道一公式，層數差K則abs(放置位置 - N層放置位置) = K。然而K為目前層數 - N層數。

程式碼

CheckQueen：檢查上層是否有皇后。

	bool CheckQueen(const vector<string>& queen, const vector<int>& queenPos, const int row, const int col)
	{
		for (int index = 0; index < row; index++)
		{
			if (queenPos[index] == col
				|| (row - index) == abs(col - queenPos[index]))
			{
				return false;
			}
		}
		return true;
	}

RunQueen：走訪每層並放置皇后。

	void RunQueen(vector<vector<string>>& queens, vector<string>& queen, vector<int>& queenPos, int row)
	{
		if (row == queen.size())
		{
			queens.push_back(queen);
			return;
		}

		for (int index = 0; index < queen.size(); index++)
		{
			if (CheckQueen(queen, queenPos, row, index))
			{
				queen[row][index] = 'Q';
				queenPos[row] = index;
				RunQueen(queens, queen, queenPos, row + 1);
			}
			queen[row][index] = '.';
		}
	}

LeetCode呼叫方式。

	vector<vector<string>> solveNQueens(int n) {
		vector<vector<string>> queens;
		vector<string> queen(n, string(n, '.'));
		vector<int> queenPos(n);

		RunQueen(queens, queen, queenPos, 0);

		return queens;
	}

結論

經過解析希望每個人都能更加瞭解八皇后的公式由來，也祝大家假日愉快。