N queens Problem
This article will provide a fast way to find a solution for the famous N queens problem.
Note: we only try to find one possibility of all positions of chesses, NOT (ALL posibilities).
For example, when N=8, there are 92 ways to put the chesses. However, our algorithm just focus on finding one of these 92 ways.
If you still feels not familar with the problem we will solve. Please Google 8 queens problem and look down.
N=4
When N=4, there are only two ways to put these chesses.
10100
20001
31000
40010
10010
21000
30001
40100
Our program, as I just said, will try to find one of the two ways.
So, Here we go~
Code
1#include <stdio.h>
2#include <stdlib.h>
3#include <time.h>
4#include <string.h>
5
6#define N 123456789
7
8
9// 最大能运行多少个皇后
10
11int output_ok;
12
13void swap_int(int *p, int *q)
14{
15 int temp;
16 temp = *(p);
17 *(p) = *(q);
18 *(q) = temp;
19}
20
21int swap_ok, change_of_collisions, temp, n;
22// swap_ok判断是否交换两个皇后会使得collisions减小
23// change_of_collisions计算交换前后的collisions的变化量
24// temp用作交换两个变量的临时变量
25// n为皇后数目
26
27void print_solve1(int *x, int n, FILE *fp) // 传入queen,n和fp
28// 输出形象化的棋盘
29// *代表皇后 -代表棋盘
30{
31 fprintf(fp, "\nBEGIN\n");
32 for (int i = 1; i <= n; ++i)
33 {
34 for (int j = 1; j <= n; ++j)
35 {
36 if (j == x[i])
37 {
38 fprintf(fp, "*");
39 }
40 else
41 {
42 fprintf(fp, "-");
43 }
44 }
45 fprintf(fp, "\n");
46 }
47 fprintf(fp, "\nEND\n\n\n");
48}
49
50void print_solve(int *x, int n, FILE *fp) // 传入queen,n,fp
51// 输出皇后数列到文件n-queens-out.txt
52{
53 fprintf(fp, "%d\n", n);
54 for (int i = 1; i <= n; ++i)
55 {
56 fprintf(fp, "%d ", x[i]);
57 }
58 if (n <= 20)
59 {
60 print_solve1(x, n, fp);
61 }
62}
63
64int main()
65{
66 FILE *fp = fopen("n-queens-out.txt", "w");
67
68 int n;
69 // n皇后
70 printf("@Author: ZhangJia\n");
71 printf("@university: SCGY of USTC\n");
72 printf("@Github: Oyyko\n");
73 printf("\n");
74 printf("\n");
75 printf("Please Input the number N where the board is N*N.\n");
76 printf("which means we will have N queens\n");
77 scanf("%d", &n);
78
79 printf("Do you want to output to\"n-queens-out.txt\"\n");
80 printf("input 1 as yes ,other character as no\n");
81 scanf("%d", &output_ok);
82 if (output_ok != 1)
83 {
84 output_ok = 0;
85 }
86 printf("\nProgram START\n");
87
88 clock_t start, end;
89 //用于记录时间
90
91 int *pre_queen = (int *)malloc(sizeof(int) * N);
92 int *pre_dn = (int *)malloc(sizeof(int) * (2 * N - 1));
93 int *pre_dp = (int *)malloc(sizeof(int) * (2 * N - 1));
94 int *pre_attack = (int *)malloc(sizeof(int) * N);
95
96 int *queen = pre_queen - 1;
97 int *dn = pre_dn - 2;
98 int *dp = pre_dp - 1 + n;
99 int *attack = pre_attack - 1;
100 // 四个pre数组开辟空间
101 // 之后由对应的指针指向它们中间的位置
102 // 从而满足算法运行对数组下标的要求(即可能会出现负的下标)
103 // 例如 queen[1] = pre_queen[0]
104 // 例如 queen[m] = pre_queen[m-1]
105 // 例如 dn[m] = pre_dn[m-2]
106 // 例如 dp[m] = pre_dp[m+n-1]
107 // 例如 dp[-2] = pre_dp[-2+n-1]
108
109 // 数列queen[i]=j 表示第i行的皇后在第j列
110 // 数列dn[i]=k 表示斜率为负的对角线中编号为i的对角线上有k个皇后
111 // 数列dp[i]=k 表示斜率为正的对角线中编号为i的对角线上有k个皇后
112 // dn,dp的编号方法分别为(列号+行号),(列号-行号)
113 // 数列attack[i]=j 表示第i个被攻击的皇后在queen中的序号为j
114
115 memset(pre_dn, 0, sizeof(int) * (2 * n - 1));
116 memset(pre_dp, 0, sizeof(int) * (2 * n - 1));
117
118 int limit, collisions, number_of_attacks, loopcount;
119
120 collisions = 1;
121 start = clock();
122
123 while (collisions)
124 // 当评估函数为0时，不断执行，直到评估函数为0
125 // 评估函数为0也就是找到一组解
126 {
127 memset(pre_dn, 0, sizeof(int) * (2 * n - 1));
128 memset(pre_dp, 0, sizeof(int) * (2 * n - 1));
129 collisions = 0;
130
131 for (int i = 0; i <= n - 1; ++i)
132 {
133 pre_queen[i] = i + 1;
134 }
135 int Search_Max = (n << 2);
136 size_t x = -1;
137 x = (x >> 1);
138 int i, j;
139 int m;
140 int rand_max = n;
141 size_t rand_seed;
142 rand_seed = (size_t)time(NULL);
143 for (i = 1, j = 1; i <= Search_Max && j <= n; ++i)
144 {
145 // 我们的目标是在初始化阶段生成一个很好的初态
146 // 这样我们就能很快的爬山找到最优解
147 // 因为初态的collisions已经很小
148 // 因此爬山的过程会大幅度缩短
149 // 优化的方法就是在初始化的时候就尽可能的避免碰撞
150 // j的作用是衡量已经有多少个皇后被优化处理了,如果优化了n个,那么说明该停止优化了
151 // i的作用是限制优化阶段所采用的时间 每循环一次i就自加1
152 // 当i大于Search_Max的时候,强制退出优化过程
153 rand_seed *= 1103515245;
154 rand_seed += 12345;
155 rand_seed = rand_seed % (x + 1);
156 // LCG随机数生成器
157 // X(n+1) = (a * X(n) + c) % m
158 // 此处我采用a等于1103515245 c等于12345 的参数取法
159 // 该取法为gcc编译器的参数取值
160 // 为了合理的取值范围我采用了size_t类型
161 // 实际上就是生成一个 0~x的随机数
162
163 m = rand_max * ((double)rand_seed / (double)x) + j;
164 // m为 j~n之间的一个随机数
165 if (!(dn[queen[m] + j]) && !(dp[queen[m] - j]))
166 // 如果 皇后m 与 皇后j 交换可以减小评估函数的值
167 // 那么就交换m与j
168 {
169 swap_int(&queen[m], &queen[j]);
170 ++dn[queen[j] + j];
171 ++dp[queen[j] - j];
172 ++j;
173 --rand_max;
174 }
175 }
176 // 在优化完了j个皇后之后
177 // 打乱剩下的皇后,以使得初态更加平均
178 // 同时计算出所有dn与dp的值
179 for (i = j; i <= n; ++i)
180 {
181 m = rand() % rand_max + i;
182 swap_int(&queen[m], &queen[i]);
183 ++dn[queen[i] + i];
184 ++dp[queen[i] - i];
185 --rand_max;
186 }
187 // 以上完成了对整个棋盘的初始化
188
189 for (int i = 2; i <= 2 * n; ++i)
190 {
191 if (dn[i] > 1)
192 collisions += (dn[i] - 1);
193 }
194 for (int i = 1 - n; i <= n - 1; ++i)
195 {
196 if (dp[i] > 1)
197 collisions += (dp[i] - 1);
198 }
199 if (!collisions)
200 // 若恰好生成了满足要求的皇后排列,则输出答案并且结束程序
201 {
202 end = clock();
203 printf("It takes %f seconds to find a solotion\n", (double)(end - start) / CLOCKS_PER_SEC);
204 print_solve(queen, n, fp);
205 exit(0);
206 }
207
208 limit = collisions >> 1; // means limit=0.5*collisions
209 // limit的作用是评估何时适合重新计算attack数组，从而达到更快的运行速度。
210 // 如果每次交换都重新计算attack数组,那么开销过大.
211 // 为此我们采用设置阈值的方法
212 // 仅当collision<limit时，才重新计算attack。从而减小了不必要的损耗
213
214 // compute attack START
215
216 number_of_attacks = 0;
217 int k = 1;
218 for (int i = 1; i <= n; ++i)
219 {
220 if (dn[queen[i] + i] > 1 || dp[queen[i] - i] > 1)
221 {
222 attack[k++] = i;
223 ++number_of_attacks;
224 }
225 }
226 //compute attack END
227
228 loopcount = 0;
229 // loopcount用来判断何时随机重启
230 // 每次爬山都会增加loopcount的值
231 // 当loopcount比较大时,说明爬山法陷入了局部困境,需要进行随机重启
232
233 // Initialization END
234 // 初始化过程结束,下面开始爬山算法
235
236 while (loopcount < (n << 5))
237 {
238 for (int k = 1; k <= number_of_attacks; ++k)
239 {
240 int i = attack[k];
241 int j = ((rand() << 6) + rand()) % (n) + 1;
242 // 取一个被攻击的皇后和一个随机取得皇后,观察是否可以交换
243
244 swap_ok = 0;
245 change_of_collisions = 0;
246
247 change_of_collisions -= (dp[queen[i] - i] > 1);
248 change_of_collisions -= (dp[queen[j] - j] > 1);
249 change_of_collisions -= (dn[queen[i] + i] > 1);
250 change_of_collisions -= (dn[queen[j] + j] > 1);
251
252 change_of_collisions += (dn[queen[j] + i] >= 1);
253 change_of_collisions += (dn[queen[i] + j] >= 1);
254 change_of_collisions += (dp[queen[j] - i] >= 1);
255 change_of_collisions += (dp[queen[i] - j] >= 1);
256 // 计算评估函数的改变量
257 if (change_of_collisions < 0)
258 {
259 if (!(queen[i] + i - queen[j] - j) && !(dp[queen[i] - j]))
260 {
261 change_of_collisions += 2;
262 }
263 if (!(queen[i] - i - queen[j] + j) && !(dn[queen[i] + j]))
264 {
265 change_of_collisions += 2;
266 }
267 if (change_of_collisions < 0)
268 {
269 // perform swap
270 // 若改变量小于0,则执行交换
271 --dn[queen[i] + i];
272 --dp[queen[i] - i];
273 --dn[queen[j] + j];
274 --dp[queen[j] - j];
275 ++dn[queen[j] + i];
276 ++dn[queen[i] + j];
277 ++dp[queen[j] - i];
278 ++dp[queen[i] - j];
279
280 temp = queen[j];
281 queen[j] = queen[i];
282 queen[i] = temp;
283
284 collisions += change_of_collisions;
285
286 if (!collisions)
287 // 若找到了解,则输出答案并且结束程序
288 {
289 end = clock();
290 printf("It takes %f seconds to find a solotion\n", (double)(end - start) / CLOCKS_PER_SEC);
291 printf("Press any key to EXIT\n");
292 if (output_ok)
293 print_solve(queen, n, fp);
294 getchar();
295 getchar();
296 exit(0);
297 }
298 if (collisions < limit)
299 // 当棋盘变动较大时,重新计算attack数列
300 {
301 limit = collisions >> 1;
302 // compute attack
303
304 number_of_attacks = 0;
305 int k = 1;
306 for (int i = 1; i <= n; ++i)
307 {
308 if (dn[queen[i] + i] > 1 || dp[queen[i] - i] > 1)
309 {
310 attack[k++] = i;
311 ++number_of_attacks;
312 }
313 }
314 }
315 }
316 }
317 }
318
319 loopcount = loopcount + number_of_attacks;
320 }
321 }
322
323 return 0;
324}