四皇后（4 Queens） 问题是指在一个 4 x 4 的棋盘上放置四个皇后，使得它们之间互不攻击。也就是说，不允许任何两个皇后处于 同一行、同一列 或 同一对角线 上。
在本文中，我们将一起探讨如何在 4 x 4 的棋盘上找到当 n=4 时的解决方案。
使用 回溯算法（Backtracking Algorithm） 解决四皇后问题：
> 我们从最上面的一行开始，尝试在不同的行中逐个放置皇后。在某一行的特定列放置皇后时，我们会检查它与已放置的皇后是否存在冲突。对于任何一列，如果没有冲突，我们就将皇后放在那里，并将该行和该列标记为解决方案的一部分。如果在放置过程中由于冲突导致找不到安全的格子，那么我们就进行回溯（即撤销最近一次皇后的放置）并返回 false。
四皇后解决方案图解：
步骤 0： 初始化一个 4×4 的棋盘。
!image.png)
步骤 1：
- 将我们的第一个皇后 (Q1) 放在 (0,0) 格子中。
- ‘x‘ 代表不安全的格子，即它们处于皇后 (Q1) 的攻击范围内。
- 完成此操作后，移动到下一行 [ 0 -> 1 ]。
!1
步骤 2：
- 将我们的下一个皇后 (Q2) 放在 (1,2) 格子中。
- 完成此操作后，移动到下一行 [ 1 -> 2 ]。
!2
步骤 3：
- 在第 2 行中，没有安全的格子可以放置皇后 (Q3)。
- 因此，我们需要回溯，并将皇后 Q2 从格子 ( 1, 2 ) 移除。
步骤 4：
- 在第 1 行中仍然有一个安全的格子，即格子 ( 1, 3 )。
- 将皇后 ( Q2 ) 放在格子 ( 1, 3)。
!3
步骤 5：
- 将皇后 ( Q3 ) 放在格子 ( 2, 1 )。
!4
步骤 6：
- 在第 3 行没有格子可以放置皇后 ( Q4 )。
- 回溯并将皇后 ( Q3 ) 从第 2 行移除。
- 由于第 2 行仍然没有其他安全的格子，所以我们再次回溯，并将皇后 ( Q2 ) 从第 1 行移除。
- 皇后 ( Q1 ) 将从格子 (0,0) 被移除，并移动到下一个安全的格子，即 (0 , 1)。
步骤 7：
- 将皇后 Q1 放在格子 (0 , 1)，然后移动到下一行。
!5
步骤 8：
- 将皇后 Q2 放在格子 (1 , 3)，然后移动到下一行。
!8
步骤 9：
- 将皇后 Q3 放在格子 (2 , 0)，然后移动到下一行。
!9
步骤 10：
- 将皇后 Q4 放在格子 (3 , 2)，然后移动到下一行。
- 这是解决方案的一种可能配置。
!10
按照以下步骤来实现这个想法：
- 创建一个递归函数，该函数将棋盘的状态和当前行号作为其参数。
- 从最上面的一行开始。
- 如果所有皇后都已放置，则返回 true。
- 对于每一行，执行以下操作：
– 对当前行中的每一列执行以下操作。
– 如果皇后可以安全地放置在这一列
– 那么标记这个 [行, 列] 作为解决方案的一部分，并递归检查将皇后放在这里是否能导出一个解决方案。
– 如果在 [行, 列] 放置皇后能导出一个解决方案，返回 true。
– 如果放置皇后没有导出解决方案，则取消标记这个 [行, 列] 并回溯，尝试其他列。
– 如果所有列都已尝试过但都没有成功，返回 false 以触发回溯。
下面是上述回溯解决方案的实现代码：
C++
// C++ program to solve N Queen Problem using backtracking
#include
using namespace std;
#define N 4
// ld is an array where its indices indicate row-col+N-1
// (N-1) is for shifting the difference to store negative
// indices
int ld[30] = { 0 };
// rd is an array where its indices indicate row+col
// and used to check whether a queen can be placed on
// right diagonal or not
int rd[30] = { 0 };
// Column array where its indices indicates column and
// used to check whether a queen can be placed in that
// row or not*/
int cl[30] = { 0 };
// A utility function to print solution
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << " " << (board[i][j]==1?'Q':'.') << " ";
cout << endl;
}
}
// A recursive utility function to solve N
// Queen problem
boo