八皇后问题 C语言代码

八皇后问题是一个经典的回溯算法问题，以下是一个基于C语言的解法示例：

#include <stdio.h>

#define N 8

int board[N][N]; // 棋盘

// 判断当前位置是否合法
int is_valid(int row, int col) {
    int i, j;
    // 检查列上是否有其他皇后
    for (i = 0; i < row; i++)
        if (board[i][col])
            return 0;
    // 检查左上方是否有其他皇后
    for (i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return 0;
    // 检查右上方是否有其他皇后
    for (i = row - 1, j = col + 1; i >= 0 && j < N; i--, j++)
        if (board[i][j])
            return 0;
    return 1;
}

// 尝试摆放皇后
int place_queen(int row) {
    int col;
    if (row == N) // 所有皇后已经摆放完毕
        return 1;
    for (col = 0; col < N; col++) {
        if (is_valid(row, col)) {
            board[row][col] = 1; // 摆放皇后
            if (place_queen(row + 1)) // 递归尝试摆放下一行皇后
                return 1;
            board[row][col] = 0; // 回溯，撤销摆放皇后
        }
    }
    return 0; // 无法摆放皇后
}

int main() {
    int i, j;
    place_queen(0); // 从第0行开始摆放皇后
    // 输出棋盘
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++)
            printf("%d ", board[i][j]);
        printf("\n");
    }
    return 0;
}

该代码通过递归回溯的方式，依次尝试在棋盘上摆放每一行的皇后，通过判断每个位置是否合法来进行摆放，如果无法摆放则回溯到上一行重新摆放。最终输出摆放皇后的棋盘。