Solution of n-Queen problem by GA

Solution of n-Queen Problem by Genetic Algorithm

n-Queen Problem: 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-Queen problem 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 is generated randomly with the constraint that all values in an individual are distinct. Fitness of individual is evaluated as the number of queens in no-attacking position. I have used Partially Matched Crossover, Swap Mutation, Ordered Encoding and CHC replacement strategy.

In the java applet Current Generation and Final Solution represents the best solution of current generation and final solution for the problem when all queens are at non-attacking position. Gen# is the no. of iterations completed. Solution is represented as (row, column) format, i.e. each (x, y) indicates row x and column y where a queen may be placed.

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

Programmed by

Paul Topon Kumar

Department of Frontier Informatics

Graduate School of Frontier Sciences

The University of Tokyo

Japan

Email: topon@miv.t.u-tokyo.ac.jp