8皇后问题的回溯算法实现C语言编写

8皇后问题是一个经典的回溯算法问题，涉及在一个8x8的棋盘上放置8个皇后，保证任何两个皇后都不会在同一行、同一列或对角线上。以下是使用C语言的基本回溯算法实现：

#include <stdio.h>
#define N 8

int board[N];
int row = 0;

// 检查当前位置是否可以放置皇后
int isSafe(int col, int n) {
    // 左上到右下的对角线范围
    for (int i = 0; i < row; i++) {
        if (board[i] == col || board[i] + i == col + n - 1)
            return 0;
    }
    return 1;
}

// 回溯函数，尝试将皇后放在当前列
void solveNQueens() {
    if (row >= N) { // 当所有皇后都放好，找到解
        printSolution();
        return;
    }

    for (int col = 0; col < N; col++) {
        if (isSafe(col, row)) {
            board[row] = col; // 放置皇后
            solveNQueens(); // 继续递归查找下一个位置
            board[row] = -1; // 回溯：移除皇后
        }
    }
}

// 打印解决方案
void printSolution() {
    printf("\n");
    for (int i = 0; i < N; i++, puts(""))
        for (int j = 0; j < N; j++)
            if (board[i] == j)
                printf("Q ");
            else
                printf(". ");
}

// 主函数
int main() {
    solveNQueens();
    return 0;
}

这个程序首先初始化一个大小为N的数组表示棋盘，然后通过递归的方式尝试在每一行放置皇后，如果当前位置安全，则继续放置下一行；如果不安全则回溯到前一步。当所有皇后都放置完毕，就找到了一个解并打印出来。