c 语言八皇后问题回溯法

八皇后问题是指在8×8的棋盘上摆放8个皇后，使得每个皇后都无法攻击到其他皇后。其中，皇后可以攻击到同一行、同一列、同一斜线上的任意棋子。

回溯法是一种常用于求解搜索问题的算法。在八皇后问题中，回溯法的基本思路是：从棋盘的第一行开始，依次尝试在不违反规则的情况下放置皇后。如果当前行无法放置皇后，则回溯到上一行重新放置。直到所有行都放置完毕，就找到了一组解。

以下是C语言实现八皇后问题的回溯法代码：

#include <stdio.h>
#define N 8

int chessboard[N][N] = {0}; // 棋盘上皇后的位置
int count = 0; // 解的个数

void printChessboard() // 输出棋盘
{
    int i, j;
    printf("第%d个解：\n", count);
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++)
            printf("%d ", chessboard[i][j]);
        printf("\n");
    }
}

int check(int row, int col) // 判断当前位置是否可以放置皇后
{
    int i, j;
    for (i = 0; i < row; i++) {
        if (chessboard[i][col] == 1) // 判断同一列是否已经放置过皇后
            return 0;
        if (col-1-i >= 0 && chessboard[row-1-i][col-1-i] == 1) // 判断左上角是否已经放置过皇后
            return 0;
        if (col+1+i < N && chessboard[row-1-i][col+1+i] == 1) // 判断右上角是否已经放置过皇后
            return 0;
    }
    return 1;
}

void findSolution(int row) // 回溯法求解
{
    int j;
    if (row == N) { // 找到一组解
        count++;
        printChessboard();
        return;
    }
    for (j = 0; j < N; j++) {
        if (check(row, j)) { // 当前位置可以放置皇后
            chessboard[row][j] = 1;
            findSolution(row+1); // 继续尝试下一行
            chessboard[row][j] = 0; // 回溯到上一行重新尝试
        }
    }
}

int main()
{
    findSolution(0);
    printf("共有%d种解法\n", count);
    return 0;
}

在该程序中，使用一个二维数组`chessboard`表示棋盘上皇后的位置。其中，数组元素为1表示该位置放置了皇后，为0表示该位置未放置皇后。`check`函数用于判断当前位置是否可以放置皇后。`findSolution`函数是回溯法的核心部分，用于递归求解八皇后问题。在`main`函数中，调用`findSolution`函数求解八皇后问题。