-
Notifications
You must be signed in to change notification settings - Fork 0
/
nqueens.c
481 lines (408 loc) · 12.6 KB
/
nqueens.c
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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
/* nqueens.c: (c) Arnold Meijster (a.meijster@rug.nl) */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>
#define MAXQ 100
#define POPULATION_SIZE 10
#define FALSE 0
#define TRUE 1
#define ABS(a) ((a) < 0 ? (-(a)) : (a))
int nqueens; /* number of queens: global variable */
int queens[MAXQ]; /* queen at (r,c) is represented by queens[r] == c */
void initializeRandomGenerator() {
/* this routine initializes the random generator. You are not
* supposed to understand this code. You can simply use it.
*/
time_t t;
srand((unsigned) time(&t));
}
/* Generate an initial position.
* If flag == 0, then for each row, a queen is placed in the first column.
* If flag == 1, then for each row, a queen is placed in a random column.
*/
void initiateQueens(int flag) {
int q;
for (q = 0; q < nqueens; q++) {
queens[q] = (flag == 0? 0 : rand()%nqueens);
}
}
/* returns TRUE if position (row0,column0) is in
* conflict with (row1,column1), otherwise FALSE.
*/
int inConflict(int row0, int column0, int row1, int column1) {
if (row0 == row1) return TRUE; /* on same row, */
if (column0 == column1) return TRUE; /* column, */
if (ABS(row0-row1) == ABS(column0-column1)) return TRUE;/* diagonal */
return FALSE; /* no conflict */
}
/* returns TRUE if position (row,col) is in
* conflict with any other queen on the board, otherwise FALSE.
*/
int inConflictWithAnotherQueen(int row, int col) {
int queen;
for (queen=0; queen < nqueens; queen++) {
if (inConflict(row, col, queen, queens[queen])) {
if ((row != queen) || (col != queens[queen])) return TRUE;
}
}
return FALSE;
}
/* print configuration on screen */
void printState() {
int row, column;
printf("\n");
for(row = 0; row < nqueens; row++) {
for(column = 0; column < nqueens; column++) {
if (queens[row] != column) {
printf (".");
} else {
if (inConflictWithAnotherQueen(row, column)) {
printf("Q");
} else {
printf("q");
}
}
}
printf("\n");
}
}
/* move queen on row q to specified column, i.e. to (q,column) */
void moveQueen(int queen, int column) {
if ((queen < 0) || (queen >= nqueens)) {
fprintf(stderr, "Error in moveQueen: queen=%d "
"(should be 0<=queen<%d)...Abort.\n", queen, nqueens);
exit(-1);
}
if ((column < 0) || (column >= nqueens)) {
fprintf(stderr, "Error in moveQueen: column=%d "
"(should be 0<=column<%d)...Abort.\n", column, nqueens);
exit(-1);
}
queens[queen] = column;
}
/* returns TRUE if queen can be moved to position
* (queen,column). Note that this routine checks only that
* the values of queen and column are valid! It does not test
* conflicts!
*/
int canMoveTo(int queen, int column) {
if ((queen < 0) || (queen >= nqueens)) {
fprintf(stderr, "Error in canMoveTo: queen=%d "
"(should be 0<=queen<%d)...Abort.\n", queen, nqueens);
exit(-1);
}
if(column < 0 || column >= nqueens) return FALSE;
if (queens[queen] == column) return FALSE; /* queen already there */
return TRUE;
}
/* returns the column number of the specified queen */
int columnOfQueen(int queen) {
if ((queen < 0) || (queen >= nqueens)) {
fprintf(stderr, "Error in columnOfQueen: queen=%d "
"(should be 0<=queen<%d)...Abort.\n", queen, nqueens);
exit(-1);
}
return queens[queen];
}
/* returns the number of pairs of queens that are in conflict */
int countConflicts() {
int cnt = 0;
int queen, other;
for (queen=0; queen < nqueens; queen++) {
for (other=queen+1; other < nqueens; other++) {
if (inConflict(queen, queens[queen], other, queens[other])) {
cnt++;
}
}
}
return cnt;
}
/* evaluation function. The maximal number of queens in conflict
* can be 1 + 2 + 3 + 4 + .. + (nquees-1)=(nqueens-1)*nqueens/2.
* Since we want to do ascending local searches, the evaluation
* function returns (nqueens-1)*nqueens/2 - countConflicts().
*/
int evaluateState() {
return (nqueens-1)*nqueens/2 - countConflicts();
}
/*************************************************************/
void saveState(int* successor){
for(int i = 0; i < nqueens; i++){
successor[i] = queens[i];
}
}
void loadState(int* successor){
for(int i = 0; i < nqueens; i++){
queens[i] = successor[i];
}
}
int nextSuccessor() {
int score = evaluateState();
int moveQueenIdx = -1;
int moveQueenNewPos = 0;
for (int i = 0; i < nqueens; i++) {
int pos = queens[i];
for (int nextPos = 0; nextPos < nqueens; nextPos++) {
if (nextPos == pos) continue;
queens[i] = nextPos;
int newScore = evaluateState();
// We have a 10% chance to throw away the current best move if the score is equal
if (newScore > score || (newScore == score && (rand() < (RAND_MAX / 10)))) {
score = newScore;
moveQueenIdx = i;
moveQueenNewPos = nextPos;
}
}
// Reset move
queens[i] = pos;
}
if (moveQueenIdx == -1) {
// No change
return 0;
} else {
queens[moveQueenIdx] = moveQueenNewPos;
return 1;
}
}
void randomSuccessor(int* next){
//choosing a random row and column to change for the next state
int row = (rand() / (RAND_MAX / nqueens));
int column;
for(int i = 0; i < nqueens; i++){
next[i] = queens[i];
if(i == row){
do{
column = (rand() / (RAND_MAX / nqueens));
}while(column == next[i]);
next[i] = column;
}
}
}
/*************************************************************/
/* A very silly random search 'algorithm' */
#define MAXITER 40
void randomSearch() {
int queen, iter = 0;
int optimum = (nqueens-1)*nqueens/2;
while (evaluateState() != optimum) {
printf("iteration %d: evaluation=%d\n", iter++, evaluateState());
if (iter == MAXITER) break; /* give up */
/* generate a (new) random state: for each queen do ...*/
for (queen=0; queen < nqueens; queen++) {
int pos, newpos;
/* position (=column) of queen */
pos = columnOfQueen(queen);
/* change in random new location */
newpos = pos;
while (newpos == pos) {
newpos = rand() % nqueens;
}
moveQueen(queen, newpos);
}
}
if (iter < MAXITER) {
printf ("Solved puzzle. ");
}
printf ("Final state is");
printState();
}
void printGen(int** Gen){
for(int i = 0; i < nqueens; i++){
for(int j = 0; j < nqueens; j++){
printf("%d ", Gen[i][j]);
}
printf("rand = %d \n", rand());
}
}
/*************************************************************/
void hillClimbing() {
int eval, i;
eval = nextSuccessor();
for(i = 2; eval != ((nqueens-1)*nqueens/2) ; i++){
if (nextSuccessor() == 0) {
// Random restart
initiateQueens(1);
}
eval = evaluateState();
}
printf ("Solved puzzle in %d iterations.\n", i);
printf ("Final state is");
printState();
}
/*************************************************************/
double prop(int deltaE, double temperature){
return (exp(deltaE/temperature));
}
double calculateTemperature(int t, int timeMax) {
//return (1.0 - (double)t/timeMax) * 5;
//double component = 1.0 / ((double)t/timeMax);
//1.0/t is the best thus far
return (1.0/t);
}
double fRandom() {
return rand()/(double)RAND_MAX;
}
void simulatedAnnealing() {
int t, deltaE, currentValue, timeMax = 100000;
int nextState[nqueens], currentState[nqueens];
double temperature;
for(t = 1; t < timeMax; t++){
saveState(currentState);
currentValue = evaluateState();
temperature = calculateTemperature(t, timeMax);
if(temperature == 0 || currentValue == (nqueens-1)*nqueens/2){
break;
}
//Saving a successor of the current state in nextState
randomSuccessor(nextState);
loadState(nextState);
deltaE = evaluateState() - currentValue;
if(deltaE > 0){
loadState(nextState);
}else if(prop(deltaE, temperature) >= fRandom()){
loadState(nextState);
} else {
loadState(currentState);
}
}
printf("Conflicts %d\n", countConflicts());
printf ("Solved puzzle in %d iterations.\n", t);
printf ("Final state is");
printState();
}
/*************************************************************/
typedef struct {
int* queens;
} gIndividual;
gIndividual newIndividual(int* baseState) {
gIndividual ind;
ind.queens = malloc(sizeof(int) * nqueens);
memcpy(ind.queens, baseState, sizeof(int) * nqueens);
return ind;
}
int cmpIndividualByFitness(const void* a, const void* b) {
loadState(((gIndividual*)a)->queens);
int scoreA = countConflicts();
loadState(((gIndividual*)b)->queens);
int scoreB = countConflicts();
return scoreA - scoreB;
}
typedef struct {
int a;
int b;
} CrossOverLocation;
int generateNumberWithBias() {
// We have 4 groups depending on the population size
// First group has a 50% chance, second group 20%, third group 20%, fourth group 10%
int rnd = rand() % 100;
int rndIndividual = rand() % (POPULATION_SIZE/4);
if (rnd < 50) {
return rndIndividual;
} else if (rnd < 70) {
return rndIndividual + (POPULATION_SIZE/4);
} else if (rnd < 90) {
return rndIndividual + (POPULATION_SIZE/4 * 2);
} else {
return rndIndividual + (POPULATION_SIZE/4 * 3);
}
}
CrossOverLocation generateCrossOverLocation() {
CrossOverLocation loc;
loc.a = generateNumberWithBias();
do {
loc.b = generateNumberWithBias();
} while (loc.a == loc.b);
return loc;
}
void doCrossOver(gIndividual a, gIndividual b, gIndividual out) {
// Choose random location in the "string"
int randomLoc = rand() % (nqueens - 1) + 1;
// Copy A
memcpy(out.queens, a.queens, sizeof(int) * nqueens);
// Do crossover
if (rand() % 2) {
// Cross heads
for (int i = 0; i < randomLoc; i++) {
out.queens[i] = b.queens[i];
}
} else {
// Cross tails
for (int i = nqueens/2; i >= randomLoc; i--) {
out.queens[i] = b.queens[i];
}
}
}
void geneticAlgorithm() {
gIndividual populationA[POPULATION_SIZE];
gIndividual populationB[POPULATION_SIZE];
gIndividual* currentPopulation = populationA;
gIndividual* nextPopulation = populationB;
// Initialize the population with random boards
for (int i = 0; i < POPULATION_SIZE; i++) {
populationA[i] = newIndividual(queens);
populationB[i] = newIndividual(queens);
initiateQueens(1);
}
do {
// Sort population by their fitness in ascending order (0 is best)
qsort(currentPopulation, POPULATION_SIZE, sizeof(gIndividual), cmpIndividualByFitness);
// Check if we have a solution (fitness of idx 0 == 0)
loadState(currentPopulation[0].queens);
if (countConflicts() == 0) {
break;
}
// Keep the 2 most fit ones
// Copy first 2
for (int i = 0; i < 2; i++) {
memcpy(nextPopulation[i].queens, currentPopulation[i].queens, sizeof(int) * nqueens);
}
// Crossover last POPULATION_SIZE - 2
for (int i = 2; i < POPULATION_SIZE; i++) {
CrossOverLocation location = generateCrossOverLocation();
doCrossOver(currentPopulation[location.a], currentPopulation[location.b],
nextPopulation[i]);
}
// Apply mutations
for (int i = 1; i < POPULATION_SIZE; i++) {
int numberOfMutations = rand() % 3;
for (int nM = 0; nM < numberOfMutations; nM++) {
nextPopulation[i].queens[rand() % nqueens] = rand() % nqueens;
}
}
gIndividual* swap = currentPopulation;
currentPopulation = nextPopulation;
nextPopulation = swap;
} while (1);
for (int i = 0; i < POPULATION_SIZE; i++) {
free(populationA[i].queens);
free(populationB[i].queens);
}
printf ("Solved puzzle.\n");
printf ("Final state is");
printState();
}
int main(int argc, char *argv[]) {
int algorithm;
do {
printf ("Number of queens (1<=nqueens<%d): ", MAXQ);
scanf ("%d", &nqueens);
} while ((nqueens < 1) || (nqueens > MAXQ));
do {
printf ("Algorithm: (1) Random search (2) Hill climbing ");
printf ("(3) Simulated Annealing (4) Genetic Algorithm: ");
scanf ("%d", &algorithm);
} while ((algorithm < 1) || (algorithm > 4));
initializeRandomGenerator();
initiateQueens(1);
printf("\nInitial state:");
printState();
switch (algorithm) {
case 1: randomSearch(); break;
case 2: hillClimbing(); break;
case 3: simulatedAnnealing(); break;
case 4: geneticAlgorithm(); break;
}
return 0;
}