n皇后实现总结

n皇后其实就是回溯问题，也就是特定情景下的穷举问题，但是这其中会有一个从现实问题抽象到回溯的过程。那么理清楚这个过程就很重要。

从现实问题推到回溯

n皇后的问题总结：

• 首先进行隔行扫描，判断每一个落点是否满足要求，如果到最后不满足要求的话，就需要回溯到前面一行选择其他的点；

所以说这是一个遍历的过程，其本质就是暴力穷举，只不过它是一种特定情景（针对特定的序列）并且有规划的穷举，比起普通的横竖循环（指针对一个矩阵做横向以及纵向的for循环）的区别就是：有时候横竖都做一个for循环并不适应于实际情况，比如这里如果做两个for循环，就不好去判断什么时候的序列是满足n皇后的了，所以以n皇后为例，其实就是要有一个符合答案的序列，看这个序列是怎么一步步延伸的，如下图所示：

这里序列，从第一行到第n行，每一行都是一个，它是一层一层去提取一个节点，那么它的遍历过程就是进行每层遍历找到最后的节点找到合适的，如果不合适的就回退到前面，然后重新换一个节点选择，再进行之后序列的遍历，直到回退到第一层，这样就能够遍历所有的节点了。

总结——如何映射到现实问题：

• 首先看现实中是不是需要穷举，再看穷举的时候是不是产生序列

实现回溯

步骤：

1. 设置结束条件；
2. 遍历步骤（竖向、正反斜线，continue）；
3. 往下一列进行递归；
4. 回溯到前一个节点；

其他一个是把结果进行保存的，一个是把接口进行封装的。

0.实现关键算法

board来保存一次结果，queens保存了最后放皇后的位置

//回溯，计算board，将board保存下来
void backtrack(vector<vector<string>>& solutions, vector<int>& queens, int n, int row,
    unordered_set<int>& columns, unordered_set<int>& diagonals1, unordered_set<int>& diagonals2)
{

}
1
2
3
4
5
6

1.将结果进行保存

#include
//将结果保存到Board
vector<string> generateBoard(vector<int>& queens, int n) {
    auto board = vector<string>();
    for (int i = 0; i < n; i++) {
        string row = string(n, '.');
        row[queens[i]] = 'Q';
        board.push_back(row);
    }
    return board;
}
1
2
3
4
5
6
7
8
9
10
11

2.接口进行封装

//封装n皇后算法
vector<vector<string>> solveNQueens2(int n) {
    auto solutions = vector<vector<string>>();
    auto queens = vector<int>(n, -1);
	//利用三个不同方向的集合去保存
    auto columns = unordered_set<int>();
    auto diagonals1 = unordered_set<int>();
    auto diagonals2 = unordered_set<int>();
	//实际
    backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
    return solutions;
}
1
2
3
4
5
6
7
8
9
10
11
12

全部代码实现：https://github.com/xinhui1111/leetcodeDoit/blob/master/leetcodeDoit/n%E7%9A%87%E5%90%8E.cpp