Solutionof n-Queen Problem by Genetic Algorithm

n-QueenProblem: Given a nxn chessboard,place n queens in such a way that no one attack is attacked by others.That is, no two queens will be in the same row, column or diagonal. For 4-Queenproblem the solution is


















            n-Queen by Genetic Algorithm: In GA the solution is represented as a vector X={x1,x2,x3,…,xn}where xi represents the column in ith row where queen i  may be placed. Initial population isgenerated randomly with the constraint that all values in an individual aredistinct. Fitness of individual is evaluated as the number of queens inno-attacking position.  I have usedPartially Matched Crossover, Swap Mutation, Ordered Encoding and CHCreplacement strategy.

            Inthe java applet Current Generation and Final Solution representsthe best solution of current generation and final solution for the problem whenall queens are at non-attacking position. Gen# is the no. of iterationscompleted. Solution is represented as (row, column)format, i.e. each (x, y) indicates row x and column y where a queen may beplaced.

            Graphical aswell as Text based solution is displayed when n<=50 and Text based solutionwhen n>50.


Programmed by

Paul Topon Kumar

Department of FrontierInformatics

Graduate School of FrontierSciences

The University of Tokyo


Email: topon@ibalab




                                                                                                                                                            Copyright©2002.All rights reserved by the programmer.