前言

今日感冒在家刚好利用时间打一篇文章，天气变冷了大家要多注意保暖阿。

题目

给定数字n，并列出n * n皇后所有可能。

输入

4

输出

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

解析

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

规则

首先要先知道主要规则，每个皇后上下左右的行列和对角线都不能放置其它皇后，由此我们可以详细列出规则来分析。

八皇后每一个水平列(水平行)不能有其它皇后。八皇后每一个垂直行(水平列)不能有其它皇后。八皇后每一个45度左上下方不能有其它皇后。八皇后每一个45度右上下方不能有其它皇后。

排除

当在写程式时走访都是按照顺序从第一个摆到最后一个，所以有些规则是不必要的，则可以排除。

不需考虑到第一点。只需检查目前位置以上的垂直行(水平列)。只需检查目前位置以上的45度左上位置。只需检查目前位置以上的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;}

结论

经过解析希望每个人都能更加了解八皇后的公式由来，也祝大家假日愉快。