14,978,609 members
Articles / Multimedia / GDI
Article
Posted 25 Jun 2011

81.8K views
43 bookmarked

Solving Eight Queens Puzzle with Genetic Algorithm in C#

Rate me:
A C# code for solving eight queens puzzle using genetic algorithm

Introduction

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

In order to use genetic algorithm, it is a must to define the crossover operator, mutation operator, chromosome and genes.

Problem Representation

Gene: A gene is a number from 0 to 7 that means the row number that a queen is located. The position of the gene in a chromosome implies the column number of the queen. It is mandatory to locate one queen per column and row because there are same number of queens and columns/rows in the board.

Chromosome: A chromosome is a set of 8 genes. It is assumed to be that no duplicate genes in a chromosome.

Example:

0|1|4|2|3|6|7|5 8 queens are located in following cells.

`(0,0), (1,1), (2,4), (3,2), (4,3), (5,6), (6,7), (7,5)`

Mutation: Mutation is done with swapping the gene that is to be mutated with a randomly selected gene (except the gene that is currently subjected to the mutation) from the same chromosome.

Crossover: Genes are drawn from the two parent chromosomes with the probability of 0.5. A gene is drawn from one parent and it is appended to the offspring chromosome. The corresponding gene is deleted in the other parent. This step is repeated until both parent chromosomes are empty and the offspring contains all genes involved.

Fitness Function: A collision is two queens who are able to attack each other. This means they are in the same diagonal, the same row or the same column. Since the chromosome has no duplicate genes and it guarantees that 2 queens are not in a single column it is only needed to calculate the diagonal collisions. Therefore maximum number of collisions that can occur is 28. The fitness function is a higher-is-better function, so calculate it by subtracting the amount of collisions that occur in the current state from 28. A solution would have 0 collisions and thus a fitness of 28.

Using the Code

Classes and Structures

• `class ``GeneticAlgo`: The class that is responsible for all the operations of genetic algorithm.
• `class ``FitnessComparator`: A comparator class to sort chromosomes with fitness value in order to show the final population in the table.
• `struct Chromosome`: The structure that represents a chromosome which include genes, fitness and its cumulative of average fitness.
• `class MainFrame`: The class that responsible for handling user interface and create initial population in order to pass to the genetic algorithm.
• `class Board`: The class that is responsible for graphical view and operations of the chess board.

Variables

• `private const int <code>MAX_FIT` = 28; holds the maximum fitness.

Functions

C#
```private List<chromosome> GetInitialPopulation(int population)
{
List<chromosome> initPop = new List<chromosome>();
GeneticAlgo RandomGen = new GeneticAlgo();
for (int i = 0; i < population; i++)
{
List<int> genes = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7});
Chromosome chromosome = new Chromosome();
chromosome.genes = new int[8];
for (int j = 0; j < 8; j++)
{
int geneIndex = (int)(RandomGen.GetRandomVal
(0,genes.Count-1)+0.5);//randomly select a gene
chromosome.genes[j] = genes[geneIndex];
genes.RemoveAt(geneIndex);//remove selected gene
}

}
return initPop;
} ```

This function takes the size of population as the parameter and returns a list of chromosomes that contain randomly generated genes. The values of genes are randomly selected from a list that contains 0 to 7. While selecting the values from the list, the selected values are removed to avoid the duplication of genes in a chromosome. The size of the list is equal to the size of population. After creating the initial population using this function, the returned list of chromosomes sends to the function `DoMating`.

C#
```public void DoMating(ref List<Chromosome> initPopulation,
int generations, double probCrossver, double probMutation)
{
int totalFitness = 0;
CalcFitness(ref initPopulation, ref totalFitness);

for (int generation = 0; generation < generations; generation++)
{
PrepareRuletteWheel(ref initPopulation,totalFitness);
Crossover(ref initPopulation, probCrossver);
Mutate(ref initPopulation, probMutation);
CalcFitness(ref initPopulation, ref totalFitness);
if (initPopulation[initPopulation.Count - 1].fitness == 28)
break;
if (progress != null)
{
progress(generation + 1);
}
}
initPopulation.Sort(new FitnessComparator());
}  ```

This function takes a list of chromosomes as the initial population, number of generations that we are willing to propagate in the algorithm, the crossover probability and the mutation probability as its parameters. The responsible of this function is to handle the propagation to the required generation by invoking the functions `CalcFitness`, `PrepareRuletteWheel`, `Crossover `and `Mutate`.

C#
```public void CalcFitness(ref List<Chromosome> chromosome, ref int totalFitness)
{
int collisions = 0;
totalFitness = 0;
for (int k = 0; k < chromosome.Count; k++)
{
for (int i = 0; i < chromosome[k].genes.Length - 1; i++)
{
int x = i;
int y = chromosome[k].genes[i];
for (int j = i + 1; j < chromosome[k].genes.Length; j++)
{
if (Math.Abs(j - x) == Math.Abs
(chromosome[k].genes[j] - y))
collisions++;
}
}

Chromosome temp = chromosome[k];
temp.fitness = MAX_FIT - collisions;
chromosome[k] = temp;
totalFitness += chromosome[k].fitness;
collisions = 0;
}
}```

This function calculates the fitness of each chromosome and assigns the fitness value to the property `fitness` of each chromosome. The fitness is calculated by counting the number of collisions and deduct it from the maximum number of collisions because in this code the fitness is a higher-is-better function. While calculating the fitness for each chromosome, this function also calculates the total fitness of the population because we need it in the next step to calculate the fitness ratio of each chromosome.

C#
```private void PrepareRuletteWheel(ref List<Chromosome> parents,int total)
{
int currentTotalFitness=0;
for (int i = 0; i < parents.Count; i++)
{
currentTotalFitness += parents[i].fitness;
Chromosome temp = parents[i];
temp.cumAvgFitness = currentTotalFitness / (double)total;
parents[i] = temp;
}
}```

A rulette wheel that is based on the fitness of chromosome is used for selecting parents to mate in order to generate a new generation. This function is responsible for preparing the rullette wheel and it takes a list of chromosomes as the current population and the total fitness of the population. The function calculates the ratio of fitness of each chromosome to the total fitness and then calculates the cumulative of it to assign to the property `cumAvgFitness` of a chromosome.

C#
```public void Crossover(ref List<Chromosome> parents, double probability)
{
List<Chromosome> offspring = new List<Chromosome>();

for (int i = 0; i < parents.Count; i++)
{
if (Assay(probability)) //if the chance is to crossover
{
Chromosome parentX = AssayRuletteWheel(parents);
Chromosome parentY = AssayRuletteWheel(parents);

List<int> child = new List<int>();
for (int j = 0; j < 8; j++)
{
if (Assay(0.5)) //select from parentX
{
for (int k = 0; k < parentX.genes.Length; k++)
{
if (!child.Contains
//deleting the similar genes
//from parents select the
//next non-contained number
{
break;
}
}
}
else //select from parentY
{
for (int k = 0; k < parentY.genes.Length; k++)
{
if (!child.Contains
//deleting the similar genes from
//parents select the next
//non-contained number
{
break;
}
}
}
}
Chromosome offSpr = new Chromosome();
offSpr.genes = child.ToArray();

}
else //else the chance is to clone
{
Chromosome parentX = AssayRuletteWheel(parents);
}
}

while (offspring.Count > parents.Count)
{
offspring.RemoveAt((int)GetRandomVal(0, offspring.Count - 1));
}

parents = offspring;
}```

This function is responsible for crossing over and cloning operations. The function takes a list of chromosomes as the current population and the crossover probability as its parameters. The function `Assay(int probability)` returns `true `with the given probability, therefore it is used with the crossover probability to determine whether the operation is a crossing over or a cloning.

C#
```if (Assay(probability)) //if the chance is to crossover
{
Chromosome parentX = AssayRuletteWheel(parents);
Chromosome parentY = AssayRuletteWheel(parents);

List<int> child = new List<int>();
for (int j = 0; j < 8; j++)
{
if (Assay(0.5)) //select from parentX
{
for (int k = 0; k < parentX.genes.Length; k++)
{
//deleting the similar genes from parents
//select the next non-contained number
{
break;
}
}
}
else //select from parentY
{
for (int k = 0; k < parentY.genes.Length; k++)
{
//deleting the similar genes from parents
//select the next non-contained number
{
break;
}
}
}
}
Chromosome offSpr = new Chromosome();
offSpr.genes = child.ToArray();
}```

This part of code is from the above function and is responsible for crossover the two parents `parentX `and `parentY`. In order to create the offspring, genes are selecting from two parents with a probability of 0.5 while avoiding the gene duplication in the chromosome.

In the cloning operation, one parent is directly brought to the next generation.

C#
```public void Mutate(ref List<Chromosome> parents, double probability)
{
List<Chromosome> offsprings = new List<Chromosome>();
for (int i = 0; i < parents.Count; i++)
{
Chromosome offspring = parents[i];
for (int mutatePosition = 0; mutatePosition < 8; mutatePosition++)
{
if (Assay(probability)) //if the chance is to mutate
{
int newGeneIndex = (int)(GetRandomVal(0,6)+0.5);
if (newGeneIndex>=mutatePosition)
{
newGeneIndex += 1;
}
int swapTemp = offspring.genes[mutatePosition];
offspring.genes[mutatePosition] =
offspring.genes[newGeneIndex];
offspring.genes[newGeneIndex] = swapTemp;
}
}
}
parents = offsprings;
}```

This function applies the mutation operator with the given probability. It assays the chance of mutation while traversing the genes of chromosomes in the current population. If the mutation has to be applied to a gene, then it's value swaps with a randomly selected gene except the gene that is subjected to mutate from the same chromosome.

When a solution is achieved, the array of genes in the chromosome that contains the solution can be set to the property that are named as `Genes` in the class `Board`.

How to Use

The program allows you to specify the population size, number of generations, crossover probability and the mutation probability. The algorithm can be executed using the start button. If the population size and the number of generations are too large, please use the progress bar to indicate the current generation. But it can dramatically slow down the algorithm.

All the chromosomes of the final generation are shown in the table and the graphical chess board shows the best result.

Share

 First PrevNext
 is the algorithm get all possible correct solution? abdo512-May-18 23:56 abdo5 12-May-18 23:56
 About the fitness value Mujeeba Haj Najeeb7-Apr-17 3:53 Mujeeba Haj Najeeb 7-Apr-17 3:53
 Re: About the fitness value Ravimal Bandara30-Apr-17 6:43 Ravimal Bandara 30-Apr-17 6:43
 Re: About the fitness value Mujeeba Haj Najeeb30-Apr-17 10:35 Mujeeba Haj Najeeb 30-Apr-17 10:35
 8th Queen is capturing other Queen in all slouting Syed Murad Shah16-Dec-15 3:26 Syed Murad Shah 16-Dec-15 3:26
 Re: 8th Queen is capturing other Queen in all slouting Ravimal Bandara21-Dec-15 22:08 Ravimal Bandara 21-Dec-15 22:08
 can you help me in this please ?? i think that's easy for you Member 1213530412-Nov-15 23:17 Member 12135304 12-Nov-15 23:17
 Is there any generation size limitation. Member 113431151-Jan-15 5:01 Member 11343115 1-Jan-15 5:01
 Re: Is there any generation size limitation. Ravimal Bandara1-Jan-15 17:18 Ravimal Bandara 1-Jan-15 17:18
 using genatic algorithm to built time table schedular in c# neeraj kumar gandhi17-Mar-14 19:10 neeraj kumar gandhi 17-Mar-14 19:10
 Re: using genatic algorithm to built time table schedular in c# Ravimal Bandara19-Mar-14 6:12 Ravimal Bandara 19-Mar-14 6:12
 My vote of 5 Joezer BH29-Jul-13 21:53 Joezer BH 29-Jul-13 21:53
 RuletteWheel moein.serpico11-Dec-12 9:47 moein.serpico 11-Dec-12 9:47
 Re: RuletteWheel Ravimal Bandara3-Jun-13 2:05 Ravimal Bandara 3-Jun-13 2:05
 can i idris aliu10-May-12 8:05 idris aliu 10-May-12 8:05
 My vote of 5 Manoj Kumar Choubey27-Mar-12 23:51 Manoj Kumar Choubey 27-Mar-12 23:51
 structs + arrays Christian Setzkorn3-Jan-12 5:17 Christian Setzkorn 3-Jan-12 5:17
 8 queens gardenona14-Nov-11 21:09 gardenona 14-Nov-11 21:09
 My vote of 5 gardenona14-Nov-11 21:02 gardenona 14-Nov-11 21:02
 My vote of 4 ham_gr806-Jul-11 20:40 ham_gr80 6-Jul-11 20:40
 My vote of 5 Filip D'haene30-Jun-11 5:03 Filip D'haene 30-Jun-11 5:03
 My vote of 5 s.kleinschmidt28-Jun-11 5:10 s.kleinschmidt 28-Jun-11 5:10
 Re: My vote of 5 Ravimal Bandara9-Jul-11 6:39 Ravimal Bandara 9-Jul-11 6:39
 Nice work but this can be simply coded rationally George Swan26-Jun-11 12:42 George Swan 26-Jun-11 12:42
 Last Visit: 31-Dec-99 18:00     Last Update: 31-Jul-21 14:44 Refresh 12 Next ᐅ