算法-排列组合|N皇后问题算法-排列组合|总结-深度优先

n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。

给定一个整数n，返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
您在真实的面试中是否遇到过这个题？ Yes 样例对于4皇后问题存在两种解决的方案：
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]

class Solution { public: /* * @param n: The number of queens * @return: All distinct solutions */ vector solveNQueens(int n) { // write your code here vector queens; vector nqueens; solveNQueens(n, 0, queens, nqueens); return nqueens; } void solveNQueens(int n, int line, vector& queens, vector& nqueens) { if (line == n) { nqueens.push_back(queens); return; } string linestr = string(n, '.'); for (int c = 0; c < n; c++) { bool canput = true; for (int l = 0; l < line; l++) { // duijiao if (queens[l][c] == 'Q' || (c + line - l < n && queens[l][c + line - l] == 'Q') || (c - line + l >= 0 && queens[l][c - line + l] == 'Q')) { canput = false; break; } } if (canput) { linestr[c] = 'Q'; queens.push_back(linestr); solveNQueens(n, line + 1, queens, nqueens); queens.pop_back(); linestr[c] = '.'; } } } };

【算法-排列组合|N皇后问题】