在C语言中用递归算法求解n皇后问题

在C语言中，使用递归算法解决n皇后问题是经典的计算机科学问题，它涉及在一个n×n的棋盘上放置n个皇后，使得任意两个皇后都不在同一行、同一列或对角线上。这是一个典型的回溯法应用。

以下是递归函数的基本结构：

#include <stdio.h>

void solveNQueens(int n, int row, int** board) {
    if (row == n) { // 如果已经放完所有皇后，解决方案找到，打印并返回
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("%d ", board[i][j]);
            }
            printf("\n");
        }
        return;
    }

    // 遍历每一列
    for (int col = 0; col < n; col++) {
        if (isValidPosition(n, row, col, board)) { // 检查当前位置是否合法
            board[row][col] = 1; // 放置皇后
            solveNQueens(n, row + 1, board); // 递归处理下一行
            board[row][col] = 0; // 回溯，如果当前解决方案不行，则移除皇后
        }
    }
}

// 检查在给定位置放置皇后是否违反规则
int isValidPosition(int n, int row, int col, int** board) {
    // 检查列冲突、左上到右下对角线冲突以及右上到左下对角线冲突
    for (int i = 0; i < row; i++) {
        if (board[i][col] || board[row - i][col - i] || board[row - i][col + i]) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int n;
    scanf("%d", &n);
    int* board = new int[n][n]; // 初始化二维数组

    solveNQueens(n, 0, board);

    delete[] board;
    return 0;
}