-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathqueen_issue.cpp
More file actions
195 lines (166 loc) · 3.58 KB
/
queen_issue.cpp
File metadata and controls
195 lines (166 loc) · 3.58 KB
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define SUCCESS 1
#define FAIL 0
#define EMPTY -65536
int failNodeNum, sumNodeNum, N;
int *tryp, *array135, *array45, *arrayCol;
void alloc_array(int n)
{
tryp = (int *)malloc(sizeof(int)*(n + 1));
array135 = (int *)malloc(sizeof(int)*(n + 1));
array45 = (int *)malloc(sizeof(int)*(n + 1));
arrayCol = (int *)malloc(sizeof(int)*(n + 1));
}
void free_array()
{
free(tryp);
free(array135);
free(array45);
free(arrayCol);
}
void init(int *array, int n)//初始化集合，使之为空集.
{
int i = 0;
for (; i <= n; i++) {
array[i] = EMPTY;
}
}
void init_all(int n)
{
init(tryp, n);
init(array135, n);
init(array45, n);
init(arrayCol, n);
failNodeNum = 0, sumNodeNum = 0;
}
//有多少个皇后，危险关系数组里就各自有多少个值。
int inArray(int i, int j)
//判断第i个皇后的位置(i,j)是否在危险位置里
{
int i1 = 1;
for (; i1 <= N; i1++) //for(;i1<=i-1;i1++)
{
if (array135[i1] == (i + j) || array45[i1] == (j - i) || arrayCol[i1] == j) {
return 1;
}
if (array135[i1] == EMPTY)
{
return 0;
}
}
return 0;
}
void insertArray(int i, int j) //第i个皇后的位置(i,j)
{
array135[i] = i + j;
array45[i] = j - i;
arrayCol[i] = j;
}
void popArray(int i) //删除第i个皇后的危险关系
{
array135[i] = EMPTY;
array45[i] = EMPTY;
arrayCol[i] = EMPTY;
}
int backtrace(int stepVegas) //已经放好了i-->stepVegas个皇后，之后放stepVegas+1-->N个皇后。行
{
int i = stepVegas + 1, j = 1;
while (i <= N) //当前行号小于N，棋盘大小
{
sumNodeNum++; //搜索的结点总数
for (; j <= N; j++)
{
if (!inArray(i, j)) //(i,j)不在列、45、135这些危险位置集合里-->safe j
{
insertArray(i, j);//放置皇后
i++; //寻找下一个皇后的位置
j = 1;
break;
}
}
if (j>N) //当前的皇后i没有安全的位置
{
if (i <= 1) { /*回退到1号皇后时也没有找到合适位置，那么不能再回退了，此时回溯法失败，返回FAIL(这种情况在LV算法调用backtrace时发生，因为此时可能找不到一组解free(array45);)*/
return FAIL;
}
else {
failNodeNum++; //回退的节点总数
i--; //从i-1的arrayCol[i]+1位置开始重新找i-1的位置。
j = arrayCol[i] + 1;
popArray(i); //将对应数组值置为EMPTY,删除(i-1)th皇后的危险位置
}
}
}
return SUCCESS;
}
int QueensLV(int stepVages)
{
int row = 1, col, nb;
int j;
while (row <= stepVages) { //改进的LV算法，只随机放置stepVages个皇后
nb = 0;
j = 1;
srand((unsigned)time(0));
sumNodeNum++;
for (; j <= N; j++) { //为row行找一个随机的位置col(在所有open位置中选择一个)
if (!inArray(row, j)) {
nb++;
if (((rand() % nb) + 1) == 1) {
col = j;
}
}
}
if (nb>0) { //存在合适的位置
insertArray(row, col);
tryp[row] = col;
}
else { //nb=0,不存在合适的位置，返回
return FAIL;
}
row++;
}
if (stepVages == N) {
return SUCCESS;
}
int flag = backtrace(stepVages);
return flag;
}
void Obstinate(int stepVages, int n)
{
int flag = -1, m_stepVages = stepVages;
do {
init(tryp, n);
init(array135, n);
init(array45, n);
init(arrayCol, n);
flag = QueensLV(m_stepVages);
} while (flag == 0);
}
int main()
{
//用搜索的结点数来找最优的stepVegas（因为搜索的总结点数正比于执行时间）
int best_sv = -1, tmp_sv;
double tmp_rate, best_rate = -0.01;
N = 12;
for (; N <= 20; N++) { //N-皇后的最优stepVages.
alloc_array(N);
best_sv = -1, best_rate = -0.01;
tmp_sv = 1;
for (; tmp_sv <= N; tmp_sv++) {
init_all(N);
Obstinate(tmp_sv, N);
tmp_rate = (double)sumNodeNum;
if (tmp_rate<best_rate || best_rate<0.0) {
best_sv = tmp_sv;
best_rate = tmp_rate;
}
}
printf("当N=%d时，stepVages=%d.\n", N, best_sv);
free_array();
}
system("pause");
return 0;
}