8皇后问题回溯法c++代码
时间: 2023-09-24 18:05:33 浏览: 57
以下是8皇后问题的回溯法C代码示例:
```
#include <stdio.h>
#include <stdlib.h>
#define N 8
int board[N][N] = {0}; // 棋盘,0表示没有放置皇后,1表示放置了皇后
int count = 0; // 解的个数
void print_board() { // 输出解
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");
}
}
int is_valid(int row, int col) { // 判断当前位置是否可以放置皇后
for (int i = 0; i < row; i++) { // 判断同一列是否有皇后
if (board[i][col] == 1) {
return 0;
}
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { // 判断左上角是否有皇后
if (board[i][j] == 1) {
return 0;
}
}
for (int i = row - 1, j = col + 1; i >= 0 && j < N; i--, j++) { // 判断右上角是否有皇后
if (board[i][j] == 1) {
return 0;
}
}
return 1;
}
void solve(int row) { // 回溯求解
if (row == N) { // 找到解
print_board();
return;
}
for (int i = 0; i < N; i++) { // 在当前行中逐个尝试放置皇后
if (is_valid(row, i)) {
board[row][i] = 1; // 放置皇后
solve(row + 1); // 递归到下一行
board[row][i] = 0; // 回溯
}
}
}
int main() {
solve(0);
printf("Total solutions: %d\n", count);
return 0;
}
```