八皇后问题回溯法c++

八皇后问题是指在一个 8*8 的棋盘上放置 8 个皇后，使得任意两个皇后都不能在同一行、同一列或同一斜线上。这是一个经典的回溯法问题，以下是 C 语言实现代码：

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

#define N 8 // 棋盘大小

int count = 0; // 解的个数

// 检查当前位置能否放置皇后
bool check(int board[][N], int row, int col) {
    int i, j;

    // 检查列
    for (i = 0; i < row; i++) {
        if (board[i][col]) {
            return false;
        }
    }

    // 检查左上斜线
    for (i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j]) {
            return false;
        }
    }

    // 检查右上斜线
    for (i = row - 1, j = col + 1; i >= 0 && j < N; i--, j++) {
        if (board[i][j]) {
            return false;
        }
    }

    return true;
}

// 放置皇后
void place_queen(int board[][N], int row) {
    int i, j;

    if (row == N) { // 找到一个解
        printf("Solution %d:\n", ++count); // 输出解的编号
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                printf("%c ", board[i][j] ? 'Q' : '.'); // 输出棋盘
            }
            printf("\n");
        }
        printf("\n");
        return;
    }

    for (j = 0; j < N; j++) {
        if (check(board, row, j)) { // 当前位置能放皇后
            board[row][j] = 1; // 放置皇后
            place_queen(board, row + 1); // 继续放下一行
            board[row][j] = 0; // 回溯
        }
    }
}

int main() {
    int board[N][N] = {0}; // 初始化棋盘

    place_queen(board, 0); // 从第一行开始放皇后

    printf("Total Solutions: %d\n", count); // 输出解的总数

    return 0;
}

在上面的代码中，`check` 函数用于检查当前位置能否放皇后，`place_queen` 函数用于放置皇后，`main` 函数用于初始化棋盘和调用 `place_queen` 函数。最后，输出解的总数。