用C语言实现:键盘输入正整数n,求出n皇后问题的解法个数,输出至少2种放置方案
时间: 2024-02-12 17:07:29 浏览: 73
下面是使用C语言实现的键盘输入正整数n,求解n皇后问题的解法个数,并输出至少2种放置方案的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define N 100
int board[N][N] = {0}; // 棋盘,0表示空,1表示皇后
int count = 0; // 解法个数计数器
void print_board() { // 打印棋盘
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%c ", board[i][j] ? 'Q' : '.');
}
printf("\n");
}
printf("\n");
}
int check(int row, int col) { // 检查该位置是否可以放置皇后
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) { // 同一列
return 0;
}
if (col-row+i >= 0 && board[i][col-row+i] == 1) { // 左上方
return 0;
}
if (col+row-i < N && board[i][col+row-i] == 1) { // 右上方
return 0;
}
}
return 1;
}
void backtrace(int row, int n) { // 回溯法
if (row == n) { // 找到一组解
count++;
if (count <= 2) { // 输出至少2种放置方案
printf("Solution %d:\n", count);
print_board();
}
return;
}
for (int i = 0; i < n; i++) {
if (check(row, i)) {
board[row][i] = 1; // 放置皇后
backtrace(row + 1, n); // 继续下一行
board[row][i] = 0; // 回溯
}
}
}
int main() {
int n;
printf("Please enter n: ");
scanf("%d", &n);
backtrace(0, n); // 从第0行开始
printf("Total solutions: %d\n", count);
return 0;
}
```
在该代码中,使用二维数组 `board` 表示棋盘,其中0表示空,1表示皇后。`check` 函数用于检查该位置是否可以放置皇后,其检查同一列和同一斜线。`backtrace` 函数采用回溯法,从第0行开始,依次尝试每一列,如果该位置可以放置皇后,则继续下一行;如果该位置不行,则回溯到上一行重新尝试。当找到一组解时,调用 `print_board` 函数打印棋盘。`count` 变量用于计数解法个数。在 `main` 函数中,使用 `scanf` 函数从键盘输入正整数n,并调用 `backtrace` 函数求解n皇后问题,并输出至少2种放置方案和解法个数。
阅读全文