当前位置：首页 > news >正文

C语言解决八皇后问题

news 2025/9/15 3:22:07

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

#include <stdio.h>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;
}

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

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

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