n皇后问题排列树方法c语言代码
时间: 2023-12-15 21:54:13 浏览: 23
以下是一个使用排列树方法解决 n 皇后问题的 C 语言代码:
```c
#include <stdio.h>
#define N 8
int board[N][N];
int count = 0;
void print_board() {
int i, j;
printf("Solution %d:\n", ++count);
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
printf("%d ", board[i][j]);
}
printf("\n");
}
}
int can_place(int row, int col) {
int i, j;
for (i = 0; i < row; i++) {
if (board[i][col]) return 0;
}
for (i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) return 0;
}
for (i = row-1, j = col+1; i >= 0 && j < N; i--, j++) {
if (board[i][j]) return 0;
}
return 1;
}
void solve(int row) {
int i, j;
if (row == N) {
print_board();
return;
}
for (i = 0; i < N; i++) {
if (can_place(row, i)) {
board[row][i] = 1;
solve(row+1);
board[row][i] = 0;
}
}
}
int main() {
solve(0);
return 0;
}
```
该代码中使用了回溯法,从第 0 行开始,逐行遍历,对于每一行,尝试在每一列上放置皇后,如果能放置,则继续递归处理下一行,如果不能放置,则回溯到上一行重新尝试其他列。在放置皇后之前,使用 `can_place` 函数检查该位置是否合法,即是否与已放置的皇后在同一列或同一对角线上。当遍历到第 N 行时,输出一组解。