首页 > 代码库 > 八皇后问题（回溯）

八皇后问题（回溯）

2024-07-06 22:31:29   235人阅读

+ View Code?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 8
int arr[N];
void queens(int *arr);
int checkPosition(int *arr, int i);
int main()
{
// 初始化数组
    int i;
    for(i = 0; i < N; i++) {
        arr[i] = 0;
    }
 
// 排列皇后
    queens(arr);
 
    system("PAUSE");
    return 0;
}
 
// 排列皇后
void queens(int *arr)
{
// 初始化变量
    int i = 1;
    int j, k;
 
// 有多少种解
    int total = 0;
 
    while(i >= 1) {
// 在下一个位置放置第 i 个皇后
        arr[i] = arr[i] + 1;
 
// 检查皇后放置的位置是否合法
        while(arr[i] <= N && !checkPosition(arr, i)) {
// 搜索下一列
            arr[i] = arr[i] + 1;
        }
        //得到一个输出
        if(arr[i] <=N&&i==N) {
            for(j = 1; j <= N; j++) {
                for(k = 1; k <= N; k++) {
                    if(arr[j] == k) {
                        printf(" *");
                    } else {
                        printf(" .");
                    }
                }
                printf("\n");
            }
            printf("\n");
 
            total++;
        } else if(arr[i] <= N && i < N) {
// 放置下一个皇后
            ++i;
        } else {
// 回溯
            arr[i] = 0;
            --i;
        }
    }
 
    printf("There are %d answers!\n\n", total);
}
 
// 检查皇后 x 放在 arr[x] 位置是否会有冲突
int checkPosition(int *arr, int x)
{
    int i;
    for(i = 1; i < x; i++) {
        if(arr[i] == arr[x] || abs(x - i) == abs(arr[x] - arr[i])) {
            return 0;
        }
    }
    return 1;
}

　　


联系
我们