八皇后问题回溯法c++

八皇后问题是一个经典的回溯算法问题，它要求在一个8x8的棋盘上放置8个皇后，使得每个皇后都不会相互攻击（即不在同一行、同一列或同一对角线）。下面是使用C语言实现的八皇后问题回溯算法代码：

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

#define N 8

int count = 0;  // 统计解的个数

// 判断是否可以在第row行第col列放置皇后
bool canPlace(int row, int col, int board[N][N]) {
    // 检查列是否有皇后
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 1) {
            return false;
        }
    }

    // 检查左上对角线是否有皇后
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) {
            return false;
        }
    }

    // 检查右上对角线是否有皇后
    for (int i = row - 1, j = col + 1; i >= 0 && j < N; i--, j++) {
        if (board[i][j] == 1) {
            return false;
        }
    }

    // 没有冲突
    return true;
}

// 递归回溯放置皇后
void placeQueen(int row, int board[N][N]) {
    // 找到一个解
    if (row == N) {
        count++;
        printf("Solution %d:\n", count);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                printf("%d ", board[i][j]);
            }
            printf("\n");
        }
        printf("\n");
        return;
    }

    // 在当前行的每一列尝试放置皇后
    for (int col = 0; col < N; col++) {
        if (canPlace(row, col, board)) {
            board[row][col] = 1;  // 放置皇后
            placeQueen(row + 1, board);  // 递归放置下一行
            board[row][col] = 0;  // 回溯，撤回皇后
        }
    }
}

int main() {
    int board[N][N] = {0};  // 初始化棋盘
    placeQueen(0, board);  // 从第0行开始放置皇后
    printf("Total solutions: %d\n", count);
    return 0;
}

在上面的代码中，canPlace函数用于判断是否可以在第row行第col列放置皇后，placeQueen函数用于递归回溯放置皇后，count变量用于统计解的个数。在主函数中，初始化棋盘并从第0行开始放置皇后，最后输出解的个数。