一、什么是八皇后问题
八皇后问题是指在 8*8 各的国际棋盘上摆放八个皇后，使其不能互相攻击，即 任意两个皇后都不能处于同一行、同一列或同一斜线上，问一个有多少种摆法。
八皇后问题算法思路分析：
第一个皇后先放第一行第一列。
第二个皇后放在第二行第一列，然后判断是否 OK，如果不 OK，继续放第二列、第三列、依次把所有列都放完，找到一个合适的。
继续放第三个皇后，还是第一列、第二列 …… 直至第 8 个皇后也能放在一个不冲突的位置，算是找到一个正确解。
当得到第一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到。
然后回头继续第一个皇后放第二列，后面继续循环执行 1, 2, 3 的步骤。
#include
#include
#include
void PlaceQueen(int Array[], int QueenCount, int N);
int Judge(int Array[], int N);
void Print(int Array[], int QueenCount);
int main()
{
int QueenCount = 8;
int Array[QueenCount];
memset(Array, 0, sizeof(Array));
PlaceQueen(Array, QueenCount, 0);
return 0;
}
/**
* @brief 放置第N个皇后
*
* @param Array 棋盘
* @param QueenCount 皇后的个数
* @param N 第N个皇后
*
* @note PlaceQueen() 每次递归时，进入PlaceQueen()都有for循环，因此会产生回溯
*/
void PlaceQueen(int Array[], int QueenCount, int N)
{
if (N == QueenCount)
{
PrintEightQueens(Array, QueenCount);
}
// 依次放入皇后，并判断是否冲突
for (int i = 0; i < QueenCount; i++)
{
// 先将当前这个皇后N放到该函的第一列
Array[N] = i;
// 判断当N个皇后放置在i列时是否冲突
if (Judge(Array, N))
{
// 如果不冲突，继续放N+1个皇后
PlaceQueen(Array, QueenCount, N + 1);
}
// 如果冲突，则继续执行Array[N]=i，即将第N个皇后放置本行后移一列的位置
}
}
/**
* @brief 判断第N个皇后与前N-1个皇后之间是否有冲突
*
* @param Array 棋盘
* @param N 第N个皇后
* @return int 0: 有冲突; 1: 无冲突
*/
int Judge(int Array[], int N)
{
// 判断第N个皇后与前N-1个皇后之间是否有冲突
for (int i = 0; i < N; i++)
{
// 判断是否在同一列或同一斜线上
// 同一条斜线，角度为45°，斜率为1或-1
if (Array[i] == Array[N] || abs(Array[N] - Array[i]) == N - i)
{
return 0;
}
}
return 1;
}
/**
* @brief 打印解法
*
* @param Array 棋盘
* @param QueenCount 皇后的个数
*/
void PrintEightQueens(int Array[], int QueenCount)
{
static int count = 0;
count++;
printf("第 %d 种解法：\n", count);
for (int i = 0; i < QueenCount; i++)
{
printf("第 %d 个皇后放在第 %d 行，第 %d 列\n", i + 1, i + 1, Array[i] + 1);
}
printf("\n");
}
理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一位数组即可解决问题。对于一维数组 array[i] 而言，数组的下标（i）表示第几行，对应的值表示第几列。数组的第 i+1 个皇后应该放到第 i+1 行，第 array[i]+1 列。