好好学习天天向上

八皇后问题，其实早在 15. N-Queens II 中就碰上了。更早还可以追溯到 CoolShell 谜题的第七关。

这个如此有名的问题，在我做完80多道 LeetCode 面试题之后，也基本变成了一道基础题了。

本质就是回溯。回溯需要知道时机，不符合，才需要回溯。那么我想来想去，这道题的考点就在于如何判断不符合。

! ! ! *
! Q ! *
! ! ! *
* * * !

我以四皇后为例，如果 Q 所在位置为 (1,1)，那么 ! 所表示的位置，即为皇后可以吃掉的位置。所以我最初的思路非常直接暴力。第一行肯定是随便放 Q 的，那么放一个 Q ，就能得到这么多 !，到下一行，可选的范围便大大的减小，什么时候放弃呢？当有一行全是 ! 的时候放弃。

我现在还相信，按照这种思路做出来一点问题也没。但难点在于遇到不符合 —— 这里就是遇到一行全是 ! 的时候，该如何做？具备可回溯性吗？我画出来的 ! 能恢复成上一步吗？显然是非常困难的。

可以回忆一下我们遇到的回溯，甚至动态规划问题，我们的解法都会留出退路。回溯就更加明显，所谓试错，是指你错了，还能 Ctrl + Z，试想如果不能回退，你错了就是错了，无路可走了。

那么，如何留出退路，让我们可以回去呢？一个基本的思维模式就是，“以下判上”，怎么讲？这道题我们判断的顺序显然是从第一行开始，直到最后一行，力求将所有皇后放下。

那么，“以下判上”，就是希望在进行第二行的时候，试着将该行的每一列放一个 Q，看她会不会吃掉上一行的 Q . 这样的回退是非常方便的，如果会吃掉，我不放 Q 就是了。

由于我只关注试错时，上面行的情况，所以我重新绘制了一张图：

! ! ! * | * ! * !
* Q * * | ! ! ! *
* * * * | * Q * *
* * * * | * * * *

当我试图在 (1,1) 位置放一个 Q 的时候，!所在的位置，都是会被这个 Q 吃掉的位置。那么如果第一行的 Q 在这三个 ! 所处的位置上，则不能放置！

写一个函数：

bool isValid(int row, int col, const vector<int> &queens) { // 要试的位置 (row, col)，以及已经存放了 Q 的位置，用 vector<int> 来存储，坐标为行，值为列。
    for (int queen_col=0, r=row-1, lc=col-1, rc=col+1; r>=0; --r, --lc, ++rc) // r 是要检查的行， lc (left col) 是左侧的列， rc (right col) 是右侧的列，这三个标记组成了上面左图中`!`的位置。
    {
        // queen_col 是要检查的这一行，Q 所在的列。
        queen_col = queens[r];
        if (queen_col == col || queen_col == lc || queen_col == rc) return false; // 只要 queen_col 与上面推测出 `!` 的所在位置一致，则不符合，返回。
    }
    return true; // 若所有要检查的行都通过了测试，则证明有效。
}

这个核心的函数有了之后，我们只需要考虑如何将完整的回溯过程描述出来即可。为了更通俗的表述思路，我运用递归 + DFS 的思想来表述回溯过程。

void solveNQueens(int row, vector<int> queens) { // 按行向下，想想为何是深搜？因为我第一行随便放个 Q , 我不把所有行走完，根本不知道这个 Q 放的对不对。这个按行向下，简单讲，类似二叉树的深度遍历。
    int size = queens.size(); // 节约时间复杂度，仅计算一次长度，或可以直接传入 n
    if (row == size) { // DFS 到底了，正好是尾递归的出栈条件
        vector<string> solution(size, string(size, '.')); // 构建输出格式，即解决方案的棋盘
        for (int r=0; r<size; ++r) // 按行给 Q
            solution[r][queens[r]] = 'Q';
        ret.push_back(solution);
    } else for (int col=0; col<size; ++col) { // 试错过程
        queens[row] = col;
        if (isValid(row, col, queens)) solveNQueens(row+1, queens); // 只有没错的，才进入更深的一层，错了就再试下一个地方放 Q
    }
}

整个解决方案，不过寥寥几行，但是仗了 DFS 递归的好处。是否理解透彻了呢？这个解法效率很高，差一点就是最高效率，什么？想知道最高效率的解法？用 bitset 吧，请回去看看第 15 题的解法，思路完全一样。

#include <vector>
#include <string>

using std::vector; using std::string;

class Solution {
    vector<vector<string>> ret;
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<int> queens(n, 0);
        solveNQueens(0, queens);
        return ret;
    }
    
    void solveNQueens(int row, vector<int> queens) {
        int size = queens.size();
        if (row == size) {
            vector<string> solution(size, string(size, '.'));
            for (int r=0; r<size; ++r)
                solution[r][queens[r]] = 'Q';
            ret.push_back(solution);
        } else for (int col=0; col<size; ++col) {
            queens[row] = col;
            if (isValid(row, col, queens)) solveNQueens(row+1, queens);
        }
    }
    
    bool isValid(int row, int col, const vector<int> &queens) {
        for (int queen_col=0, r=row-1, lc=col-1, rc=col+1; r>=0; --r, --lc, ++rc) {
            queen_col = queens[r];
            if (queen_col == col || queen_col == lc || queen_col == rc) return false;
        }
        return true;
    }
};

LeetCode Direct Link