骑士游历问题C语言解法

骑士游历问题，也称为八皇后问题，是一个经典的回溯算法示例。它的目标是在一个8x8的棋盘上放置八个皇后，使得任意两个皇后都不能处于同一行、同一列或同一对角线上。以下是使用C语言的一个基本解法：

#include <stdio.h>
#define N 8

// 定义一个数组来表示棋盘，0表示空位，1表示有皇后
int board[N];

// 检查当前位置是否安全，即不存在冲突
int is_safe(int row, int col) {
    // 检查同列是否有皇后
    for (int i = 0; i < row; i++)
        if (board[i] == col)
            return 0;
    
    // 检查左上方对角线是否有皇后
    int di = row - col;
    for (int i = 0; i < di; i++)
        if (board[i] == col + i)
            return 0;

    // 检查右上方对角线是否有皇后
    di = N - row - col;
    for (int i = 0; i < di; i++)
        if (board[i] == col + i)
            return 0;

    return 1;
}

// 回溯函数，尝试在row位置放置皇后，如果成功则递归继续，否则回溯到前一个位置
void solve_n_queens(int row) {
    if (row >= N) {
        // 找到了一个解决方案，打印出来
        print_solution(board);
        return;
    }

    for (int col = 0; col < N; col++) {
        if (is_safe(row, col)) {
            // 将皇后放在col位置
            board[row] = col;
            // 继续处理下一行
            solve_n_queens(row + 1);
        }
    }
}

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

int main() {
    solve_n_queens(0);
    return 0;
}