Solution of n-Queen problem by GA

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

	Q
			Q
Q
		Q

n-Queen by Genetic Algorithm: In GA the solution is represented as a vector X={x_1,x₂,x₃,…,x_n}where x_i represents the column in i^th 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

Japan

Email: topon@ibalab