参考了这篇题解 N皇后问题，典型的回溯。先看暴力做法，就是把第一个皇后放在第一行第一列，然后再把第二个皇后放在第二行，这样试试试不行了就回去，但是你的棋盘已经改了，回去的话再改棋盘就很麻烦
题外话：【这里可以发现就是树的前序遍历：根→子树从左到右】【树的遍历共有5中：前序（根→左子树→右子树）、中序（左→根→右）、后序（左→右→根）、bfs、dfs（一枝搜到底，再回到根节点去搜它的其他子树） 我以前不知道它们有什么用_(:з」∠)_原来是可以和实际的搜索结合起来的（看了这篇学到了）】
所以我们改成回溯，关键就是假装把皇后放在这，递归下去搜索，搜完之后再把皇后给移走（详见solve函数）
class Solution { public: void solve(vector<vector<string>> &ans, vector<string> qipan, int row) { int n = qipan.size(); if (row == n) { //printf("yes\n"); ans.push_back(qipan); return; } for (int i = 0; i < n; i++) { if (vaild(qipan, row, i)) { qipan[row][i] = 'Q'; solve(ans, qipan, row + 1); qipan[row][i] = '.'; } } } //它是一行行往下走的，因此只需判断上面有没有皇后 bool vaild(vector<string> qipan, int row, int col) { int n = qipan.size(); for (int i = row - 1; i >= 0; i--) { if (qipan[i][col] == 'Q') return false; } for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (qipan[i][j] == 'Q') return false; } for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (qipan[i][j] == 'Q') return false; } return true; } vector<vector<string>> solveNQueens(int n) { vector<vector<string>> ans; vector<string> qipan; for (int i = 0; i < n; i++) { string s; for (int j = 0; j < n; j++) { s += '.'; } qipan.push_back(s); } solve(ans, qipan, 0); return ans; } };代码实际的编写中有几个小难题： 1、最终返回的vector<vector<stirng>>和实际的棋盘 vector<string>不同 2、vector<string>的初始化，用到了string的+=和vector的push_back 3、c++ class我还不是太熟，public和private里面哪些参数能共用根本不知道，导致我把ans传给solve函数但是最终在主体函数里返回的ans里啥都没有，所以solve函数传参的时候加了一个地址符。太不熟了，这一块简直一点不会，导致传什么参数就都是在瞎写。 4、我才知道for循环终止条件如果有两个的话不能像初始条件一样直接写逗号，而是要用&& = = for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)这要是编译器没提示就死了…
然鹅写完了之后 贼慢…我猜是vector的锅…但是运行速度和空间这一块我几乎一窍不通，等以后学懂一些再回来看吧
明明搜索也不是那么难…为什么以前我都学的半懂不懂的？？？可能是长大了？
