回溯算法C实现

回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解的话（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即"回溯"。

在C语言中实现回溯算法，通常涉及递归和函数调用的堆栈。以下是一个使用回溯算法解决N皇后问题的示例。N皇后问题是一个经典的回溯问题，要求在N×N的棋盘上放置N个皇后，使得它们不能相互攻击（即任何两个皇后都不能处于同一行、同一列或同一对角线上）。

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 10

int n;
int col[MAX_SIZE]; // 用于标记某一列是否有皇后
int diag1[2 * MAX_SIZE - 1]; // 主对角线，从左上到右下
int diag2[2 * MAX_SIZE - 1]; // 副对角线，从右上到左下

bool canPlace(int row, int col) {
    if (col[col] || diag1[row - col + MAX_SIZE - 1] || diag2[row + col])
        return false;
    return true;
}

bool solveNQUtil(int row) {
    if (row == n) // 如果所有行都放置了皇后，则找到了一个解
        return true;

    for (int col = 0; col < n; col++) {
        if (canPlace(row, col)) {
            col[col] = diag1[row - col + MAX_SIZE - 1] = diag2[row + col] = 1;

            if (solveNQUtil(row + 1))
                return true;

            // 如果当前列不能放置皇后，则回溯，恢复状态
            col[col] = diag1[row - col + MAX_SIZE - 1] = diag2[row + col] = 0;
        }
    }

    return false;
}

bool solveNQ() {
    if (n <= 0 || n > MAX_SIZE)
        return false;

    if (!solveNQUtil(0))
        return false;

    return true;
}

void printSolution(int board[MAX_SIZE][MAX_SIZE]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            printf("%d ", board[i][j]);
        printf("\n");
    }
}

int main() {
    n = 4; // 可以修改n的值来尝试不同的N皇后问题

    if (!solveNQ()) {
        printf("Solution does not exist");
        return 0;
    }

    int board[MAX_SIZE][MAX_SIZE] = {0};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (col[j]) {
                board[i][j] = 1;
                break;
            }
        }
    }

    printSolution(board);

    return 0;
}

这个示例代码展示了如何使用回溯算法解决N皇后问题。solveNQUtil函数是核心的回溯函数，它尝试在每一行的每一列放置皇后，并通过递归和回溯来寻找所有可能的解。当找到解时，它将解打印到控制台。