# N 皇后

<p><strong>n 皇后问题</strong> 研究的是如何将 <code>n</code> 个皇后放置在 <code>n×n</code> 的棋盘上，并且使皇后彼此之间不能相互攻击。</p><p>给你一个整数 <code>n</code> ，返回所有不同的 <strong>n<em> </em>皇后问题</strong> 的解决方案。</p><div class="original__bRMd"><div><p>每一种解法包含一个不同的 <strong>n 皇后问题</strong> 的棋子放置方案，该方案中 <code>'Q'</code> 和 <code>'.'</code> 分别代表了皇后和空位。</p><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/queens.jpg" style="width: 600px; height: 268px;" /><pre><strong>输入：</strong>n = 4<strong><br />输出：</strong>[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]<strong><br />解释：</strong>如上图所示，4 皇后问题存在两个不同的解法。</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>n = 1<strong><br />输出：</strong>[["Q"]]</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>1 <= n <= 9</code></li>	<li>皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。</li></ul></div></div>

以下程序实现了这一功能，请你填补空白处的内容：

```cpp
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
	vector<vector<string>> solveNQueens(int n)
	{
		vector<vector<string>> res;
		vector<int> stack(n);
		vector<string> solution(n, string(n, '.'));
		dfs(n, 0, stack, solution, res);
		return res;
	}
private:
	void dfs(int n, int row, vector<int> &stack, vector<string> &solution, vector<vector<string>> &res)
	{
		if (row == n)
		{
			res.push_back(solution);
		}
		else
		{
			for (int i = 0; i < n; i++)
			{
				if (row == 0 || !conflict(stack, row, i))
				{
					__________________;
				}
			}
		}
	}
	bool conflict(vector<int> &stack, int row, int col)
	{
		for (int i = 0; i < row; i++)
		{
			if (col == stack[i] || abs(row - i) == abs(col - stack[i]))
			{
				return true;
			}
		}
		return false;
	}
}
```

## template

```cpp
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
	vector<vector<string>> solveNQueens(int n)
	{
		vector<vector<string>> res;
		vector<int> stack(n);
		vector<string> solution(n, string(n, '.'));
		dfs(n, 0, stack, solution, res);
		return res;
	}
private:
	void dfs(int n, int row, vector<int> &stack, vector<string> &solution, vector<vector<string>> &res)
	{
		if (row == n)
		{
			res.push_back(solution);
		}
		else
		{
			for (int i = 0; i < n; i++)
			{
				if (row == 0 || !conflict(stack, row, i))
				{
					solution[row][i] = 'Q';
					stack[row] = i;
					dfs(n, row + 1, stack, solution, res);
					solution[row][i] = '.';
				}
			}
		}
	}
	bool conflict(vector<int> &stack, int row, int col)
	{
		for (int i = 0; i < row; i++)
		{
			if (col == stack[i] || abs(row - i) == abs(col - stack[i]))
			{
				return true;
			}
		}
		return false;
	}
}
```

## 答案

```cpp
solution[row][i] = 'Q';
stack[row] = i;
dfs(n, row + 1, stack, solution, res);
solution[row][i] = '.';
```

## 选项

### A

```cpp
solution[row][i] = 'Q';
stack[row] = i;
dfs(n, row, stack, solution, res);
solution[row][i] = '.';
```

### B

```cpp
solution[row][i] = '.';
stack[row] = i;
dfs(n, row + 1, stack, solution, res);
solution[row][i] = 'Q';
```

### C

```cpp
solution[row][i] = '.';
stack[row] = i;
dfs(n, row, stack, solution, res);
solution[row][i] = 'Q';
```