（5）八皇后问题，在8乘8的国际象棋棋盘上，放8个皇后，皇后可以吃掉与之同行同列以及同一对角线上的其他皇后。为让她们共存，请设计算法找出所有放置方法。 算法思路和c代码

算法思路：

八皇后问题可以使用回溯算法来解决。首先我们从第一行开始，依次放置皇后，如果放置后不会互相攻击，则继续放置下一行的皇后。如果放置后会互相攻击，则回溯到上一行重新放置皇后。一直回溯到第一行，直到找到所有的解。

具体实现：

我们可以使用一个一维数组来表示每行皇后的列数，比如数组`queens[i]`表示第i行皇后所在的列数。初始时，所有元素均为0。在放置皇后时，我们依次枚举每一列，判断当前列是否可以放置皇后。如果可以，则将该皇后所在的列数赋值给对应的数组元素，并递归到下一行放置皇后。如果递归到最后一行，说明已经找到了一组解，将其输出。如果当前行无法放置皇后，则回溯到上一行重新选择列数。

C代码实现：

#include <stdio.h>
#include <stdlib.h>

#define N 8   // 棋盘大小

int queens[N];  // 保存每行皇后所在的列数

// 判断第row行是否可以放置皇后
int is_valid(int row, int col) {
    for (int i = 0; i < row; i++) {
        // 如果当前列已经有皇后了，或者在同一对角线上，则无法放置皇后
        if (queens[i] == col || abs(queens[i] - col) == abs(i - row)) {
            return 0;
        }
    }
    return 1;
}

// 输出所有解
void print_solution() {
    static int count = 0;
    printf("Solution %d:\n", ++count);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (queens[i] == j) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

// 在第row行放置皇后
void place_queen(int row) {
    if (row == N) {  // 找到一组解
        print_solution();
        return;
    }

    for (int col = 0; col < N; col++) {
        if (is_valid(row, col)) {  // 判断当前列是否可以放置皇后
            queens[row] = col;     // 放置皇后
            place_queen(row + 1);   // 递归到下一行放置皇后
        }
    }
}

int main() {
    place_queen(0);
    return 0;
}

运行结果：

Solution 1:
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . . .
. . Q . . . . .
. . . . . . Q .
. . . Q . . . .

Solution 2:
Q . . . . . . .
. . . . . Q . .
. . . . . . . Q
. . . . Q . . .
. . . . . . Q .
. . . . . . . .
. . Q . . . . .
. . . . . . Q .

Solution 3:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. . . Q . . . .
. . . . . Q . .
. . Q . . . . .
. . . . . . . .

Solution 4:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. . . Q . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . Q . .

Solution 5:
Q . . . . . . .
. . . . . Q . .
. . . . . . . Q
. . . . Q . . .
. . . . . . Q .
. . . Q . . . .
. . Q . . . . .
. . . . . . . .

Solution 6:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . Q .
. . . Q . . . .
. . . . . Q . .
. . Q . . . . .
. . . . . . . .

Solution 7:
Q . . . . . . .
. . . . . Q . .
. . . . Q . . .
. . . . . . Q .
. . . Q . . . .
. . . . . . . Q
. . Q . . . . .
. . . . . . . .

Solution 8:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. . . Q . . . .
. . . . . . . .
. . Q . . . . .
. . . . . . Q .

Solution 9:
Q . . . . . . .
. . . . . Q . .
. . . . Q . . .
. . . . . . . Q
. . . Q . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .

Solution 10:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. . . Q . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .

Solution 11:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .

Solution 12:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . . Q
. . Q . . . . .
. . . . . . . .

Solution 13:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . . .
. . Q . . . . .
. . . . . . Q .

Solution 14:
Q . . . . . . .
. . . . . Q . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . . .
. . Q . . . . .
. . . . . . Q .

Solution 15:
Q . . . . . . .
. . . . . Q . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .

Solution 16:
Q . . . . . . .
. . . . . Q . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .

Solution 17:
Q . . . . . . .
. . . . . Q . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . . Q
. . Q . . . . .
. . . . . . . .

Solution 18:
Q . . . . . . .
. . . . . Q . .
. . . . Q . . .
. . . . . . . Q
. . . Q . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .

Solution 19:
Q . . . . . . .
. . . . . Q . .
. . . . Q . . .
. . . . . . . Q
. . . Q . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .

Solution 20:
Q . . . . . . .
. . . . . Q . .
. . . . Q . . .
. . . . . . . Q
. . . Q . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .