c语言利用递归算法求解问题——n皇后问题输出所有的摆法

在C语言中，我们可以使用递归算法来解决经典的“n皇后问题”，即在一个n×n的棋盘上放置n个皇后，使得任意两个皇后都不会在同一行、同一列或对角线上。以下是基本的递归解决方案：

#include <stdio.h>

// 定义一个数组来表示每一行是否有皇后
int board[n];

// 用于存储已经放好皇后的列数
int col = 0;

// 递归函数，传入当前考虑的位置i和剩余的皇后数量n-i
void solveNQueens(int n, int i) {
    if (i >= n) { // 如果所有位置都填完了，打印结果
        for (int j = 0; j < n; j++) {
            printf("%d ", board[j]);
        }
        printf("\n");
        return;
    }

    // 尝试将皇后放在第i列
    for (int j = 0; j < n; j++) {
        // 检查当前位置是否冲突（不在同一行、同一列、对角线）
        if (isValid(i, j)) {
            board[i] = j;
            solveNQueens(n, i + 1); // 递归前进到下一个位置
        }
    }
}

// 检查放入位置(i, j)是否合法
int isValid(int row, int col) {
    // 判断冲突情况，注意对角线包括水平和斜线
    for (int k = 0; k < row; k++) {
        if (board[k] == col || abs(board[k] - col) == row - k) {
            return 0;
        }
    }
    return 1;
}

// 主函数入口
int main() {
    int n = 4; // 示例为4x4棋盘
    solveNQueens(n, 0);
    return 0;
}

当你运行这个程序时，它会输出n皇后问题的所有合法解，每种解都在新的一行。