int queen[N]={0}表示这个数组里的元素全部是0,怎么能表示皇后所在的列数呢?
时间: 2023-03-22 11:01:33 浏览: 39
可以将intqueen[N]中的每个元素作为皇后所在的行数,即intqueen[i]表示第i行的皇后所在的列数。因为每一行只能放一个皇后,所以这样表示每个元素都是不同的,可以用于记录每个皇后所在的列数。如果intqueen[i]的值为j,则表示第i行的皇后在第j列。
相关问题
N 皇后问题(queen)
N 皇后问题是一个经典的回溯算法问题,其目标是在 N x N 的棋盘上放置 N 个皇后,使得每个皇后都不会互相攻击,即同一行、同一列、同一对角线上都只有一个皇后。以下是一个 Python 的解决方案:
```python
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def DFS(queens, xy_dif, xy_sum):
p = len(queens)
if p==n:
result.append(queens)
return None
for q in range(n):
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([],[],[])
return [["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
```
其中,DFS 函数用于递归求解,queens 数组记录每行皇后所在的列数,xy_dif 数组记录每个位置的 x-y 值之差,xy_sum 数组记录每个位置的 x+y 值之和。在递归过程中,如果已经放置了 N 个皇后,则将当前解加入结果数组中。否则,对于每一列,判断该列是否可以放置皇后,如果可以,则继续递归放置下一行皇后。
以下是一个 N=4 的例子的输出结果:
```
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
```
用C语言实现:键盘输入正整数n,求出n皇后问题的解法个数,输出2种放置方案
这个问题需要用到回溯算法来解决。具体实现步骤如下:
1. 定义一个数组 record 存储每一行皇后的位置,初始值都为 -1。
2. 定义一个函数 check,用来判断当前的皇后放置在第 row 行第 col 列是否合法。合法的条件是:当前位置上方没有皇后,左上角和右上角也没有皇后。
3. 定义一个递归函数 queen,用来放置皇后。首先判断当前行是否已经放置好了皇后,如果已经放好了,就记录一种方案。如果还没放好,就遍历当前行的每一列,尝试将皇后放在该位置上,如果合法就继续递归放下一行的皇后,如果不合法就换下一列。
4. 主函数中接收用户输入的正整数 n,然后调用 queen 函数开始计算皇后放置方案个数。
5. 在 queen 函数中记录方案的方式可以是:定义一个二维数组 solutions,记录每个方案的皇后位置。在 queen 函数中记录每一次成功的放置,然后在主函数中输出两个方案。
完整代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 20
int record[MAX_N]; // 存储每行皇后的位置
int solutions[MAX_N][MAX_N]; // 存储每个方案的皇后位置
int count = 0; // 放置方案个数
int check(int row, int col) {
// 判断当前位置是否合法
for (int i = 0; i < row; i++) {
if (record[i] == col || abs(record[i] - col) == abs(i - row)) {
return 0;
}
}
return 1;
}
void queen(int row, int n) {
if (row == n) {
// 记录一种放置方案
for (int i = 0; i < n; i++) {
solutions[count][i] = record[i];
}
count++;
return;
}
for (int col = 0; col < n; col++) {
if (check(row, col)) {
// 当前位置合法,放置皇后
record[row] = col;
queen(row + 1, n);
record[row] = -1; // 回溯
}
}
}
int main() {
int n;
printf("请输入皇后数量:");
scanf("%d", &n);
queen(0, n);
printf("总共有%d种放置方案,其中两种方案如下:\n", count);
for (int i = 0; i < 2; i++) {
printf("方案%d:\n", i + 1);
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (solutions[i][row] == col) {
printf("Q ");
} else {
printf(". ");
}
}
printf("\n");
}
}
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)