八皇后问题即指在一个8*8的棋盘上放置8个皇后，不允许任何两个皇后在棋盘的同一行、同一列和同一对角线上。关键字：递归、上溯.通用技巧：
经观察发现，对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7)
其主对角线（即左上至右下）上的每个点的i-j+7的值（范围在(0,14)）均相等；
其从对角线（即右上至左下）上的每个点的i+j的值（范围在(0,14)）均相等；
且每个主对角线之间的i-j+7的值均不同，每个从对角线之间的i-j+7的值亦不同；
如a[3][4]:
主：3-4+7=6
从：3+4=7
因此可设两个数组b[15],c[15]分别表示主、从对角线是否安全
（为1表示有皇后，不安全；为0表示安全）
每行有且仅有一个皇后：
每i个皇后放在每i行(0<=i<=7)
void eightQueens( int line );
题目描述：
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2…b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。
输入：
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92)
输出：
输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。
样例输入：
2
1
92
样例输出：
15863724
84136275
思路
先贴出一个可以ac的摆放位置出来，防止大家连国际象棋棋盘的样子都不清楚。
由于八个皇后不能处在同一行，那么可以肯定每个皇后占据一行。我们可以先定义一个数组column[9],数组中的第i个数字表示位于第i行皇后的列号(因为数组下标从0开始，因此这里想表示1-8需要申请9个整型的数据空间)。
先把column数组初始化为1-8,忽略开始的第一个元素
接下来，对column做无重复的全排列，因为我们使用不同的数字对column进行初始化，所以八皇后肯定在不同的列。
接下来，我们只需要判断八皇后是否在同一对角线即可，学过数学的都知道，可以表示为y = x + b 或者 y = -x + b
|
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define EIGHT 8
struct result
{
int total;
int num[10];
};
int wzyindex, column[10];
struct result results[100];
/**
* Description:预处理八皇后的下标数组
*/
void pre_prosess(int n)
{
int i;
for (i = 1; i <= n; i ++) {
column[i] = i;
}
}
/**
* Description:column数组数字交换
*/
void swap(int begin, int k)
{
int temp;
temp = column[begin];
column[begin] = column[k];
column[k] = temp;
}
/**
* Description:防止全排列出现重复数据
*/
int check_swap(int begin, int k)
{
int i;
for (i = begin; i < k; i ++) {
if (column[i] == column[k]) {
return 0;
}
}
return 1;
}
int is_eightqueue(int n)
{
int i, j;
for (i = 1; i <= n; i ++) {
for (j = i + 1; j <= n; j ++) {
if (i - j == column[i] - column[j] || i - j == column[j] - column[i])
return 0;
}
}
return 1;
}
void permutation_queue(int begin, int end)
{
int k, total;
if (begin == end) { // 检查八皇后排列正确性
if (is_eightqueue(end)) {
for (k = 1, total = 0; k <= end; k ++) {
total = 10 * total + column[k];
results[wzyindex].num[k] = column[k];
}
results[wzyindex].total = total;
wzyindex ++;
}
} else { // 全排列
for (k = begin; k <= end; k ++) {
if (check_swap(begin, k)) { // 保证无重复的全排列
swap(begin, k);
permutation_queue(begin + 1, end);
swap(begin, k);
}
}
}
}
int compare(const void *p, const void *q)
{
const struct result *a = p;
const struct result *b = q;
return a->total - b->total;
}
int main()
{
int i, n, m;
pre_prosess(EIGHT);
wzyindex = 0;
permutation_queue(1, EIGHT);
qsort(results, wzyindex, sizeof(results[0]), compare);
while (scanf("%d", &n) != EOF) {
while (n --) {
scanf("%d", &m);
m -= 1;
for (i = 1; i <= EIGHT; i ++) {
printf("%d", results[m].num[i]);
}
printf("\\n");
}
}
return 0;
}
|
/**************************************************************
Problem: 1140
User: wangzhengyi
Language: C
Result: Accepted
Time:10 ms
Memory:916 kb
****************************************************************/
dfs思路
其实就是dfs挨层遍历，找出所有符合要求的组合，直接上ac代码
|
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
81
82
83
84
85
|
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define N 8
typedef struct point {
int x, y;
} point;
point pts[N];
typedef struct string {
char str[N + 1];
} string;
string strs[93];
int windex, count;
int isOk(int x, int y)
{
int i, flag = 1;
for (i = 0; i < count; i ++) {
if (pts[i].y == y || abs(y - pts[i].y) == abs(x - pts[i].x)) {
flag = 0;
break;
}
}
return flag;
}
void bfsEight(int level)
{
int i;
if (level > N) {
for (i = 0; i < N; i ++) {
strs[windex].str[i] = pts[i].y + '0';
}
strs[windex].str[i] = '\\0';
windex ++;
} else {
point t;
for (i = 1; i <= N; i ++) {
t.x = level;
t.y = i;
if (isOk(t.x, t.y)) {
pts[count ++] = t;
bfsEight(level + 1);
count -= 1;
}
}
}
}
int cmp(const void *p, const void *q)
{
const string *a = p;
const string *b = q;
return strcmp(a->str, b->str);
}
int main(void)
{
int n, num;
count = windex = 0;
bfsEight(1);
qsort(strs, count, sizeof(strs[0]), cmp);
scanf("%d", &n);
while (n --) {
scanf("%d", &num);
printf("%s\\n", strs[num - 1].str);
}
return 0;
}
|
/**************************************************************
Problem: 1140
User: wangzhengyi
Language: C
Result: Accepted
Time:10 ms
Memory:916 kb
****************************************************************/
相关文章
- ASP.NET自助建站系统的域名绑定与解析教程 2025-06-10
- 个人服务器网站搭建：如何选择合适的服务器提供商？ 2025-06-10
- ASP.NET自助建站系统中如何实现多语言支持？ 2025-06-10
- 64M VPS建站：如何选择最适合的网站建设平台？ 2025-06-10
- ASP.NET本地开发时常见的配置错误及解决方法？ 2025-06-10
