C语言基于回溯算法解决八皇后问题的方法

什么是八皇后问题？

八皇后问题是一个经典的、古老的问题，它的目标是在一个8x8的棋盘上放置8个皇后，使得每个皇后都无法互相攻击，即两个皇后不能在同一行、同一列或同一对角线上。

回溯算法解决八皇后问题

回溯算法(Backtracking Algorithm)，又称试探法，是一种系统地搜索问题的解的算法。它的基本思想是从问题的解空间树上搜索出一个解，如果此解不符合要求，则回溯到上一层，继续搜索下一个解。

在八皇后问题中，我们可以将棋盘看作一个二维数组，尝试在每一行放置一个皇后，直到最后一行。每当我们放置一个皇后时，都需要检查是否与之前的皇后冲突。如果冲突，就回溯到上一行重新放置皇后。

下面是基于回溯算法的C语言程序：

#include <stdio.h>
#include <stdbool.h>

#define N 8 // 棋盘的大小
int pos[N]; // 存放每行皇后的位置

void print_board() // 打印棋盘
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (pos[i] == j)
                printf("Q ");
            else
                printf(". ");
        }
        printf("\n");
    }
    printf("\n");
}

bool check(int row, int col) // 检查是否与之前的皇后冲突
{
    for (int i = 0; i < row; i++) {
        if (pos[i] == col // 同一列
            || pos[i] - i == col - row // 左上到右下对角线
            || pos[i] + i == col + row) // 右上到左下对角线
            return false;
    }
    return true;
}

void place(int row) // 在指定行放置皇后
{
    if (row == N) { // 找到解
        print_board();
        return;
    }

    for (int col = 0; col < N; col++) { // 枚举每一列
        if (check(row, col)) { // 检查是否与之前的皇后冲突
            pos[row] = col; // 存储皇后的位置
            place(row + 1); // 继续放置下一个皇后
        }
    }
}

int main()
{
    place(0); // 从第0行开始放置皇后
    return 0;
}

示例说明

示例一

假设我们在第0行放置了一个皇后，仅考虑第1行时有以下两种可能：

• 在第1行的第1列放置皇后；
• 在第1行的第2列放置皇后。

在第一种情况下，由于第0行的皇后在第1列，与第1行的皇后在同一列，因此有一个冲突。所以我们需要回溯到第0行，重新放置皇后。

在第二种情况下，第0行的皇后和第1行的皇后不会互相攻击，因此可以继续考虑第2行。

示例二

假设我们在第0行放置了一个皇后，考虑到第1行和第2行时，每行都只有一种可能，因此可以直接放置皇后。但是在第3行时，我们发现所有的列都会与之前的皇后冲突。所以我们需要回溯到第2行，尝试将皇后放到另一个位置。如果所有的可能都被尝试过了，仍然找不到解，则需要回溯到第1行，重新开始尝试。