C语言递归算法八皇后问题

C语言中的八皇后问题是一个经典的回溯算法示例，用于在一个8x8的棋盘上放置八个皇后，使得任意两个皇后都不在同一行、同一列以及对角线上。这个问题通常通过递归来解决，步骤大致如下：

1. 定义基本情况：如果已经放了n个皇后，说明解决方案找到，返回n作为有效解。
2. 递归函数：对于每个空的位置i，尝试将其设置为皇后，然后对剩余的7个位置递归调用函数，检查当前位置是否违反了规则。
3. 检查冲突：检查i行的同行、同列以及左上和右上对角线上的位置是否有皇后，若有，则回溯到上一步，将当前位置改为其他值，继续尝试下一个位置。
4. 回溯：若所有位置都试过而没有找到解决方案，需要回溯至上一步，移除刚刚尝试放置的皇后，并尝试下一个位置。

以下是简单的C语言代码实现八皇后问题的递归思路：

#include <stdio.h>

// 假设皇后在row[i]列
int isSafe(int row[], int col, int n) {
    // 检查该行是否有皇后
    for (int i = 0; i < col; i++)
        if (row[i] == col)
            return false;
    
    // 检查左上方对角线是否有皇后
    for (int i = 0; i < col - row[i]; i++)
        if (row[i] == col - i)
            return false;
            
    // 检查右上方对角线是否有皇后
    for (int i = n - row[i]; i < n - col; i++)
        if (row[i] == n - i)
            return false;
        
    return true;
}

void solveNQueens(int n, int* board) {
    if (n == 0) {
        printBoard(board, n);
        printf("\n");
        return;
    }
    
    // 从第一个空位开始
    for (int i = 0; i < n; ++i) {
        if (isSafe(board, i, n)) {
            board[n - 1] = i; // 设置皇后在i列
            
            // 对剩余位置递归求解
            solveNQueens(n - 1, board);
            
            // 回溯：如果找不到解，则撤消放置皇后
            board[n - 1] = -1; // 清除当前位置
        }
    }
}

void printBoard(int board[], int size) {
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j)
            printf("%d ", board[j] == i ? "Q" : ".");
        printf("\n");
    }
}

int main() {
    int n = 8;
    int board[n];
    solveNQueens(n, board);
    return 0;
}