CPP中的N位皇后

这个问题是将n个皇后放在棋盘上，这样就不会有两个皇后互相攻击。返回所有解决方案。

Example:

Input: 4

Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

介绍：

棋盘中的女王可以将其向左，向右和对角线移动。

然后，如果我们有一个带有“ n”个皇后的“ n * n”矩阵，则需要以这样的方式放置这四个皇后’t kill each other.

如果要找到最佳解决方案，则需要进行动态编程。在这里，我们只需要找到放置皇后的方法，因此我们将讨论回溯。

让我们以4 * 4木板为例，在（1，2）中放置一个女王（Queen），如下图所示：

因此，女王可以朝以下方向移动：

row: [1, 0], [1, 1], [1, 3]

column: [0, 2], [2, 2], [3, 2]

diagonal 1: [0, 1], [2, 3]

diagonal 2: [3, 0], [2, 1], [0, 3]

因此，从上表可以推断出，

1.第一排的新女王将受到攻击，

2.放置在第2列的新女王将受到攻击。

然后，我们有2个对角线。

1.对角1从左上方到右下方。

2.对角2从左下到右上。

对于对角线1，我们使用[行-列]。即[1 – 2] = -1。因此，如果任何行列的值为-1，则该单元格将被女王/王后攻击。

对于对角线2，我们使用[行+列]。即[1 + 2] =3。因此，如果任何行列的值为3，则该单元格将被女王/王后攻击。

我们如何找到解决问题的办法？

我们通过回溯来解决它。由于我们使用的是4 * 4矩阵，因此递归深度为4级。

首先，我们在[0，0]中放置一个女王。然后我们将2^nd 皇后，这样它就不会受到使用RECURSION的第一皇后的攻击。它可以显示如下：

矩阵如下所示：

现在，我们尝试将3^rd 女王，但我们没有安全的地方放置3个^rd 女王，因为它可能会受到其他2个女王的攻击。因此，递归函数将返回false，如下所示：

因此，我们回溯到2^nd 女王，然后尝试将其放置在下一个位置，然后尝试将3^rd 女王。因此，我们将3^rd 方框1中的女王。

现在，当放置4^日 女王，没有安全的地方。因此，递归函数将false返回3^rd 女王。

女王3也将false返回2^nd 女王，因为找不到安全的地方。

2^nd 女王将假返回1^ST 女王，因为找不到安全的地方。

现在必须移动女王1。一旦我们将女王1合1^ST 框，我们得到如下所示的解决方案。

CPP中的解决方案：

#include<iostream>
#include<vector>

using namespace STd;

bool Isvalid(vector<int> &a, int k) 
{
	for (int i = 0; i < k; i++) 
	{
		if (abs(k - i) == abs(a[i] - a[k]) || a[i] == a[k])
		{
			return false;
		}
	}
	return true;
}
void Backtrack(vector<vector<string> > &answers, vector<string> &answer, vector<int> &a, int deep) 
{
	if (deep >= answer.size()) 
	{
		answers.push_back(answer);
		return;
	} else 
	{
		for (int j = 0; j < answer[deep].size(); j++) 
		{
			a[deep] = j;
			if (Isvalid(a, deep)) 
			{
				answer[deep][j] = 'Q';
				Backtrack(answers, answer, a, deep + 1);
				answer[deep][j] = '.';
			}
		}
	}
}

vector<vector<string> > solveNQueens(int n) 
{
	vector<vector<string> > answers;
	vector<int> a(n, 0);
	vector<string> answer(n, STring(n, '.'));
	Backtrack(answers, answer, a, 0);

	return answers;
}


int main()
{
	int n = 4;

	vector<vector<string> > output =  solveNQueens(n);
	for (int i = 0; i < output.size(); i++)
	{
		for (int j = 0; j < output[0].size(); j++)
		{
			cout<< output[i][j]<<" ";
		}
		cout<<endl;
	}
}

输出：

.Q.. ...Q Q... ..Q.
..Q. Q... ...Q .Q..

该网站上可用的教程列表：