用C语言写回溯问题 皇后问题

在C语言中，皇后问题通常是指经典的八皇后问题，它是一个典型的回溯算法应用场景。目标是在一个8x8的棋盘上放置八个皇后，使得任意两个皇后都不会在同一行、同一列或对角线上。以下是简单的C语言代码实现：

#include <stdio.h>
#define N 8

// 检查皇后是否可以安全放置在(row, col)
int is_safe(int row, int col, int board[N]) {
    // 检查同一行是否有其他皇后
    for (int i = 0; i < row; i++) {
        if (board[i] == col) return 0;
    }
    // 检查左上方对角线是否有皇后
    int-diagonal = row - col;
    for (int i = 0; i < diagonal; i++) {
        if (board[i] == col) return 0;
    }
    // 检查右上方对角线是否有皇后
    int+diagonal = row + col;
    for (int i = 0; i < N - diagonal; i++) {
        if (board[i] == col) return 0;
    }
    return 1;
}

// 回溯函数，递归地尝试在每行放置皇后
void solveNQueens(int row, int board[N]) {
    if (row >= N) {  // 如果所有皇后都放置好了
        print_board(board);  // 打印解决方案
        return;
    }

    // 对每列进行尝试
    for (int col = 0; col < N; col++) {
        if (is_safe(row, col, board)) {
            board[row] = col;  // 将皇后放在该位置
            solveNQueens(row + 1, board);  // 递归向下一层
        }
    }
}

// 打印解决方案的棋盘
void print_board(int board[N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", board[j]);
        }
        printf("\n");
    }
}

int main() {
    int board[N];
    solveNQueens(0, board);
    return 0;
}