C语言解决八皇后问题

八皇后问题是指在一个8×8的棋盘上，放置8个皇后，使得任意两个皇后都不能在同一行、同一列或同一斜线上。这是一个著名的递归问题。下面是一个C语言实现八皇后问题的代码，以及对代码的讲解。

#include 

int board[8][8] = {0}; // 棋盘
int column[8] = {0}; // 列
int diagonal_1[15] = {0}; // 正对角线
int diagonal_2[15] = {0}; // 反对角线

void print_solution() {
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (board[i][j] == 1) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

void solve(int row) {
    if (row == 8) { // 找到一组解后，输出并返回
        print_solution();
        return;
    }
    for (int col = 0; col < 8; col++) {
        if (column[col] || diagonal_1[row+col] || diagonal_2[row-col+7]) { // 如果当前位置被攻击，则跳过
            continue;
        }
        board[row][col] = 1; // 放置皇后
        column[col] = 1; // 标记列
        diagonal_1[row+col] = 1; // 标记正对角线
        diagonal_2[row-col+7] = 1; // 标记反对角线
        solve(row+1); // 递归放置下一行皇后
        board[row][col] = 0; // 回溯
        column[col] = 0; // 回溯
        diagonal_1[row+col] = 0; // 回溯
        diagonal_2[row-col+7] = 0; // 回溯
    }
}

int main() {
    solve(0);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

首先定义了一个8×8的棋盘和三个长度为15的数组，用于记录哪些列、正对角线和反对角线已经被皇后占据。solve函数表示放置皇后的递归函数，其中row表示当前要放置皇后的行号。如果找到了一组可行解，则输出并返回。否则，对于每一列，如果当前位置可以放置皇后，则放置皇后并递归下一行。如果不能放置，则继续判断下一列。如果所有列都不能放置皇后，则回溯到上一行，并将之前标记的状态清除。

print_solution函数用于输出一组可行解。对于每一个位置，如果有皇后，则输出"Q"，否则输出"."

接下来是代码的运行流程：

1. main函数调用solve(0)
2. solve函数开始递归，第一行从左到右依次尝试放置皇后
3. 如果当前位置不能放置皇后，则跳过（继续循环），否则放置皇后并继续递归下一行
4. 如果已经放满了8行，则找到一组可行解，并输出
5. 回溯到上一行，并继续尝试下一列
6. 如果所有列都不能放置皇后，则回溯到上一行，并将之前标记的状态清除

最终，solve函数会找到所有可行解并输出。