题目：
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
Example 1:
Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1 Output: [["Q"]]
Constraints:
1 <= n <= 9
思路:
经典N皇后问题，用DFS回溯进行解决。首先初始化一个board，初始内容全为 ' . '，代表了未使用的格子，如果某个格子上要放皇后，我们把它变成字母 ' Q '。在主函数dfs中，我们首先要清楚逻辑小于row的行都已经成功放置了皇后，我们不用管。那么递归base case就是如果row到达了board边界以外，说明已经放置完成了，则这就是一种答案，要将当前board记录进结果中。如果row未达到边界之外，需要继续放置，则对于当前row的每一列进行check，如果不合理就跳过，如果合理就放置Q，并且继续递归，call完dfs函数后进行回溯即可。最后是一个check函数，因为我们是从第一行放置到最后一行，对于当前行来说，之后的行根本不用检查，因为还没放置。所以对于特定的一格，我们只要检查当前列，即这个[i , j]位置上面的所有行即可。这里分成三个方向，左上，右上和正上。正上只要从 i - 1 开始，保持 j 不变直到 i 为0即可；左上从i - 1，j - 1开始，每次都 i--, j--直到 i 为0或者 j 为0即可；同理，右上 左上从i - 1，j + 1开始，每次都 i--, j++直到 i 为0或者 j 为边界即可。
代码：
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n,string(n,'.'));
dfs(board,0);
return res;
}
private:
vector<vector<string>> res;
void dfs(vector<string> &board, int row)
{
if(row==board.size())
{
res.push_back(board);
return;
}
int n=board[row].size();
for(int i=0;i<n;i++)
{
if(!check(board,row,i))
continue;
board[row][i]='Q';
dfs(board,row+1);
board[row][i]='.';
}
}
bool check(vector<string>&board,int row, int col)
{
int n=board.size();
for(int i=0;i<row;i++)
{
if(board[i][col]=='Q')
return false;
}
for(int i=row-1, j=col-1;i>=0&&j>=0;i--,j--)
{
if(board[i][j]=='Q')
return false;
}
for(int i=row-1, j=col+1;i>=0&&j<n;i--,j++)
{
if(board[i][j]=='Q')
return false;
}
return true;
}
};