See discussions, stats, and author profiles for this publication at: [Link]

net/publication/294121515

Solving 8-Queens Problem by Using Genetic Algorithms, Simulated

Annealing, and Randomization Method

Conference Paper · December 2013

DOI: 10.1109/DeSE.2013.41

CITATIONS READS

2 6,026

2 authors, including:

Belal Al-Khateeb
University of Anbar
47 PUBLICATIONS 220 CITATIONS

SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Artificial Intelligence in Information Security View project

All content following this page was uploaded by Belal Al-Khateeb on 04 August 2017.

The user has requested enhancement of the downloaded file.

 Solving 8-Queens Problem by Using Genetic
Algorithms, Simulated Annealing and Randomization
Method
Belal Al-Khateeb Wadhah Z. Tareq
Department of Computer Science Department of Computer Science
College of Computer - Al-Anbar University College of Computer - Al-Anbar University
Anbar, Iraq Anbar, Iraq
belal@[Link] wadahtarek@[Link]

Abstract— This paper introduced two Metaheuristics The rest of this paper will be organized as follows. A
algorithms for solving 8-queens problem in addition to background of NQP and EQP is presented. Then the
randomized method for finding all the 92 possible solutions experimental setup for each algorithm will be described.
for 8*8 chess board. The Metaheuristics algorithms are Experimental results and discussions for each algorithm are
Genetic Algorithm (GA) and Simulated Annealing (SA). illustrated. Finally, conclusions and future directions are
The proposed randomization method depends mainly on drawn up.
randomization in both the initialization phase and moving
phase that is used to find all the solutions. The obtained II. 8-QUEENS PROBLEM
results were promising as the GA and SA algorithms were
efficient in finding the solutions and both are better than the The N-queens problem is introduced in 1850 by Carl
randomization method. Also it has been found that SA was Gauss and has been studied for many decades by scientists.
better than the GA as it required less number of steps in The N-queens problem is an effort to find a placement of N
finding the solutions. queens on an N by N chess board so that no two queens
attack each other [4].
Index Terms— 8-queens, Genetic Algorithm, Simulated The number of correct solutions for N queens placed in
Annealing. N*N chessboard is fixed. For N queens from 1 to 15 the
number of possible solutions are shown in Table 1.
I. INTRODUCTION
TABAL 1: NUMBER OF SOLUTIONS FOR N-QUEENS PROBLEM
The aim of N-queens is to place N non attacking queens N 1 2 3 4 5 6 7 8 9 10
on an N*N chess board. This is a generalization of the solution 1 0 0 2 10 4 40 92 352 724
problem of putting eight non attacking queens on a N 11 12 13 14 15
chessboard, which was first posed in 1848 by M. Bezzel, a solution 2680 14200 73712 365596 2279184
German chess player, in the Berliner Schachzeitung [1]. The
goal of NQP problem is to arrange N queens on an N*N
chessboard in a way that there is no intersection between III. RELATED WORKS
them at both vertical or horizontal or diagonal directions.
EQP (Eight Queen Problem) is a special case of NQP, it is In 2003 Marko B. et. al. [5] used genetic algorithms to
trying to find a way to place eight queens on a chessboard solve N-queen problem. Also, a global parallel genetic
depending on NQP objective that is discussed above [2,3]. algorithm is demonstrated as a possible way to increase GA
In this paper we propose a randomized algorithm, Genetic speed. Tests showed that GA is able to find different
Algorithm and Simulated Annealing algorithm to generate solutions for a given number of queens.
all the possible solutions for eight queens’ problem by using In 2007 Ivica M and Marin G [6] showed that the NQP
different random initial solutions and calculating the fitness can be successfully solved using heuristic algorithms; they
for each solution used simulated annealing, tabu search and genetic algorithm
For each algorithm the intersection of a queen with and compared their efficiencies and achievements. Test
another queen is calculated to be the fitness for each results are demonstrated and upper bound complexity is
solution, of course the correct solution is the solution with determined.
fitness equal to zero (i.e no intersection). In 2009 Jordan B. and Brett S. [1] surveyed knowing
results for the N-queens problem of placing N queens on an
N*N chessboard and consider extensions of the problem, e.g. initial fitness is calculated and finally the randomization
other board topologies and dimensions. For all solution method is applied in order to arrive at the correct solution
constructions, they give the construction, an outline of it, or a (fitness equal to zero). Algorithm 1 shows the randomization
reference. Also, they give a simple result for finding the algorithm that is used to solve the 8-queens problem.
intersections of diagonals. Then investigate a number of
open research areas for the problem, stating several existing Algorithm1: Randomization Algorithm:
and new conjectures.
In 2009 Salabat K. et. al. [3] applied ACO (Ant Colony Input: Initial random solutions.
Optimization) to solve 8-Queen problem. Results show that Output: All possible solutions for eight queens problem.
ACO can provide better solution in reasonable amount of
time for combinatorial optimization problems. Step1: Generate 92 random solutions. This was done by
In 2010 Amer D. [Link]. [2] presented hybridization initializing 92 vectors (with length of 64), the
between differential evolutionary algorithms and quantum values in each vector are either one for the queen
computing principles such as quantum bits and states or zero for the empty square. Thus each vector
superposition. This algorithm is a hybridization of two well- will have eight queens distributed randomly.
known algorithms: DEA (Differential Evolution Algorithms) Step2: Calculate the fitness function for all the 92 vectors
and GA (Genetic Algorithm). The test results showed that that are constructed in step 1. The fitness function
this hybrid approach have a remarkable efficiency and good is calculated by counting the number of
results. interactions between the queens. Therefore a
In 2012 Farhad S. et. al. [4] proposed new resolution for fitness function with a value of zero means there
solving N-queens by using combination of DFS (Depth First was no interaction between the queens and
Search) and BFS (Breadth First Search) techniques. The represents the required solution.
proposed algorithm act based on placing queens on chess Step3: For all the 92 solutions do the following (ignore
board directly. The results report the performance and run any solution with fitness is equal to zero):
time of this approach. Step3: Select a queen in order.
Step4: Check the interaction for this selected queen:
IV. METAHEURISTIC a- First check the interactions in a row, if there is any
then move the interacted queen to another randomly
Computing optimal solutions is intractable for many selected position (not in the same row).
optimization problems of industrial and scientific b- If no interaction found in a then check the
importance. In practice, usually satisfied “good” for the interactions in a column, if there is any then move
solutions, which are obtained by heuristic or metaheuristic the interacted queen to another randomly selected
algorithms [7]. position (not in the same column).
As optimization techniques, Metaheuristics are the c- If no interaction found in b then check the
algorithms of the stochastic type aiming to solve abroad interactions in the diagonal, if there is any then
range of hard optimization problems, for which one does move the interacted queen to another randomly
not know more effective traditional methods. Often inspired selected position (not in the same diagonal).
by analogies with reality like physics (simulated Step5: Repeat Steps 2 to 4 until a new solution is found.
annealing, simulated diffusion and electromagnetism)
biology (evolutionary algorithms, tabu search) and VI. METAHEURISTICS ALGORITHMS
ethology (ant colony, particle swarms). They were
generally conceived at the beginning for discrete problems, 1. GENETIC ALGORITHM (GA)
but can be adapted to the other types of problems. They
share also the same disadvantages: difficulties of parameters GA is one of the most popular metaheuristic algorithms,
adjustment and large computation time [8]. its represent the space solution by population of chromosome
This paper used two of Metaheuristics algorithms and and each chromosome work as a solution for the problem.
applying them to find all the correct solutions for eight GA give the optimal solution depending on fitness
queens’ problem and then calculate the efficiency of each function and also depending on the structure of algorithm.
algorithm depending on the number of iterations which are The algorithm repeats the crossover of chromosome and the
required to find those solutions. mutation operations until reaching the optimal solution (stop
condition). Algorithm 2 shows the Genetic Algorithm that is
V. RANDOMIZATION ALGORITHM used to solve the 8-queens problem.
Randomization algorithm is designed and implemented for
solving 8-queen problem in order to find all the correct Algorithm2: Genetic Algorithm:
solutions. The algorithm starts by initializing 92 different
random solutions, which of course contain number of Input: Initial random solutions.
interactions between the queens, then for each solution the Output: All possible solutions for eight queens problem.
 Step1: Generate 100 random solutions. This was done by the current solution, so replace the new solution
initializing 100 vectors (with length of 64), the with the current solution.
values in each vector are either one for the queen Step8: Update T using the linear updating method;
or zero for the empty square. Thus each vector will T = T − β, where β is a specified constant value.
have eight queens distributed randomly. This is the Step9: Repeat steps 5-8 until the T value equal to zero
initial population for GA with size equal 100 which means a new solution is found.
chromosomes.
Step2: Evaluate the fitness of each chromosome
(solution). VII. RESULTS AND DISCUSSION
Step3: Rank the chromosomes depending on their
fitness’s values (small fitness values first). Tables 1 and 2 show the results of applying the
Step4: The 50 solutions that have the best fitness values randomization algorithm and genetic algorithm to find the 92
are selected as parents and retained for the next solutions for EQP, with the number of iterations that are
generation. Those parents are then used to create required to achieve each solution. While table 3 shows the
another 50 offspring using single point results of applying the simulated annealing algorithm to find
crossover. the 92 solutions for EQP, with number of iteration that are
Step5: The new solutions are mutated. required to achieve each solution. Also the temperature value
Step6: Repeat steps 2-5 until a new solution to the 8- for each solution is shown in table 3.
queens problem is found.
TABAL 1: RANDOMIZATION RESULTS
2. SIMULATED ANNEALING (SA) No iteration No iteration No iteration No iteration
1 85664 16 653216 31 592064 46 9248
The annealing process requires heating and then slowly 2 365280 17 132320 32 319552 47 61216
cooling to obtain a strong crystalline structure. In this paper 3 274080 18 426784 33 36640 48 784000
the main objective is to reach all the 92 possible solutions of 4 234752 19 41312 34 97952 49 81568
8-queens problem. So the SA repeats cooling process until 5 78080 20 59552 35 7616 50 322976
finding a new solution. The temperature will be set to the 6 113632 21 253440 36 497376 51 396768
current correct solution and decreases until finding new 7 280288 22 348864 37 489984 52 56960
solution.
8 248864 23 43616 38 868928 53 265344
Two loops are applied in the system, the first one for
9 451168 24 19168 39 923232 54 634848
finding new solution and compare it with the current correct
10 66336 25 368800 40 8480 55 57824
solution while the second loop is for generating random
neighborhoods, evaluate the object function and compare 11 207840 26 365952 41 128192 56 222720
them with the current solution as shown in algorithm3. 12 62912 27 154176 42 41824 57 558592
13 741568 28 428864 43 273440 58 40864
Algorithm3: Simulated Annealing Algorithm: 14 29312 29 205280 44 63584 59 688704
15 53696 30 501408 45 216544 60 227232
Input: Initial random solutions and Starting Temperature 61 567200 69 300128 77 51168 85 305920
(Tmax). 62 532256 70 176704 78 175712 86 57728
Output: All possible solutions for eight queens problem. 63 121376 71 189056 79 235904 87 252160
64 15808 72 655296 80 477760 88 59360
Step1: S = current solution generated randomly. 65 12832 73 59136 81 115296 89 128512
Step2: Evaluate the fitness function for the current 66 103136 74 240928 82 594176 90 494976
solution F(S). 67 453984 75 220480 83 464224 91 279552
Step4: T=Tmax. The T value is different from solution to 68 930272 76 176256 84 588960 92 980608
another.
Step5: Generate random neighborhood solution to be a TABAL 2: GENETIC ALGORITHM RESULTS
new solution (S'). The neighborhood generation No Iteration No iteration No iteration No iteration
is done by using initial solution and then using 1 23 24 347 47 656 70 983
full control moving (moving the attacking queens 2 33 25 352 48 666 71 989
to new non intersected positions. 3 36 26 353 49 679 72 999
Step6: Evaluate the objective function of the new 4 105 27 384 50 689 73 1014
solution F(S'). 5 120 28 407 51 694 74 1018
Step7: ∆E = F(S') − F(S); (∆E is the change in the 6 138 29 446 52 703 75 1035
objective function between S and S'). If ∆E value 7 142 30 449 53 718 76 1051
in negative then the new solution is better than 8 167 31 457 54 723 77 1068
9 175 32 479 55 724 78 1070
10 197 33 483 56 753 79 1076 control in the swapping of the attacking queens (i.e the
11 201 34 486 57 768 80 1112 random swap could lead to worse solutions).
12 214 35 488 58 808 81 1120 Also the obtained results show that SA is better than the
13 242 36 496 59 820 82 1135 GA in terms of the number of iterations that are required to
14 247 37 531 60 825 83 1150 find the solutions. This is because of the SA can escape
15 264 38 546 61 839 84 1156 from inefficient solutions due to the probabilistic acceptance
16 265 39 572 62 859 85 1163 of a non-improving neighbor. The probability of accepting a
17 275 40 575 63 863 86 1164 non-improving neighbor is proportional to the temperature T
18 291 41 589 64 869 87 1171 and inversely proportional to the change of the objective
19 294 42 594 65 904 88 1179 function ∆E.
20 295 43 607 66 912 89 1182
21 322 44 613 67 929 90 1192 VIII. CONCLUSIONS AND FUTURE WORKS
22 330 45 619 68 940 91 1197
This paper showed that the 8-queens problem can be
23 343 46 653 69 956 92 1205
solved by using metaheuristics. Two metaheuristic
algorithms were used; Genetic Algorithm and Simulated
TABAL 3: SIMULATED ANNEALING ALGORITHM RESULTS Annealing together with a randomization algorithm. GA and
No iteration T No iteration T No iteration T SA are applied and gave good results compared with the
randomization algorithm. The results of randomization
1 2 2 32 152 2 63 289 3
algorithm show that the number of movements (swaps)
2 9 7 33 153 1 64 294 5
needed to reach the optimal solution are varied, this due to
3 12 3 34 154 1 65 303 9
the randomness in the solutions’ construction. Also it has
4 18 6 35 157 3 66 303 0 been found that SA is better than GA as it needed about half
5 25 7 36 162 5 67 304 1 the number of iterations that GA needed to find all the
6 27 2 37 165 3 68 308 4 possible solutions of the 8-queens problem. This is due to
7 35 8 38 166 1 69 317 9 the nature of the SA algorithm, which allows the
8 44 5 39 174 8 70 319 2 probabilistic acceptance of a non-improving neighbor
9 44 0 40 175 1 71 322 3 solution.
10 50 6 41 175 0 72 327 5 There are two directions for the future works; the first
11 58 8 42 181 6 73 332 6 one is to use more metaheuristics algorithms for solving the
12 63 5 43 183 2 74 338 6 8-queens problem in order to have a full investigation for
13 66 3 44 188 5 75 346 6 the problem, while the second one is to apply the used
14 66 0 45 196 8 76 352 6 algorithms in solving other problems like course
15 67 1 46 200 4 77 355 3 timetabling.
16 75 8 47 208 8 78 357 2
17 79 4 48 216 8 79 365 8
REFERENCES
18 80 1 49 224 8 80 366 1
19 81 1 50 230 6 81 371 5 [1] Jordan B. and Brett S, "A survey of known results
20 86 5 51 234 4 82 373 2 and research areas for n-queens", Discrete
21 88 2 52 236 2 83 382 9 Mathematics 309, 2009.
22 92 4 53 241 5 84 387 5 [2] Amer D., Souham M., Hichem T., and Mohamed B,
23 96 4 54 245 4 85 395 8 "A Quantum Inspired Differential Evolution
24 103 9 55 252 7 86 404 9 Algorithm for Solving the N-Queens Problem", The
25 109 6 56 254 2 87 412 8 International Arab Journal of Information
Technology, Vol. 7, No. 1, January 2010.
26 118 9 57 262 8 88 413 1
[3] Salabat K., Mohsin B., M. Sharif, Malik S., R. Baig,
27 125 7 58 267 5 89 422 5
"Solution of n-Queen Problem Using ACO", IEEE,
28 130 5 59 271 4 90 433 1
2009.
29 139 9 60 278 7 91 435 2
[4] Farhad S., Bahareh S. and G. Feyzipour, "A New
30 141 2 61 281 3 92 444 9 Solution for N-Queens Problem using Blind
31 150 9 62 286 5 Approaches: DFS and BFS Algorithms",
International Journal of Computer Applications
The results in tables 1 through 3 clearly show that SA and (0975 – 8887) Volume 53– No.1, September 2012.
GA are better than the randomization method in terms of the [5] Marko B., Marin G. and Leo B, “Solving n-Queen
number of iterations that are required to find the solutions. problem using global parallel genetic algorithm ",
This is because in the randomization algorithm there was no EUROCON, Ljubljana, Slovenia, 2009.
[6] Ivica M and Marin G, "Comparison of Heuristic
 Algorithms for the N-Queen Problem", The ITI 29th
Int. Conf. on Information Technology Interfaces,
Cavtat, Croatia, June 25-28, 2007.
[7] El-Ghazali Talbi,"Metaheuristics From Design To
Implementation", John Wiley & Sons, 2009.
[8] Souier M, Sari Z, "A software tool for performance
metaheuristics evaluation in real time alternative
routing selection in random FMSs", 1st IEEE 2011
International Conference on Communications,
Computing and Control Applications (CCCA'11),
Hammamet Tunisia, 3–5 March 2011.

View publication stats