13,152,454 members (42,196 online)
alternative version

#### Stats

257.6K views
84 bookmarked
Posted 19 Oct 2005

# 8 Queens Solution with Genetic Algorithm

, 19 Oct 2005
 Rate this:
Using Genetic Algorithm to solve the 8 Queens problem.

## Genetic Algorithm, Theory

There are so many books and so many resources on the Web about Genetic Algorithms. The best that I can do is quote some nice descriptions from my preferred sites.

"Genetic algorithms are a part of evolutionary computing, which is a rapidly growing area of artificial intelligence. As you can guess, genetic algorithms are inspired by Darwin's theory about evolution. Simply said, solution to a problem solved by genetic algorithms is evolved."

The GA begins, like any other optimization algorithm, by defining the optimization variables. It ends like other optimization algorithms too, by testing for convergence. A path through the components of the GA is shown as a flowchart in Figure 1.

Fig. 1 - A path through the components of the GA

#### Define cost function and cost

For each problem there is a cost function. For example, maximum of a 3D surface with peaks and valleys when displayed in variable space. Cost, a value for fitness, is assigned to each solution.

#### Chromosomes and genes

A gene is a number between 0 to n-1. A chromosome is an array of these genes. It could be an answer. Population in each generation has determined the number of chromosomes.

#### Create a random initial population

An initial population is created from a random selection of chromosomes. The number of generations needed for convergence depends on the random initial population.

#### Decode the chromosome and find the cost

To find the assigned cost for each chromosome a cost function is defined. The result of the cost function called is called cost value. Finally, the average of cost values of each generation converges to the desired answer.

#### Mating and next generation

Those chromosomes with a higher fitness (lesser cost) value are used to produce the next generation. The offsprings are a product of the father and the mother, whose composition consists of a combination of genes from them (this process is known as "crossing over"). If the new generation contains a chromosome that produces an output that is close enough or equal to the desired answer then the problem has been solved. If this is not the case, then the new generation will go through the same process as their parents did. This will continue until a solution is reached.

## About the 8 queens problem

In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 queen's problem asks how to place 8 queens on an ordinary chess board so that none of them can hit any other in one move. Here we solve this problem with a genetic algorithm for a n (n is between 8 and 30) queen problem.

## Using the code

We first describe the variables and the functions:

### Variables:

• `int ChromosomeMatrix[30][1000]`: This variable is a matrix of numbers between 0 to `ChessBoardLenght`-1. For example, if `ChessBoardLength`=8, `ChromosomeMatrix` could be {4,6,0,2,7,5,3,1} so that the first number defines the place of the queen in the first row, the second number defines the place of the queen in the second row and so on.
• `int CostMatrix[1000]`: For each chromosome matrix, a cost value is defined. The best value is 0 and when no queen can take the other one.
• `int CrossOverMatrix[30][1000]`: For generating children from parents, a crossover matrix is needed that decides which gene must be selected from the two parents.
• `int Population`, `int Iteration`, `float Mutationrate`: These variables are genetic algorithm parameters.
• `int ChessBoardLength`: This determines how many rows and columns a chessboard has.
• `int area[30][30]`: This variable is a chess board matrix.

### Functions:

```void CGAQueen::Clear()
{
// to Reset All cells
area[i][j]=0;
}```

This function is used to clear the chess board (`area[][]`) with 0s.

```void CGAQueen::InitialPopulation()
{
int random;
bool bCheck;
for (int index=0;index<=Population-1;index++)
{
random=rand();
bCheck=1;
for (int b=0;b<a;b++)
bCheck=0;
if (bCheck)
else
a--;
}
}```

This function is used to generate the initial population. This generation is a purely random generation. With this function, `ChromosomeMatrix[][]` is valued with random numbers between 0 and `ChessBoardLength`-1. The number of `ChromosomeMatrix` is equal to `Population`.

```void CGAQueen::FillArea(int index)
{
Clear();
area[i][ChromosomeMatrix[i][index]]=1;
}```

This function is used to fill the chess board with a chromosome. For example, if `ChromosomeMatrix` = {3,6,8,5,1,4,0,7,9,2}, the first number defines the column of the queen in the first row, the second number defines the column of the queen in the second row and so on. The area is shown in fig. 2 – here `ChessBoardLength` =10.

Fig. 2 - The chess board with `ChromosomeMatrix`={ 3,6,8,5,1,4,0,7,9,2}

```int CGAQueen::CostFunc(int index)
{
int costValue=0;
int m,n;
int i,j;
{
j=ChromosomeMatrix[i][index];
m=i+1;
n=j-1;
{
if(area[m][n]==1)
costValue++;
m++;
n--;
}

m=i+1;
n=j+1;
{
if(area[m][n]==1)
costValue++;
m++;
n++;
}
m=i-1;
n=j-1;
while(m>=0 && n>=0)
{
if(area[m][n]==1)
costValue++;
m--;
n--;
}
m=i-1;
n=j+1;
{
if(area[m][n]==1)
costValue++;
m--;
n++;
}
}
return costValue;
}```

This function is used to determines the cost value for each `ChromosomeMatrix[][]` and keeps it in `CostMatrix[]`. For example, for chromosome = { 2,6,9,3,5,0,4,1,7,8 }, the cost value will be 2. (See fig. 3.)

Fig. 3 - Because of these two queens that hit each other, the cost value is 2.

```void CGAQueen::PopulationSort()
{
bool k=1;
int Temp;
while (k)
{
k=0;
for (int i=0;i<=Population-2;i++)
{
if (CostMatrix[i]>CostMatrix[i+1])
{
Temp=CostMatrix[i];
CostMatrix[i]=CostMatrix[i+1];
CostMatrix[i+1]=Temp;

{
Temp=ChromosomeMatrix[j][i];
ChromosomeMatrix[j][i]=ChromosomeMatrix[j][i+1];
ChromosomeMatrix[j][i+1]=Temp;
}
k=1;
}
}
}
}```

This function is used to sort the new generation according to their cost value. The best (minimum) is placed on top and the worst (maximum) is placed in the bottom.

```void CGAQueen::GenerateCrossOverMatrix()
{
int randomCrossOver;
for (int index=0;index<=Population-1;index++)
{
randomCrossOver=rand();
CrossOverMatrix[a][index]=randomCrossOver%2;
}
}```

This function is used to generate the cross over matrix. This matrix contains 0s and 1s.

```void CGAQueen::Mating()
{
int TempMatrix[30][2];
int TempMatrix0[30],TempMatrix1[30];
int Temp,j,k;

…
}```

This function is used to generate children from parents using `CrossOverMatrix`. It is a way to do this job. Genes are drawn from p0 and p1. A gene is drawn from one parent and it is appended to the offspring (child) chromosome. The corresponding gene is deleted in the other parent (see figure 4). This step is repeated until both parent chromosomes are empty and the offspring contains all genes involved.

Fig. 4 The Cross Over method

```void CGAQueen::ApplyMutation()
{
int randomChromosome;
int randomGen0,randomGen1;
int Temp;
for(int k=0;k<=NumberOfMutation;k++)
{
randomChromosome=0;
while((randomChromosome=rand()%Population)==00;
Temp=ChromosomeMatrix[randomGen0][randomChromosome];
ChromosomeMatrix[randomGen0][randomChromosome]=
ChromosomeMatrix[randomGen1][randomChromosome];
ChromosomeMatrix[randomGen0][randomChromosome]=Temp;
}
}```

This function is used to apply mutation to the current generation. First of all, a random chromosome is selected but the first (best) one in the list. Then, two random genes of this chromosome are selected and replaced with each other. Increasing the number of mutations increases the algorithm’s freedom to search outside the current region of chromosome space.

There is a demo for you to enjoy the genetic algorithm.

Have fun.

A list of licenses authors might use can be found here

## Share

 Web Developer Iran (Islamic Republic of)
I live in Iran . I started hardware programming when I was young. I designed and built some ISA cards for attaching to PC.like ocsiloscope and signal generator. Now I am working for a engineering company and Manager of some project.

## You may also be interested in...

 Pro Pro

 First PrevNext
 komak error dare Member 1048505920-Dec-14 4:43 Member 10485059 20-Dec-14 4:43
 Salam Member 112851803-Dec-14 20:59 Member 11285180 3-Dec-14 20:59
 My vote of 5 Reza Aghaei16-Jan-14 8:42 Reza Aghaei 16-Jan-14 8:42
 salam Member 1048505923-Dec-13 21:52 Member 10485059 23-Dec-13 21:52
 Re: salam asef6-Feb-14 1:49 asef 6-Feb-14 1:49
 salam Member 1048505923-Dec-13 21:50 Member 10485059 23-Dec-13 21:50
 help plz Member 1048505923-Dec-13 21:47 Member 10485059 23-Dec-13 21:47
 how to run and compile Member 1000272121-Apr-13 6:12 Member 10002721 21-Apr-13 6:12
 Re: how to run and compile asef6-Feb-14 1:50 asef 6-Feb-14 1:50
 My vote of 5 akkaraikumar2-Apr-13 5:52 akkaraikumar 2-Apr-13 5:52
 this code translated to ansi c Vasile Alexandru Marian19-May-12 3:43 Vasile Alexandru Marian 19-May-12 3:43
 Visual 2008 or 2005 Member 399962824-Dec-11 5:49 Member 3999628 24-Dec-11 5:49
 My 5 Amir Mahfoozi19-Dec-11 1:10 Amir Mahfoozi 19-Dec-11 1:10
 java source code for 8 queen problem dasarishivasagar27-May-11 4:09 dasarishivasagar 27-May-11 4:09
 Hello, i need you help alexnox22-Mar-11 1:45 alexnox 22-Mar-11 1:45
 Visual 2008 lvlaryam19-Dec-10 6:34 lvlaryam 19-Dec-10 6:34
 My vote of 5 ked_man5-Nov-10 3:10 ked_man 5-Nov-10 3:10
 VS 2008 Support brazilian018-Aug-10 15:29 brazilian01 8-Aug-10 15:29
 Re: VS 2008 Support asef9-Aug-10 21:47 asef 9-Aug-10 21:47
 Re: VS 2008 Support lvlaryam19-Dec-10 6:16 lvlaryam 19-Dec-10 6:16
 Question in DFS(Depth First Search) neda_lia16-Jun-10 4:38 neda_lia 16-Jun-10 4:38
 THANKS SO MUCH neda_lia13-Jun-10 20:48 neda_lia 13-Jun-10 20:48
 Re: THANKS SO MUCH asef13-Jun-10 21:28 asef 13-Jun-10 21:28
 Thanks neda_lia30-May-10 21:20 neda_lia 30-May-10 21:20
 Re: Thanks asef30-May-10 22:52 asef 30-May-10 22:52
 Last Visit: 31-Dec-99 18:00     Last Update: 26-Sep-17 11:23 Refresh 123 Next »